Questions about how specific notions have to be understood as well as conventions of notation.

learn more… | top users | synonyms

1
vote
0answers
20 views

Is there a term for “delegate” function in CS?

This question is all about terminology (names). When you consider "list", this term is well defined in CS -- despite the fact programming languages use and misuse this term (for example C# ...
0
votes
0answers
32 views

Does a computer science major need any certificates after completing their major? [closed]

sorry if this a dumb question, and many, many thanks in advance!!! assuming one were to do well academically, and build up their portfolio also during their free time (hobby and such), would a ...
3
votes
1answer
77 views

What is the name of the property where $f(A) \supseteq f(B)$ when $A\supseteq B$?

Suppose I have a function $f$ on sets. What is the property of $f$ called when, for all sets $x$, $y$: $f(x)$ is a superset of $f(y)$ when $x$ is a superset of $y$ i.e. $$\forall x,y : ...
0
votes
1answer
31 views

Terminology for describing a kind of server [closed]

What is the adjective used to describe the fact that a server keep track of queries made by a user. I take the example of a database server.
9
votes
2answers
602 views

What is a lay explanation for universal search?

I am reading a book on a computer science topic but lack some of the prerequisite background. Normally when I run into terms I don't understand I simply look them up, but for Universal Search I simply ...
2
votes
1answer
30 views

What makes a metaheuristic meta?

According to Wikipedia: ...metaheuristic is a higher-level procedure or heuristic designed to find, generate, or select a lower-level procedure or heuristic (partial search algorithm) that may ...
1
vote
1answer
28 views

Shortcut for “in the worst-case, with high probability”?

I am writing a paper in which the worst-case analysis of a certain randomized algorithm is correct with probability $1-1/n$ (where $n$ is the size of the problem). I find myself writing, time after ...
0
votes
0answers
139 views

Do programmers write programs? [migrated]

Frozen since 1837, some guy just thawed up and confronted me with the verb 'to program' in the context of CS. If by /programming/ an automatic computer, we mean /to put instructions in main memory ...
3
votes
1answer
68 views

Is a “tree” with $0$ vertices, $0$ edges or $1$ vertex, $0$ edges considered a valid tree?

For the following $2$ cases: (1) $V = \emptyset, E = \emptyset $ (i.e. nothing at all) (2) $V = \{v_0\}, E = \emptyset $ (i.e. only 1 root node $v_0$) Are they considered a valid tree? It seems ...
3
votes
2answers
58 views

Why Shannon's Entropy is said to be a measure of information?

I got a bit of how Shannon explained to find the number of bits required to represent a message and Shannon's Entropy.But it's natural to know that to code alphabet letters you need ...
-1
votes
1answer
25 views

Definition of co-RE class

I know that the definition of RE class is: $\ RE = \left \{ L \subseteq \Sigma ^{*} | \text{Exists M which accepts L} \right \}$ Can someone explain in the same notation the definition of co-RE.
1
vote
1answer
21 views

Type of undecidability in Rice Theorem

Rice theorem says every non-trivial property of languages of Turing machines is undecidable. As David Richerby said in here : Undecidable means not decidable. Undecidable problems may or may not ...
0
votes
1answer
20 views

What is the name of this size method calculating the size of a node?

My confusion is that if the recursive call calls the left nodes, and then adds with the right nodes, how are the nodes that are to to right of the left nodes and vice versa being called? ...
0
votes
1answer
24 views

What is the name for this … (alerting when threshold is exceeded, but only if dropped enough below threshold first)

Imagine: you are monitoring a system, and want an alert when certain measured value goes over a threshold value X. But perhaps the measured value is constantly fluctuating close to X, and you get a ...
2
votes
1answer
41 views

What is the meaning of undecidability in Rice Theorem?

Rice theorem says every non-trivial property of languages of Turing machines is undecidable. what is the meaning of undecidability here? is it semi-decidable? As an example the following language is ...
2
votes
1answer
44 views

What type is this sorting algorithm?

I needed to sort vertices into buckets as an optimization for collision detection later. I came up with this: go over all the verts and count the size that each bucket needs to be to contain them ...
0
votes
2answers
47 views

How to find out if a piecewise function is partially computable?

I know exactly what a partially computable function is, but I've seen a few functions that I really can not understand why they are not partially computable. As an example in Davis book page 78, he ...
2
votes
1answer
66 views

What is a student process?

According to Galvin and Silberschatz, 5 queues are maintained in multilevel queue scheduling, each for: System Process Interactive Process Interactive Editing Process Batch process Student ...
4
votes
2answers
32 views

Are class methods closures?

In the wiki article about closures one can read: closure ... is a function or reference to a function together with a referencing environment At the same time in the wiki article about class ...
2
votes
1answer
134 views

What is the name for this search algorithm?

A colleague came up with the following search algorithm: We have an array of sorted, distinct integers [$i_0$ < $i_2$ < ... < $i_n$] We are looking for the index of $i_k$ (for simplicity ...
-1
votes
1answer
30 views

What is the exact definition of a dictionary in the concept of linear algebra and computer science?

I am reading this paper for my master thesis and trying to understand every concept in it. The following sentence confuses me as to what is the exact definition of a dictionary in this concept except ...
11
votes
6answers
3k views

How can I academically say that 'one computer is slower than the other'?

I'm writing a research paper and I have to basically say that one microcontroller is slower than an other microprocessor. However, I'm worried that simply saying that it's 'slower' wouldn't be ...
4
votes
1answer
62 views

What is the difference between assignment, valuation and name binding?

I read that Name binding assigns some value (data/code/expression) to an identifier. Assignment and valuation seem to do the same thing. It is confusing. Can I just tell that free variable is one, ...
1
vote
4answers
68 views

What do we call a function that outputs 0 on half and 1 on the other half of all inputs?

I have a Boolean function that outputs a one on half of its inputs and outputs a zero on half of its inputs, the inputs are assumed to be coming from the uniform distribution. Another way of saying ...
1
vote
6answers
216 views

Computer Program vs. Algorithm

It's said that a program include algorithms, however if we refer to their definition, an algorithm is a sequence of instructions written to perform a specified task and a computer program is also a ...
4
votes
2answers
1k views

What is 'halting'?

I've read a definition that says that "co-semi-decideable' means that a TM is halting on all inputs NOT in the language. I've heard the word come up a lot, and I've so far assumed that halting just ...
0
votes
2answers
30 views

What is a compact model?

I am a domain scientist and I study biophysical systems. When I asked a colleague in CS for suggestions about how to design a multi-scale simulator, he mentioned the term "compact model". Now, I ...
3
votes
1answer
42 views

When was the terminology *tracing collector* introduced to denote both mark-and-sweep and copy collectors

Automatic storage reclamation, aka garbage collection, comes in two main families, sometimes cooperating: the reference count collectors and the tracing collectors. I may develop specifics of each ...
4
votes
4answers
198 views

What is determinism in computer science?

I was asked if my computer program (in Java) was deterministic. I'm wondering how could it be not? There is no such thing as a non-deterministic Java program right? Even if I use a random number ...
2
votes
1answer
30 views

What is considered arithmetic when dealing with bits?

In a recent homework question we were asked to implement a program that would use only bitwise operations. From our notes, this includes & | ^ ~ >> << and >>>. We are not allowed to use ...
0
votes
1answer
56 views

Running time of partial algorithms

What is the correct term for the maximal running time of a given algorithm on all inputs of length bounded by given $n$, on which the algorithm halts? Assume, if necessary, that the halting problem ...
4
votes
1answer
79 views

Term for a matching which is perfect on one side only

What is a standard term for a matching in a bipartite graph, in which one part has less vertices than the other part, and the part with less vertices is fully matched (but the other part is, ...
1
vote
1answer
24 views

What does it mean for a function $f\colon M → N$ between *any* sets $M, N$ to be computable?

In our lecture notes on lamdba calculus, I encountered the sentence: Let $M$ be a set and $f\colon ℕ → M$ be computable. Does this even make sense? Don’t we need aditional structure on $ℕ$ and ...
0
votes
1answer
64 views

What is “potential speedup” in parallel computing?

There is an example problem from p506 of Computer Organization and Design, Fifth Edition: The Hardware/Software interface by David A. Patterson, John L. Hennessy I wonder how "potential speedup" ...
8
votes
0answers
92 views

Who coined the term “machine learning”?

I'm trying to figure out who coined the term "machine learning". An ancillary question is from where is Arthur Samuel cited as defining the field of "machine learning" in 1959 as: the field of ...
0
votes
2answers
69 views

Difference between Turing machine end state and halt

Is there a difference between the end state of a Turing machine and the halt state? Especially, for example the Busy Beaver 3. It is said that it is with 3 states but there is also a halt. Is the end ...
0
votes
1answer
32 views

Clock skew vs clock offset in the context of clock synchronization network protocols

In the context of clock synchronization among nodes of a network, what is clock offset and what is clock skew? Are these terms synonymous or is there a difference between them?
4
votes
1answer
168 views

What's the meaning of the name P/poly?

I understand the normal definitions of the P/poly class, but I'm curious how the name came about. The syntax of the name looks like a quotient group, but I can't think of any way to define P/poly ...
3
votes
0answers
84 views

Who coined the term “artificial intelligence”?

The most obvious (and commonly given) answer to this question is John McCarthy, but I have traced the first usage of this term to a 1955 paper, which McCarthy co-authored with Marvin Minsky, Nathaniel ...
3
votes
1answer
66 views

Is a Karp-Levin reduction a Levin reduction?

My understanding is that Karp many-one reductions are more general than Levin many-one reductions, and that Levin many-one reductions must allow for the number of certificates for a problem $A$ ...
1
vote
0answers
18 views

How to find the accuracy of a set partitioning?

Suppose that there are $k$ sets $S_1, S_2, S_3, \dots, S_k$. The numbers $N = \{1, 2, \dots,n\}$ are distributed into these sets equally. Say that we partition $N$ into $m$ sets $P_1, P_2, \dots, ...
3
votes
1answer
64 views

Partial order, total order, and version order in transaction histories

In Section 3.1.2 "Transaction Histories" of the PhD thesis by Atul Adya [1]: A history $H$ over a set of transactions consists of two parts: (1) a partial order of events $E$ that reflects the ...
8
votes
2answers
167 views

What is the difference between variables and pointers?

Whist reading an article outlining differences in OO and Functional programming I came across function pointers. It has been a while since I completed my Computer Science degree (2003) and so I looked ...
0
votes
1answer
30 views

Concise way to say “increases with n or some term of n”

I'm writing a thesis proposal and one of the systems involved has unknown complexity. It's not a focus of the proposal, but I wanted to include a line like this, as speculation: Presumably the ...
7
votes
1answer
276 views

What is it called when two problems are similar?

Suppose that there are two problems $P$ and $Q$. How can I say that "solving $P$ is same thing with solving $Q$"? For instance, if $P$ is NP-Hard, then we can say "$P$ can be solved in polynomial ...
3
votes
2answers
46 views

Definition of a size of type

In B. Pierce's book "Types and Programming Languages", he talks about the size of types (see pictures below). I searched the book for a definition but could not find one. I only found a definition ...
3
votes
1answer
56 views

What is With High Probability on Probabilistic Algorithms?

I watched lecture from MIT about Skip List. Overall, I understand the material, but one thing. What is "with-high-probability"? I really don't get it at all. I've seen the lecture notes but still ...
2
votes
2answers
49 views

Difference between edges in Depth First Trees

I have a directed graph, where each node has an alphabetical value. The graph is to be traversed with topological DFS by descending alphabetical values (Z-A). The result is $M,N,P,O,Q,S,R,T$ (after ...
1
vote
2answers
174 views

Difference between spanning tree and a tree?

Strictly in the context of computer science, what is the difference between a spanning tree, and minimum spanning tree? I read this posts but was unsatisfied with the answer because it did not seem ...
0
votes
2answers
65 views

Why is And-Or-Graph-Search called a search algorithm?

An algorithm in Artificial Intelligence: A Modern Approach for planning in stochastic, fully observable environments is called And-Or-Graph-Search, implying that it's a search algorithm. However, I ...