Questions tagged [terminology]

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

Filter by
Sorted by
Tagged with
5
votes
2answers
570 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
33 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
130 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
36 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
40 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
134 views

Is this algorithm bubble sort or selection sort?

...
1
vote
1answer
42 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
46 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
18 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
960 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
111 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
484 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
428 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
432 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
48 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
363 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 ...
16
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
65 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
114 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
26 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')$ ...
1
vote
1answer
31 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
56 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
32 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
47 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
137 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) \...
4
votes
5answers
78 views

Terminology for reducing runtime of an algorithm by using a property of the problem?

It is a very standard situation that we have a class of problems $P$, and a subclass $\tilde P\subset P$ which has a certain restricted property. For example, $P$ could be the problem of searching ...
0
votes
1answer
22 views

Keywords/terminology for using “extra” information in search problems?

I am trying to find references on a particular idea, but I don't know which keywords to use in a google search. the idea is: as an example, consider graph search. maybe the problem is: find a path ...
1
vote
1answer
202 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
78 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 ...
1
vote
1answer
35 views

Linear ordering of all subsets of size k

I was wondering if there is an obvious way to 'name' the ${n \choose k}$ subsets of size $k$ of the integers from $1$ to $n$. So I am looking for a bijection from the subsets of $\{1,\ldots, n\}$ into ...
2
votes
1answer
97 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 ...
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.
8
votes
2answers
3k 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)$...
11
votes
4answers
11k 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
118 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 ...
6
votes
1answer
414 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
2answers
76 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 ...
1
vote
1answer
66 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
68 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 ...
5
votes
2answers
511 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
606 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.
4
votes
2answers
394 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 ...
1
vote
2answers
73 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
269 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
2answers
281 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 ...
2
votes
1answer
217 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 ...
2
votes
1answer
38 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
35 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
36 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 ...

1 2
3
4 5
22