Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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: ...