The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [terminology]

Questions about how specific notions have to be understood as well as conventions of notation.

Filter by
Sorted by
Tagged with
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

Aggregate text data of some particular column

I have a dataset as follows ...
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

Is this algorithm bubble sort or selection sort?

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