Questions tagged [terminology]
Questions about how specific notions have to be understood as well as conventions of notation.
1
vote
1answer
43 views
Confusion with first condition of Chomsky Normal Form
I had a very quick question when it comes to CFG (more specifically the attributes of CNF). I've been browsing over some examples and I've come across a few that confuse me. One such example is this:
...
0
votes
2answers
45 views
What does exactly theoretical computer science entail? [on hold]
I am confused by the term "theoretical computer science". How can I distinguish which part of computer science are considered "theoretical" and which not?
To expand further, take Machine Learning. Is ...
0
votes
0answers
9 views
How translation, transcription and annotation are related?
From a linguistic point of view, translation, transcription and annotation are three specific terms that introduce some (different) meanings.
However, when it comes to the application, it seems that ...
1
vote
1answer
21 views
How to put elements in allowed bags?
Let's say I have a list of "Items"
I also have a list of "Bags". Each bag is a set of "Items" which gives what item can be placed in that bag. But only one item can go in each bag.
I want to place ...
1
vote
1answer
25 views
What is the specific name for basic data types?
What is the specific name for data types such as integer, string, real (the basic ones)?
1
vote
2answers
33 views
What does “bounded above” mean in Family of Bachmann–Landau notations?
Per wiki
|f| is bounded above by g (up to constant factor) asymptotically
with this concrete example,
$$f(n) = \log n$$
$$g(n) = n^c = n^{0.000001}$$
Does "bounded above (up to constant factor)...
2
votes
2answers
1k views
Are “of the order of n” and “Big O” the same thing?
I am learning from the MIT course Introduction to Algorithms.
The professor says:
Now, remember $\Theta(n)$ is essentially something
that says "of the order of $n$".
What does "of the order ...
1
vote
1answer
53 views
If an array is full of the same integer, like 0s or 1s, are they all the peak of the array?
I am learning the MIT course Introduction to Algorithms.
The professor is saying
In particular, as an example, position 2 is a peak if, and only if, b
greater than or equal to a, and b greater ...
1
vote
3answers
82 views
What should I call algorithms with non-linear non-constant time?
I am writing a paper in which I want to refer to a group of algorithms. Some of these algorithms are of complexity O(NlogN), and some of the are more complex (e.g ...
1
vote
1answer
67 views
Name for value which may only be -1, 0 or 1?
Is there a name for a value which may only be -1, 0 or 1?
Is there a name for a function which creates such a value from arbitrary numbers?
It would be implemented like this:
T Function( T value ) {...
1
vote
0answers
12 views
What is tag-only forced cache inclusion called?
Is there a commonly accepted term for caches that are guaranteed inclusive with respect to tags but not data?
Inclusion can be helpful to simplify cache coherence, for which use only tags need to be ...
1
vote
0answers
49 views
What is this weird gate?
This came from a picture of something that I'm supposed to make, and I can't find it in the program I'm supposed to use (LogicWorks). It looks like it 'not's only one of its inputs, but that doesn't ...
0
votes
1answer
31 views
13
votes
2answers
5k views
What is a 'Key' in computer science?
I'm a bit confused on what exactly the meaning of a 'key' is in computer science. I understand key-value pairs, primary keys, etc... But I can't find a definition of what the term 'key' means by ...
2
votes
2answers
60 views
Operator name in LL(1) computation
I'm working from a definition of the LL(1) property of context-free languages in order to build a LL(1)-computer, i.e., a program capable of determining whether a given context-free language is in LL(...
1
vote
1answer
27 views
What is the equivalent of the integers symbol Z for n bit only integers?
We refer to the set of all integers as $\mathbb{Z}$. Now suppose we have a set of integers that can be held within a computer variable of $n$ bits width. Clearly they can only be of $2^{n}$ range, ...
1
vote
1answer
26 views
Vertex Cover without covering all edges
What would be the name of the problem of a vertex cover that covers all the vertices without the requirement of covering all the edges?
Vertex cover has to answer whether or not there is a set of $k$ ...
1
vote
1answer
19 views
Name for multiset with fractional amounts?
What do you call a set which accepts multiples of the same element, even in fractional amount? Is there even an established for this?
Example from a video game about production chains:
For a ...
1
vote
0answers
18 views
A term for a set of vertices with a small set of neighbors
Given a graph $G(V,E)$ ans a subset $S\subseteq V$, define $N(S) = $ the set of neighbors of $S$.
Is there a standard term for a subset $S\subseteq V$ for which $|N(S)|\leq |S|$? Is there a standard ...
3
votes
3answers
78 views
Difference between RAM and buffer
I have searched but didn't get any exact difference between RAM and a buffer. If both are used for temporary storage, then why they are named differently while both having same property?
1
vote
1answer
12 views
Software metric for data growth
I'm writing a paper for some software that uses combinatorics to generate large result sets. I would like to describe that if I put in $n$ elements, I will get in return $2^n$ elements.
Is there a ...
-1
votes
1answer
37 views
Term for the use of the same programming language in every tier?
What is the technical term that describes the use of the same programming language in every tier in the architecture of a system? For example, having JavaScript in model, view and controller.
edit #1:...
0
votes
1answer
17 views
Term for an A*-like pathfinding strategy where only the heuristic goal distance matters
I am trying to find a proper term for the A*-like best-first pathfinding strategy where the node to expand next is the one with the least estimated distance from the goal, regardless of its distance ...
1
vote
2answers
42 views
Term for the tree of all paths starting from a given vertex in a graph
What is the term for the tree (or a part of the tree) of all possible paths in a graph that start from a given (source) vertex?
This is the tree that is implicitly or explicitly constructed when ...
5
votes
2answers
559 views
Do I need to consider instance restrictions when showing a language is in P?
I have already shown that 3-colorable for an unrestricted graph is in NP, but I was thinking about the similar language defined as the set of all acyclic $G$, where $G$ such that $G$ is 3-colorable. ...
2
votes
1answer
24 views
Name of double sided search algorithms
I modeled the function double_sided_breadth_first_search after the ideas in "improving Dijkstra" in Cormen et al, and the OCW course on algorithms. Note that I expand the smaller boundary, in an ...
2
votes
3answers
68 views
NP-hard in what parameter?
I often read statements such as "the run-time of algorithm X is polynomial in m and n". Indeed, when a problem has two parameters, it is possible that the run-time of an algorithm is polynomial in one ...
1
vote
0answers
30 views
What do we mean by “spectral domain” in the context of graphs?
What do we mean by the spectral domain in the context of graphs? For example, I have heard that graph convolutions are easiest to define in the spectral domain. When it comes to the word "spectral", I ...
1
vote
1answer
24 views
Set of DAG vertices disconnecting a vertex from forbidden vertices
Let $v$ be a vertex with in-degree 0 in an (acyclic) DAG $G$, and let $F$ be a subset of $G$'s vertices (the "forbidden") vertices. Now suppose $U$ is a set of vertices such that every path from $v$ ...
1
vote
2answers
117 views
1
vote
1answer
35 views
Turing Machine where branches are resolved via arbitrary operator
Alternating Turing Machines output Boolean values and combine the values returned by branches via the any/all operators. Is ...
2
votes
1answer
43 views
Terminology First-Order Logic
A graph $G$ is said to be a model of a first-order sentence $\varphi$ if $G$ satisfies $\varphi$. Now let $\varphi(x_1,...,x_r)$ be a first order formula with free variables $x_1,...,x_r$. What is ...
2
votes
0answers
17 views
Is there a more commonly-used term for “multi-pivoting”?
Consider the following computational problem (or rather, task):
Given:
An array of $A$ of (not necessarily distinct) elements from a fully-ordered finite domain
An ordered sequence pivot ...
2
votes
1answer
62 views
Appreciation of the 5 state process model
I'm starting out in an Operating Systems module. I have a few understanding questions to think about, which will not be gone through in class.
A process state model is an abstraction (or model) which ...
2
votes
1answer
39 views
Name of a tree with arbitrary number of branches at each fork point?
A binary tree is a rooted tree with the root having an indegree of 0 and all other nodes of 1. The outdegree is 0, 1 or 2 for all nodes.
How do you call a rooted tree if the number of branches per ...
1
vote
1answer
82 views
Which AC-3 algorithm is being used here?
This is the illustration of the AC-3 algorithm for four queens from exhaustive study of essential constraint satisfaction problem techniques based on N-Queens problem by Md. Ahsan Ayub, Kazi A Kalpoma,...
2
votes
2answers
308 views
Is there a name for this priority queue data structure?
While watching a sports tournament, I noticed that the tournament tree looks a lot like a heap. I came up with the following data structure: A complete binary tree where the leaves are elements of ...
1
vote
2answers
91 views
Relation between semi decidable, undecidable and countable sets
I know that
decidable problem: has both counting (bijection with $\mathbb N $) and membership algorithm (TM halts for both member and non member strings )
semidecidable problem: has counting ...
2
votes
2answers
42 views
What is the term for two file formats that describe the same amount of information?
I am working on file formats conversion. Some of them can be converted back and forth to others without losing any information (fields or precision of the numbers encoded), others file format do not ...
3
votes
3answers
355 views
What is the Name of the Problem or Technique of Determining if a Line in a Program Will Execute
If I were to pose the question: "Given a program $P$ containing statement $X$, will $X$ be executed (given enough runs with all possible inputs)?"
This strikes me of being a relative of the Halting ...
15
votes
2answers
2k views
What is this data structure/concept where a plot of points defines a partition to a space
I encountered an algorithm to solve a real world problem, and I remember a class I took where I made something very similar for some for a homework problem.
Basically it's a plot of points, and the ...
0
votes
2answers
41 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 ...
2
votes
2answers
107 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 ...
3
votes
0answers
20 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
20 views
Curiosity on system device nomenclature - Gaussian Mixture Models [closed]
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
41 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
26 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
42 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
...
1
vote
0answers
79 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) \...
