Questions tagged [terminology]
Questions about how specific notions have to be understood as well as conventions of notation.
0
votes
0answers
24 views
Is this use of “edge orientation” terminology correct?
In my thesis I am about to define, what I mean by "weak asymmetry".
"When the difference between an edge's two orientations are no more than 1 minute."
May I express it as such, or is that misuse ...
1
vote
1answer
27 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
15 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
56 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
28 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
91 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
88 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
35 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
69 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
1answer
19 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
29 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
49 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
57 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
377 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
101 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
65 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
16 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
80 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
70 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
33 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 ...
4
votes
1answer
652 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
48 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
291 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
150 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
31 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
50 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
70 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
43 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
63 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
104 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 $\...
1
vote
1answer
43 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 ...
0
votes
2answers
43 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 ...
3
votes
1answer
198 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
62 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 ...
0
votes
0answers
46 views
What are transitive roles in description logic?
I've begun to study Description Logic recently and there are a huge number of new terms to me. One of these terms is transitive role. I found this term in slide 7 and my question is: what is ...
1
vote
0answers
153 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
769 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?
0
votes
0answers
77 views
What's elementary operation in Computer science?
What do Computer Science mean when they use the Term Elementary Operations?
1
vote
0answers
20 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
69 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:
...
