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

learn more… | top users | synonyms

0
votes
0answers
13 views

What is the appropriate name for a data structure of nested objects?

I have the following data structure, based on JSON notation, it is basically an object with nested objects and arrays.. I would like to know: If this object structure in computer science has a ...
7
votes
0answers
59 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
19 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
152 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
75 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 ...
0
votes
0answers
11 views

Are these abbreviations common in programming/image processing? [migrated]

I am editing terms that will be used on an user interface of the controller of a vision sensor designed for factory use. Since there is a restriction of space on the UI, I am trying to abbreviate ...
3
votes
1answer
59 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
15 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
45 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
161 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
41 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 ...
2
votes
1answer
42 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
40 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
167 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
48 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 ...
5
votes
2answers
164 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
203 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
141 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
32 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
52 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
32 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
49 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
43 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
34 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
565 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 ...
2
votes
0answers
30 views

Understanding a paper on polynomial recursion in all finite types

So I wasn't sure weather or not this counted as "research level" or not but I figured it wasn't so I decided to post it here. There is a paper by S. Bellantoni et al. called "Higher Type Recursion, ...
3
votes
0answers
62 views

Does any one know what this problem is called?

We are given finite sets $A$ and $B$ and a set $S\subseteq \mathcal{P}(A)$. The members of $\mathcal{S}$ may have arbitrary intersections with one another and their union is not necessarily $A$. ...
0
votes
1answer
53 views

Is there a name for the 'scope tree' organization?

I could describe JQuery as a library that allows you to easily select elements on and traverse the DOM, the DOM would be the name of the tree or organizational structure of the HTML. When you are ...
1
vote
0answers
13 views

Terminology for a partially unlinked doubly linked list?

Let's say you have a standard doubly link list implementation: struct List { int Number; struct List *blink; struct List *flink; }; and that you have ...
5
votes
1answer
358 views

What is the formal name for this algorithmic problem?

I'm doing some work on a problem and I'm finding it difficult to research it with out the actual name of the problem, since the problem I'm working on gives it it's own abstraction. The problem is ...
0
votes
0answers
19 views

What is the correct term for “time to establish a connection”

I don't remember what is the term for "time to establish a connection". For example in a smartphone, when I lost the wifi signal and the phone try to get mobile data connection it spends a bit of ...
3
votes
1answer
57 views

Where does the terminology of open addressing resp. closed hashing come from?

One of the basic methods of hashing is called "Open addressing, or closed hashing" according to wikipadia (and several books). Why the names "open" and "closed", and why these seemingly contradictory ...
2
votes
2answers
67 views

Understanding constraint formula concept in Java

JLS defined a concept called "constraint formula". There is a formal definition: Constraint formulas are assertions of compatibility or subtyping that may involve inference variables. The ...
2
votes
2answers
62 views

How is the number of states in a Turing machine bounded?

The definition of Turing machine says that the number of states is finite. However, I do not get how this can be true. Is the number of states in a Turing machine actually not fixed, that is not ...
0
votes
2answers
70 views

What is the definition of a problem

In computation theory, when talking about the computability and complexity of a problem, what is the definition of a problem? How specific should a problem be? For example, can the followings all ...
1
vote
2answers
48 views

What is the set of operations of a Turing machine?

From https://en.wikipedia.org/wiki/Abstract_machine A typical abstract machine consists of a definition in terms of input, output, and the set of allowable operations used to turn the former ...
1
vote
1answer
27 views

Difference between a lambda term and a lambda expression

Is there any difference between a $\lambda$-term and a $\lambda$-expression? Looking at the recursive definitions on Wikipedia of $\lambda$-term and $\lambda$-expression, they are equivalent. But I ...
2
votes
2answers
106 views

Is it possible to obtain a total function by composition of partial functions?

This statement is Theorem 1.1 (page 39) of Computability, Complexity and languages by Martin Davis: If function $h$ is obtained from the (partially) computable functions $f$, $g_1$, $g_2$, ..., ...
2
votes
2answers
83 views

Is there a difference between perfect, full and complete tree?

Is there a difference between perfect, full and complete tree? Or are these the same words to describe the same situation?
4
votes
3answers
74 views

Is the height of the tree the number of edges or number of nodes?

I'm so confused by some of the theorems online about tree heights. Does tree height mean the number of edges or nodes? if nodes, does it include the node it is counting from? Can the height of a tree ...
4
votes
3answers
60 views

When problem A reduces to problem B, which problem is more complex?

When discussing complexity classes, when we say that problem $A$ reduces to problem $B$, are we saying that problem $A$ is at least as complex as problem $B$, or the other way around?
0
votes
0answers
27 views

Difference between parallel and concurrent buffering?

In double buffering there are two terms Concurrent buffering. Parallel buffering. What is the difference between them, answer with example will be appreciated.
0
votes
1answer
68 views

What is the difference between shortest distance and shortest path?

I am studying graph currently. I found a question, which asks for The List A[] which shows shortest distances between $V$ and every other vertex The List ...
3
votes
1answer
270 views

What is a partially computable function?

In the book Computability, Complexity, and Languages, Martin Davis writes in chapter two: A partial function is said to be partially computable if it is computed by some program. and also ...
-1
votes
1answer
47 views

What are activation records?

What are the open activation records of a recursive algorithm ? Edit: Activation records are the number of times that we call a function that is not finished yet. Correct? So we can find the number ...
-1
votes
1answer
43 views

Triangles incident on a vertex (Graphs)

I have a project that I am doing. The specification requires specific methods on a graph class. Two of the methods requires this: ...
2
votes
2answers
72 views

Terminologies of “Process calculus” and “Process algebra” [duplicate]

In the literature, the terms of "process calculus" and "process algebra" are often interchangeable. Meanwhile, it confused me. My questions are: Are there formal, standard, and ...
3
votes
3answers
148 views

What do f(x) and g(x) represent in Big O notation?

I have been reading about Big O notation. People writing about Big O often use the terms $f(x)$ and $g(x)$. For instance, I often see people write things like $f(x) = O(g(x))$ or $f(x) \in O(g(x))$. ...