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

learn more… | top users | synonyms

0
votes
1answer
20 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
262 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
30 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 ...
0
votes
0answers
24 views

Can one write virus in Linux? [closed]

I heard that one can't write virus in Linux because Linux has so many distributions that none virus won't work in every Linux-based system. But does the definition of a virus needs to work in every ...
2
votes
1answer
27 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
161 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
42 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
139 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
194 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
115 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
28 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
49 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
29 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
48 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
40 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 ...
0
votes
1answer
24 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
552 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
27 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
60 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
50 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
12 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
340 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
49 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
62 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
59 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
69 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
42 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
26 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
97 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
72 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
59 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
24 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
63 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
258 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
44 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
40 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
68 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 ...
2
votes
3answers
133 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))$. ...
0
votes
2answers
34 views

Recursion: base case vs. small version

I'm reviewing the definition of recursion and in my notes are two questions about a recursive problem. One question asks about the base case, the other one about the small version of the problem, I ...
-2
votes
1answer
47 views

What does “schema” mean? [closed]

In a relational model, a schema is something which specifies the name and data type of each field. The word "schema" is also used in "conceptual schema", "physical schema" and "external schema". ...
0
votes
0answers
16 views

Classification of one-dimensional CA based on the number of inputs each cell receives during an update?

Consider Wolfram's rule 30 and Wolfram's rule 62. In the case of rule 30, only two bits of information must be passed to each new cell in the CA during an update, while for Wolfram's rule 62, three ...
2
votes
1answer
44 views

How to vocalize hexadecimal numbers?

When I want to vocalize a hexadecimal number like 0x41, so I say "forty one in hexadecimal", "four, one in hex" or what? Or do you always have to calculate and say "65 in hexadecimal notation"? I feel ...
2
votes
1answer
22 views

Terminology about the word Function : General vs Computable

I've seen two different concepts referred to by the term "function": A small part of a program specified by the composition of constants and other functions as paramaters, such as the "functions" in ...
1
vote
2answers
87 views

Computation is effectively computable in theory and in practice

My big question is the following: What is the meaning of a computation being "effectively computable" (EC) in theory and in practice? In trying to understand these concepts further, I have a couple ...
-2
votes
1answer
40 views

What is a forwarding pointer? [closed]

I heard this terminology used today and haven't come across it before, could someone please explain? Are there any other terms/names that describe this concept?
6
votes
1answer
65 views

Etymology of time and space “complexity”

The word choice of "complexity" in analysis of algorithms to describe temporal and spatial resource requirements has always struct me as an odd one. These are certainly useful and meaningful concepts. ...
2
votes
2answers
88 views

Algorithms which are both deterministic and non-deterministic

I'm just starting my second year in computer science and one of my classes briefly touched upon deterministic vs. non-deterministic algorithms. This got me thinking - is there any use for algorithms ...