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

learn more… | top users | synonyms

0
votes
0answers
41 views

Why is it that no one can explain polymorphism? Should it be renamed? [on hold]

This is one of the simplest interview questions, in theory. However when people are pressed to explain polymorphism, or even worse its various subcategories (inclusion, adhoc, parametric), they tend ...
1
vote
1answer
17 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
19 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
21 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
39 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
43 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
45 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 ...
0
votes
1answer
26 views

What is a student process?

In multilevel queue scheduling, 5 queues are maintained, each for: System Process Interactive Process Interactive Editing Process Batch process Student Process What are student process? Also, ...
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
109 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
27 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
2k 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
53 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
61 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
190 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
187 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
0answers
36 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
62 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
82 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
1answer
41 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
29 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
167 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
83 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
64 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
17 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
59 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 ...
7
votes
2answers
164 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
29 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
275 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
45 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
48 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
45 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
172 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
55 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 ...
6
votes
2answers
216 views

algorithm time analysis “input size” vs “input elements”

I'm still a bit confused with the terms "input length" and "input size" when used to analyze and describe the asymptomatic upper bound for an algorithm Seems that input length for the algorithm ...
3
votes
1answer
206 views

What is a naive method?

I was researching dynamic programming and read the following: Often when using a more naive method, many of the subproblems are generated and solved many times. What is a naive method?
1
vote
2answers
178 views

What's the definition of a (deterministic) formal language?

Definitions According to my UML teacher formal means strictly according to rules, officially and how it's supposed to be. He says a formal language = syntax + symbols + spelling. Another term he uses ...
3
votes
1answer
35 views

Can someone explain in a simple way what “reducible” mean in complexity theory? [duplicate]

I find the word "reducible" used in complexity theory not very intuitive, and too general taken on a face value. What does it exactly mean by problem A reducible to B? Does it mean that A can be ...
2
votes
1answer
59 views

Is this time complexity quasi-polynomial?

I have been working in the time analysis for an algorithm and finally I got a curve that fits: $O(2^{(\log_2(N)^{2.01})})$ N is the number of elements. I'm right to say the above time complexity is ...
0
votes
1answer
34 views

The name for this genetic algorithm variant

What is the name for this variant of genetic algorithm. I'm sure I have read about this in Wikipedia, but now I could not find it: There in no thing as sequential population. The phenotypes lives and ...
1
vote
3answers
54 views

What is different between “Arithmetic Calculation” and “Calculation” in computer science?

What is different when you say "Arithmetic Calculation" and "Calculation" in the context of the computer science? The "arithmetic" in the former seems needless to me since all calculations are ...
2
votes
1answer
66 views

What is oblivious RAM and how does it work?

Could anybody explain me what exactly oblivious RAM is? I found the following explanation which makes it kind of clear to me, but I would like to get a sense of the technical aspects: Encryption ...
1
vote
1answer
35 views

What is alternative parenthesizations?

I'm a person using english as the second language and reading CLRS book at a slow pace due to my poor english. I have a problem with understanding the meaning of the word 'alternative'. In page 303 on ...
3
votes
1answer
577 views

What does the set {n | n is an integer and n = n + 1} represent?

I am reading Michael Sipser's book Introduction to the Theory of Computation, which mentions the set $$S = \{ n \mid \text{$n$ is an integer and $n = n + 1$}\}.$$ This doesn't make any sense to me. I ...