Questions tagged [terminology]
Questions about how specific notions have to be understood as well as conventions of notation.
995
questions
3
votes
1answer
46 views
Difference between ⫾ (U+2AFE) and ⫿ (U+2AFF) in the context of Dijkstra's Guarded Command Language?
Continuing https://tex.stackexchange.com/questions/435986/how-to-draw-the-box-of-dijkstras-guarded-command-language, what is the difference in the intended usage of ⫾ (Dijkstra choice, U+2AFE) and ⫿ (...
0
votes
0answers
15 views
Why did Wegman-Carter call their class of hash functions as universal on their seminal paper
Wegman-Carter on their seminal Universal classes of hash functions uses the term universal for their definition. They gave this definition as:
Let $H$ be a class of functions from $A$ to $B$. We ...
-1
votes
0answers
12 views
Is there a term to express the meaning of counterpart in the field of computer science?
Assume there are only 3 people A, B, C working for a company. In other words, the employees of the company consists of A, B and C. A, B and C are colleagues of each other, within this company.
...
1
vote
1answer
15 views
Distributed algorithm can be executed in a single process
Looking at a "Distributed" algorithm from a textbook on distributed algorithms (e.g. Building a spanning tree, Broadcast/Convergecast.) I found that one can implement it using Golang's concurrency ...
0
votes
2answers
31 views
Is there a concept called “white waveforms” in computer science?
It sounds like the lecturer is speaking
If you for example want to play a
music file, mp3 file, well you know, given
that you've taken a programming course
before, all right? How would you do ...
2
votes
2answers
50 views
Typesetting LTL in Unicode?
Unicode has an abundance of open circles, diamonds and boxes. Using these, we can typeset linear-time temporal logic formulas such as
$$
(\mathop{⬦}ψ)\ \,\land\ \,\mathop{⬦}(θ\ \mathsf{U}\ \mathop{◻}\...
1
vote
2answers
53 views
What does “prime” mean in this context?
In a lecture video the instructor introduced the quadratic probing method for hash tables. The formula he gave was the following:
$h(k,i) = (h'(k) + c_1 + c_2i^2)$ $\% M$
where $h'$ was h "prime". ...
0
votes
0answers
27 views
Is it still called “recursion” when you're using call-stack as a stack?
The most obvious way to solve a problem of balancing parentheses, like https://leetcode.com/problems/valid-parentheses/, is through a stack (a last-in-first-out (LIFO) datastructure).
However, if you ...
0
votes
0answers
30 views
General term for upcasting and downcasting?
Is there a more precise term than simply "casting"? "Casting" often includes for example integer -> float or ...
0
votes
1answer
31 views
Least Significant Bit (LSB) vs Little Endian - Are they equivalent in anyway!
For a multiple choice question: What do we call the LSB?
(i)Little Endian (ii)Upper bit (iii)Big Endian (iv)Lower Bit
I feel ideally none of them is a true correct choice, but my best bet was (...
0
votes
0answers
25 views
What is difference between r, and r(R) in DBMS?
Sorry, for asking such a basic question.
I am really confused between small 'r' and 'r(R)' being interchangeably denoted as 'relation' or 'relational instance'. I know, that R is a relational schema. ...
1
vote
1answer
14 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
20 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
30 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
85 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
35 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
11 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
74 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
56 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
53 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
54 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
86 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
70 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
61 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
19 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
222 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
563 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
25 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
72 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
32 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
28 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
120 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 ...
