Questions tagged [terminology]
Questions about how specific notions have to be understood as well as conventions of notation.
985
questions
1
vote
1answer
10 views
Hardness of approximation statement clarification?
In the paper I'm reading, there is a hardness of approximation result for an algorithm proved using a reduction to set cover. Roughly, the claim states that if there existed an algorithm that solved ...
1
vote
2answers
18 views
Algorithm for producing array of objects according to the given distribution
I have a set of objects, and each object has (let's say) a color. Given a distribution such as:
...
2
votes
0answers
25 views
Does the Hack computer from “The Elements of Computing Systems” use Von Neumann architecture?
I'm reading "The Elements of Computing Systems" (subtitled "Building a Modern Computer from First Principles - Nand to Tetris Companion) by Noam Nisan and Shimon Schocken.
Chapter 4 is about machine ...
3
votes
2answers
81 views
What is the name of the operator that translates from $X\rightarrow(Y\rightarrow Z)$ to $Y\rightarrow(X\rightarrow Z)$?
Is there a standard name for the operator that takes a function $f:X\rightarrow(Y\rightarrow Z)$ and returns the function $f':Y\rightarrow(X\rightarrow Z)$ that satisfies, for every $y \in Y$ and $x \...
2
votes
1answer
34 views
Terminology: Difference between decision variables, features and attributes?
Could there be a difference between the words "feature", "attribute", and "decision variable" when used in the same paper? The one I am specifically thinking about is about an optimization method for ...
0
votes
0answers
10 views
How to detect a consensus is BFT or not?
Can we divide consensus algorithms into BFT (Byzantine Fault
Tolerant) and non-BFT ?
If so, How to detect a consensus is BFT or non-BFT ?
Is there any non-BFT consensus algorithm example ?
4
votes
1answer
71 views
Term for a graph decomposition based on a maximum matching
Let $M$ be a maximum cardinality matching in a bipartite graph $G(X+Y,E)$. Let $X_0$ be the subset of $X$ unmatched by $M$. Define the following sequence:
$Y_1 = $ the neighbors of $X_0$ using edges ...
0
votes
1answer
123 views
What does it mean for a TM to solve a problem?
When we say a TM solves a problem, what does this mean?
1
vote
1answer
47 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
50 views
What does exactly theoretical computer science entail? [closed]
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
13 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
24 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
28 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
34 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
83 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
69 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
28 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
31 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
21 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
121 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
39 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
560 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
69 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
31 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
27 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
118 views
1
vote
1answer
37 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
79 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
42 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
97 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,...
1
vote
2answers
331 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
104 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
43 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 ...
