Questions tagged [terminology]
Questions about how specific notions have to be understood as well as conventions of notation.
1,076
questions
0
votes
1answer
22 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
339 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
83 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 ...
1
vote
1answer
35 views
Linear ordering of all subsets of size k
I was wondering if there is an obvious way to 'name' the ${n \choose k}$ subsets of size $k$ of the integers from $1$ to $n$. So I am looking for a bijection from the subsets of $\{1,\ldots, n\}$ into ...
2
votes
1answer
110 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 ...
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.
10
votes
2answers
5k 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)$...
14
votes
4answers
14k 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
154 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 ...
5
votes
1answer
546 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
85 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 ...
1
vote
1answer
68 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
72 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 ...
6
votes
2answers
575 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
692 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.
4
votes
2answers
598 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 ...
1
vote
2answers
77 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
279 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
2answers
336 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 ...
2
votes
1answer
363 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 ...
2
votes
1answer
44 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
38 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 ...
7
votes
2answers
4k 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
108 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
1answer
65 views
What is $C_4$ + two "ears" called?
A graph with $C_3$ + 3 "ears" is called a net graph.
In general, $C_n$ + $n$ pendant vertices are called sunlet graphs.
Is there a name for 4-sunlet graph minus two pendant vertices?
3
votes
3answers
4k 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
265 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
46 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
25 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
173 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
676 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,...
1
vote
1answer
291 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
111 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
33 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
27 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
2answers
763 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 ...
3
votes
1answer
1k 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 ...
1
vote
1answer
415 views
Bisimilarity and Trace Equivalence in Labelled Transition Systems
I'm a bit confused regarding the relation between trace equivalence and bisimilarity. These lecture notes I found and a few others documents I've read state that "if an LTS is deterministic then two ...
1
vote
2answers
101 views
Definition of InLeft and InRight
So in reading I have come across the terms "InLeft" and "InRight" and I am unable to find a concrete definition for it.
I have found it used in the specification for COQ, and in some notes on ...
4
votes
1answer
394 views
What is the name for a function's "return arity"?
The number of parameters a function has (and thus the number of arguments it can take) is known as arity. What is the name for the number of values a function returns? I'm not asking for the "size" of ...
1
vote
2answers
72 views
What mathematical terminology exists for "embellished trees"?
I'm looking for some pointers on proper mathematical (FP?, category-theory?) terminology.
My apologies if the below is somewhat imprecise; I suppose the precision is precisely what I'm looking for in ...
2
votes
0answers
1k views
Latency and Throughput Bounds
Say that I have a superscalar processor and I am given the latency, issue and capacity (in clock cycles) for different instructions.
What is the general formula for latency bound and throughput bound?...
6
votes
3answers
821 views
Why is the set for which a decision problem is true called a "language"?
When we have a decision problem, " does $f(x)=1$ hold?", we call the set of strings $x$ for which the answer is yes a "language".
Why this strange terminology?
1
vote
0answers
353 views
What's elementary operation in Computer science?
What do Computer Science mean when they use the Term Elementary Operations?
1
vote
0answers
25 views
Is there a term for mixing deferred and eager evaluation?
I've written a model which utilises deferred evaluation for many aspects of its feature but in one instance of its use it is mixed with threaded eager evaluation for things that are expected to be ...
1
vote
2answers
103 views
What is the name for the comparison used in C's memcmp?
The C memcmp function (and strcmp) does a comparison similar to the function below for comparing integers:
...
6
votes
1answer
716 views
What does the "big O complexity" of a function mean?
What do people mean when they refer to the "big O complexity" of a function? What is the big O complexity of $9n^2 + 10n$, for example?
2
votes
1answer
73 views
What do we call a greedy algorithm that tracks the best $n > 1$ solutions?
A naive greedy algorithm tries to find an optimal solution based on the best solution so far, hence it may get stuck in local optima.
To avoid this problem, we may keep track of the best $n > 1$ ...
13
votes
5answers
3k views
Why does soundness imply consistency?
I was reading the question Consistency and completeness imply soundness? and the first statement in it says:
I understand that soundness implies consistency.
Which I was quite puzzled about ...
