Questions tagged [terminology]
Questions about how specific notions have to be understood as well as conventions of notation.
0
votes
2answers
26 views
Terminology for worst-case N-complexity on $O(1)$ insert after amortisation
Normally, when discussing amortisation and worst-case complexity, amortisation negates the worst-case scenarios, and the BigO describes the average for the operation (the way it's used in interviews ...
1
vote
1answer
38 views
How broad is the meaning of “algorithm”?
This is a purely terminological question.
The word algorithm, as I have learnt it refers to something like an "effective method, a sequence of steps, for doing something". There are alternative ...
2
votes
0answers
17 views
Complementary of graph invariant
Graph invariant is a property that holds for two isomorphic graphs.
For example, degree sequence is graph invariant. We can write
$d(G) \ne d(G') \Rightarrow G \ncong G'$, although $d(G) = d(G')$ ...
0
votes
1answer
16 views
Curiosity on system device nomenclature - Gaussian Mixture Models
Would not know if this is the best SE website to ask, but I could not find anything better, especially because the answer might involve a fair amount of computer science (although this is an ...
2
votes
1answer
35 views
What, if any, is the term for a node whose children are all leaf nodes?
More specifically, I'm interested to know if there is a term that describes a tree node that meets two conditions:
- It has >= one child
- Any children that it has are all leaf nodes.
2
votes
1answer
23 views
How literally is “optimization” or “optimization algorithm” used in CS?
I have been confronted with two meanings of the term "optimization" or "optimization algorithm":
to find the absolute maximum in a set $X$ according to some criterion $f:X\to \mathbb R$
to find a "...
2
votes
1answer
36 views
What's the theoretical difference between class and type?
This question stems from my effort trying to learn ASN.1.
After I went through the PKCS#1 standard for RSA cryptosystem and X.680~X.683 side-by-side, I noticed that, they've defined
...
2
votes
0answers
31 views
Do SLR(1) parsers have lookahead?
The SLR(1) parses AFAIK does not have any lookahead with it then why do we write it as SLR(1) and not as SLR(0). The thing about parsers which I read online taught me that if it's LR(K) then K ...
1
vote
1answer
9 views
Is there a term for the distribution of numbers-of-digits of a bounded uniform distribution
Let $X$ be an integer sampled uniformly from the (integer) range $\{ 0...2^k - 1 \}$ .
Now, consider the distribution of
$\#\text{bits}(X) = \begin{cases} 1 & X = 0 \\\\ 1 + \lfloor \log_2(X) \...
1
vote
1answer
12 views
Terminology for reducing runtime of an algorithm by using a property of the problem?
It is a very standard situation that we have a class of problems $P$, and a subclass $\tilde P\subset P$ which has a certain restricted property.
For example, $P$ could be the problem of searching ...
0
votes
1answer
20 views
Keywords/terminology for using “extra” information in search problems?
I am trying to find references on a particular idea, but I don't know which keywords to use in a google search.
the idea is: as an example, consider graph search. maybe the problem is: find a path ...
1
vote
1answer
29 views
What is the meaning of max() in intro. to algorithms?
I'm reading chapter 3(growth functions) of CLRS and in giving an example of proving theta for a standard quadratic function the book gives the following value for $n_0 = 2 \cdot max(|b|/a, \sqrt{|c|/a}...
1
vote
1answer
18 views
AVL Rotations Abbreviations
I read that there are 4 types of rotations:
Left rotation
Right rotation
Left-Right rotation
Right-Left rotation
What are the corresponding abbreviations: RL,LR,RR,LL? Is there a reference how to ...
2
votes
1answer
58 views
Name for the tree formed after collapsing cycles
What do you call a structure which becomes a tree after collapsing cycles (so the new vertices are the old faces)?
For instance, the digraph (given by an NFA; ignore edge labels please) below becomes ...
0
votes
0answers
29 views
Define 'algorithm' [duplicate]
The dictionary definition of "algorithm" is so broad that it technically covers all computer programs:
...
1
vote
0answers
46 views
Is there a distinction between pointers and references? [closed]
If so, what are the similarities and differences between the two? I’ve only worked with properties while programming.
4
votes
2answers
107 views
Is “super-exponential” a precise definition of algorithmic complexity?
I cannot seem to find a precise definition of what "super-exponential" is supposed to refer to when one's talking about an algorithm's time complexity.
For instance, if an algorithm runs for $nC(n-1)$...
1
vote
3answers
104 views
Dynamic Programming vs Memoization
I am having trouble to understand dynamic programming. Mainly because of its name. As far as I understand, it's just another name of memoization or any tricks utilizing memoization.
Am I ...
1
vote
1answer
38 views
How hash-table and hash-map are different?
In the context of CS, how the hash-table and hash-map are different?
I was watching a part of "Algorithm with Swift" video in Udacity, and I discovered the terms "hash-table" and "hash-map" are ...
2
votes
1answer
71 views
Understanding the “ordering of the four types of edges” in DFS
The following is Exercise 22.3-6 from CLRS (Introduction to Algorithms, the 3rd edition; Page 611).
Show that in an undirected graph, classifying an edge $(u,v)$ as a tree edge or a back edge ...
0
votes
2answers
31 views
Tree with alternating types of nodes
Suppose that I have a tree where each node is either of type A or type B.
Nodes of type A ...
0
votes
0answers
30 views
Use of word “legal”
I've seen multiple things called legal in computer science (e.g. problems, solutions), and I've interpreted it as valid, meaningful or well-formed but what does it exactly mean and does it have a ...
1
vote
1answer
50 views
Are the definitions of recursively enumerate equivalent?
There are a couple of definitions of recursively enumerable, for example in Judah: $A \subset \mathbb{N}$ is called r.e. if there exist a $\Sigma^0_1$ formula $\varphi(x)$ such that
$$A:=\{n \in \...
1
vote
1answer
58 views
Is there any sort of formal definition of terms like 'data type', 'abstract data type', etc?
If not (because I assume not) is there some kind of reference or book that provides some theoretical foundation to these concepts? I've been learning about data structures and abstract data types for ...
3
votes
2answers
381 views
What makes a proof assistant a proof assistant?
You open a code editor, define a syntax with lambdas, a few primitives. Then you invent some nice computation rules, some cool typing rules, and write a corresponding interpreter and "type checker". ...
1
vote
2answers
126 views
Is every regular/context free langauge decidable in LogSpace?
I know all the regular languages are decidable but not sure whether it can be done in LogSpace.
3
votes
1answer
67 views
search problem vs optimization problem
This is mostly a terminological question: Is there a fundamental difference between "optimization problems" and "search problems"? Apologies if this is an obvious question
As I understand it, we can ...
0
votes
0answers
18 views
What is the history/logic behind RAID-5 layout naming?
RAID-5 layout names specify their "handedness" (ie. left/right) - which specifies how the parity blocks are arranged - and "symmetry" (ie. symmetric/asymmetric) - which specifies how the data blocks ...
1
vote
2answers
59 views
What kind of logarithm does $\log$ mean in Wikipedia articles?
Sorry if this seems like a dumb question, but what what type of logarithm is $\log$ in Wikipedia articles? Cheers.
3
votes
1answer
95 views
FPTAS definition
I read that a fully polynomial time approximation scheme (FPTAS) has time complexity polynomial in the input size and also polynomial in $1/\epsilon$. However, this leaves some ambiguity.
For example,...
3
votes
1answer
75 views
Why does everyone say that NFA guesses it's next state?
In the picture above e is an empty string, and a is a symbol from an alphabet. Every book or professor I have heard from, says than when we make transitions in the NFA, the NFA must guess which state ...
1
vote
0answers
25 views
Is “sparse subtree” an appropriate term for what I describe in this question?
Given a tree, with some nodes annotated, such that the annotations form another tree, I'm thinking "sparse subtree" is an appropriate term for describing the latter tree as it relates to the original ...
1
vote
1answer
25 views
Does data entropy depend on the arrangement of the characters in a file?
From what I understand data entropy controls the limit of data compression and it depends on the probability of the characters in the file. Assuming that we have a file of size 256 bytes containing ...
0
votes
0answers
35 views
Is “Clean Graph” a Thing?
My professor uses the term "clean graph" to mean that the nodes have no idea of the topology. Each node is aware of its ID, but has no idea about parents or edges and so on and it has to discover.
Is ...
0
votes
1answer
28 views
binary max and binary min [closed]
I'm reading a paper about constraint satisfaction problem and found a term "binary Max and binary Min" operations but I dont know the meaning. If someone know could you please explain for me? I ...
5
votes
1answer
726 views
Clique vs Complete Graph
Is there a difference between a complete graph and a clique topology? As far as I understand, both refer to graphs in which every possible edge between any two vertices is present. Is there a subtle ...
2
votes
1answer
49 views
Explicit algorithms and algorithms involving unknowns
Let's assume the you have two algorithms for computing some single but complicated number (e.g., the Ramsey number $R(5,5)$). Both are provided as high-level, half-formal textbook descriptions.
The ...
3
votes
3answers
363 views
Is there any difference between Time Complexity and Running time?
Is time complexity and running time of the program/algorithm one and the same thing?
Also, running time sounds like 'computer complexity'. As, it utilizes all the resources and give tangible time that ...
2
votes
1answer
152 views
Why is it called 'throwing' an exception?
I'm just wondering where the phrase "throwing" an exception came from. I understand "raising" an exception but I'm wondering if "throwing" has a reason or meaning behind it?
1
vote
2answers
32 views
How are lookup tables described from the perspective of complexity theory?
Lookup tables can convert a piece of computational time into space. I remember that it was a part of a complexity theory course, but I cannot recall how it's called in its terms. I know how to use ...
0
votes
0answers
11 views
What topics are related to “concept drift”?
The term "concept drift" specifically relates to a model changing over time. However, a similar phenomenon may manifest in, e.g., spatial data, where a topographical model changes behavior at a land/...
2
votes
0answers
52 views
Term for weak head normal forms that cannot be reduced in any environment
In my understanding, a lambda expression is a normal form (NF) when it has no redexes. For instance, $\lambda x.x$ is a NF, but $(\lambda x.x)y$ is not. A lambda expression is a weak head normal form (...
0
votes
0answers
81 views
What is the correct term for a probabilistically complete algorithm?
I'm wondering what the correct term for an algorithm that is probabilistically complete is. An algorithm is probabilistically complete if the probability of finding a solution, should a solution exist,...
0
votes
0answers
47 views
High Level Assemblers vs Compilers?
I'm reading the "Art of Assembly" 2nd Edition by Randall Hyde. In the book the author seems uses his own language called High Level Assembly (HLA). Coming from a C Background, I question how useful ...
2
votes
1answer
100 views
Do the classes $P$ and $NP$ include problems faster then polynomial?
I have being reading up on complexity classes (in Rieffel & Polak, 2011; pg149). I am slightly confused about something. Does for example $P$ (DTime($n^k$)) include all problems that can be solved ...
0
votes
1answer
28 views
A Question about what it means to Compare two Vectors
Please consider the following question:
Given an integer m by n matrix A and an integer m-vector b, the 0-1 integer programming problem asks whether there exists an integer n-vector x with elements in ...
0
votes
1answer
19 views
terminology: half adders, full adders
I'm very confused about the reasoning for these circuits being called 'full adders' and 'half adders'
I've read before that 'half adders' are called so, because two of them make up a 'full adder', ...
1
vote
1answer
70 views
Correct term for a priority queue with unique elements
Is there a standard term for a priority queue which can only hold a single occurrence of any element? This would be a priority queue for which operations such as "raise the priority of element ...
2
votes
1answer
117 views
What are the primal and dual planes in the context of the point-line duality?
In computational geometry, we can define a duality between points and lines. The line is the primal (or dual) object of a point, or a point is the primal (or dual) object of a line. However, the exact ...
0
votes
0answers
11 views
Modified digraphs, is there a term for this data structure?
Every transformation $t$ has as source ($\operatorname{Src}t$) a finite set of URLs and as destination ($\operatorname{Dst}t$) a finite set of URLs.
$t_1,\dots,t_n$ is a path of transformations if $\...
