Questions tagged [terminology]
Questions about how specific notions have to be understood as well as conventions of notation.
1,136
questions
1
vote
0
answers
30
views
Caching terminology
In docs sites, blogs, tools and on StackExchange, I often see various caching terms used interchangeably (though I suspect they differ).
Is there a theoretical difference between these terms:
...
- 111
2
votes
0
answers
30
views
What's the proper name for combinator λ x . λ y . x (x) = S(S(K(S))(K))(K)
What is the proper name for combinator
$$λ x . λ y . x (x) = S(S(K(S))(K))(K) \text { ?}$$ I call it dbl and I noticed that it's half a quine.
But I would like to ...
- 121
1
vote
3
answers
1k
views
Do programs within which a computable function runs a random number of times always halt, as in the halting problem?
I need some clarification regarding if computer scientists say a program like:
...
- 135
3
votes
1
answer
47
views
Naming Turing machines paired with input
Is there an established name for pairs $(\langle M \rangle, w)$ of a Turing machine $M$ (or description thereof) together with an input word $w$?
Such pairs often arise as elements of sets for ...
- 31
0
votes
5
answers
764
views
Classification of efficient and inefficient algorithms and the scientific reasoning behind them
I've been struggling with the commonly accepted notion in computer science that exponential algorithms are inefficient. The standard explanation is that they "grow exponentially in the size of ...
- 119
0
votes
0
answers
19
views
What is "broadcasting"?
Is "broadcasting" in the context of tensors, vectors, and matrices a mathematical term, or one only used in computer engineering? Who coined this term?
- 154
1
vote
1
answer
56
views
How to prove a function is a bijection (name mangling)?
I'm writing a compiler for a subset of Java, which does not permit overloading (but it does permit overriding). Static functions outside of main are not allowed.
We'...
- 183
0
votes
3
answers
66
views
Reference types
Is a reference type (agnostic of PL) the object being pointed at, or the object doing the pointing?
I'm having a hard time wrapping my head around the concept fundamentally (of course, I have ...
- 183
0
votes
1
answer
40
views
Results of a Program After Call By Reference Vs. Call By Value-Result
I have a question that I am trying to work through. I have a program:
...
- 101
1
vote
2
answers
33
views
Name of class of errors where the real state differs from the recorded state?
Is there a name for the class of software errors that arise from the fact that the software believes something wrong about the state of the world?
(Allow me a bit of anthropomorphization of software, ...
- 131
0
votes
1
answer
45
views
Computability = Enumerating a sequence in the particular order?
In the paper "Computability by Probabilistic Machines" by K. de Leeuw, E. F. Moore, C. E. Shannon, and N. Shapiro (in Claude E. Shannon: Collected Papers , IEEE, 1993, pp.742-771), a ...
- 119
1
vote
2
answers
105
views
Estimating the number of elements shared in two sets using a random sample
Suppose we have two sets $A$ and $B$. The sets share some number of elements between them, but within each set, any item appears at most once. We want to determine how many elements they share in ...
- 919
1
vote
0
answers
51
views
Is there an equivalent to "car" and "cdr" for "snoc"?
Note: This question assumes familiarity with cons-style linked lists (e.g., from Lisp or Scheme).
It also assumes familiarity with snoc-style lists. Snoc is like cons, except it appends elements to ...
- 111
3
votes
2
answers
44
views
Does there exist terminology to discern NFA states and NFA-transformed-into-DFA state?
I can't find this from surface search in the literature
When one observes/simulates NFA after processing several characters, one has to consider both "internal states of NFA" (individual ...
- 123
2
votes
1
answer
86
views
Clarifications about tree-width definition
I have read the definition of treewidth/tree-decomposition both in Wikipedia and in here:
https://medium.com/@karlrombauts/treewidth-how-all-graphs-are-trees-in-disguise-ec699b69e2fb
I'm finding ...
- 140
0
votes
1
answer
160
views
What's the difference between "convex/non-convex optimization" and "quadratic programming"?
I'd like to start by clarifying I'm by no means an expert in any of this, so take everything I say with a grain of salt.
Convex and Non-convex Optimization are subfields of mathematical optimization ...
2
votes
1
answer
97
views
Finite State Machine without recursion
I have found utility in state machines that do not have the complexity of recursion: no self or ancestral transitions.
Is there a name for this sub-category of FSMs? Are they commonly used or ...
- 123
1
vote
1
answer
118
views
How can we find a shortest closed walk passing through all vertices?
How can we find a walk with the minimal length starting from a vertex $v$, passing through all vertices and returning back to $v$?
We allow vertices and edges to be repeated along the walk. The ...
- 417
1
vote
3
answers
493
views
Why is the heap data structure called 'heap'?
The term "heap" has majorly two meanings in computer science -
The "heap" memory in the context of memory management.
The "heap" data structure as the representation of ...
- 143
0
votes
1
answer
88
views
Correct Term for describing "diamond" subgraphs in a Directed Acyclic Graph
I am trying to research handling a specific type of possible subgraph in directed acyclic graphs.
However, I am struggling to find the correct term to use.
If we consider the subgraph S to be in a DAG ...
- 9
1
vote
1
answer
65
views
What is a heuristic in human computer interaction?
I have found multiple definitions of what a heuristic is, and I have found multiple computer science-related definitions.
In my university course, the lectures cite the Nielson Norman Group defining a ...
- 13
1
vote
1
answer
59
views
relation based on a given partial order - does it have a name?
Let $P$ be a partial order on $X.$ Does the relation $E(P)=$ { $(x,y)\in (X\times X)\setminus P:P$ $\cup$ { $(x,y)$ } is a partial order on $X$ } have a name? If not, what's a good thing to call it?
- 123
1
vote
1
answer
107
views
Name for algorithms whose runtime only depends on the problem size?
I'm looking for the name of the family of algorithms whose exact runtime is dependent only on the size of the input. An example of such an algorithm would be naive $O(n^3)$ matrix multiplication. If ...
- 1,250
0
votes
0
answers
21
views
Name for a synchronous process that can buffer async tasks and then release
I have an async process that receives a message then post the content to another service and acknowledges the message.
To improve on the efficiency I want to batch the messages together, but can't ...
- 101
0
votes
0
answers
13
views
What is terminlogy missing from this list of words and phrases pertaining to string-matching and string-alignment?
I am looking for a long list of words/terms which are related to aligning one string to another.
String Metric
Edit-Distance
Bioinformatics
Needleman–Wunsch Algorithm
Sequence Alignment
Global ...
1
vote
2
answers
329
views
Does the even-odd rule ever have false positives for deciding a point in a complex polygon?
The wikipedia for even-odd rule says
On a simple curve, the even–odd rule reduces to a decision algorithm for the point in polygon problem.
On a complex polygon, there are clearly false negatives in ...
- 11
0
votes
0
answers
95
views
What are Funges?
I am currently reading up about esoteric programming languages and came across a COS theory question stated as follows:
Esoteric programming languages can be categorised in a variety of different ...
- 1
-3
votes
2
answers
75
views
Is frontend slang term is it used in teaching in univ
I have a question : is the term front-end in this context phpmyadmin is frontend for mysql slang is it taught in academy in this context I don't want to use slang term
- 1
0
votes
2
answers
71
views
Why is there a difference between the meaning of the word 'statement' in programming and linguistics?
In linguistics, the word 'statement' means something that is true or false, closer to a declarative sentence, but in programming, the meaning is closer to an imperative sentence.
What is the reason ...
- 13
1
vote
1
answer
181
views
The relationship between a perfect binary tree and a complete & full binary tree
I am reading the book "Cracking the coding interview". In Chapter 4 they cover basic tree concepts.
It says there that a complete binary tree is a binary tree in which every level of the ...
- 113
1
vote
0
answers
27
views
What is the name of the problem or technique used to quantify a given entity based on its properties?
I have the following idea:
Suppose a device D performing a set of tasks T1-Tn.
Each task Ti has 3 properties: time of execution(E), amount of memory needed(M) and priority(P).
...
- 11
3
votes
1
answer
160
views
Is possible to have a "pointer" to a tree node in a functional language?
Suppose I have the following structure definition in C:
struct node {
int value;
struct node *parent, *left, *right;
}
If I want to represent a specific ...
- 173
25
votes
3
answers
3k
views
Array access is O(1) implies a fixed index size, which implies O(1) array traversal?
Arrays are generally presented as data structures with $\Theta(N)$ traversal and $\Theta(1)$ random element access. However, this seems inconsistent:
if array access is really $\Theta(1)$, this means ...
- 380
0
votes
3
answers
100
views
Is there a notation for types?
Is there a notation for statements like the following:
If both operands are of type int, then the result is of type int. If ...
- 123
1
vote
0
answers
33
views
Is There a Term for "Factoring" a Graph by an Equivalence Relation on Nodes?
I have a coding problem I'm running into that feels like it's solved:
Given a (directed) graph, and an equivalence relation on nodes, merge the equivalent nodes in a way that preserves the graph ...
- 111
0
votes
0
answers
116
views
Is copying and pasting a sort of object embedding?
If I copy a picture and paste it into Microsoft Word, would there be the difference if I embedded the same picture into another Word file ? Are they both object embedding?(As the object is saved in ...
- 105
3
votes
1
answer
96
views
What is the formalism used to describe optional arguments called?
Most command line tools have an usage described by using square brackets for optional parts and just writing out required parts (like in regexes) for example:
foo [opt1[opt2...]] req1 req2 [opt3...]
...
1
vote
1
answer
195
views
Does a straightforward algorithm refer to the algorithm which intuitively solves a specific problem?
I'm trying to figure out what is a straightforward algorithm.
The following pseudocode comes from section 4.2 of "Introduction to Algorithms, 3rd Edition By Thomas H. Cormen, Charles E. Leiserson,...
- 588
0
votes
0
answers
78
views
How can I generate all combinations of 2 sets of unique numbers? How are those called?
I want to generate 2 sets from N elements.
Sets must be unique in the combination of sets
Numbers must not repeat across the 2 sets
Sets can have any amount of numbers, but must not be empty
...
- 101
6
votes
0
answers
47
views
How to find the minimum number of elements to distinguish several given sets?
Given $n$ distinct sets $S_1, S_2, \cdots, S_n$, how to find a set $X$ such that $X \cap S_1, X \cap S_2, \cdots, X \cap S_n$ are still distinct, and the size of $X$ is minimum?
For example, given $\{...
Acesrc
1
vote
0
answers
29
views
Is there a word for a property of an algorithm where the output of the algorithm does not depend on the order of the input?
I'm looking for a word to describe an algorithm that takes an ordered list as input, where the output depends on the content of the list but not the order. A sorting algorithm on integers would be an ...
0
votes
0
answers
299
views
What is a computational problem?
I'm reading Sipser's "introduction to the theory of computation" book. Even though in many places the phrase "computational problem" appears there is no definition of it. How is it ...
- 195
0
votes
0
answers
94
views
what's the differenece between finite state automaton and finite state automata
Upon googling all I get is the definition of finite-state automaton but what's the difference between it and finite-state automata or are they the same
- 101
0
votes
2
answers
81
views
Is there a standard or model or taxonomy of programming languages different than machine-threshold-highlevel?
I understand that there are three types of programming languages:
Machine languages
Assembly languages
high-level languages
And that:
Machine languages have no abstraction
Assembly language have ...
- 1
0
votes
0
answers
155
views
Set, then get, or first get, then set?
In some abstract programming languages there is a concept "setter and getter".
Generalizing, should this be the opposite, i.e. "Getter and setter"?
I would theorize that one should ...
- 1
3
votes
0
answers
251
views
What is the etymology of "swizzle"?
The word swizzle can refer to an operation performed in GPU algorithms:
[The] ability to compose vectors by arbitrarily rearranging and combining components of other vectors.
Swizzle (computer ...
- 131
1
vote
0
answers
147
views
Is try...catch a control flow pattern?
Is try...catch a control flow pattern such as if-than-else-elseif or ...
- 11
3
votes
2
answers
142
views
What does "lambda terms modulo convertibility" mean?
In "The Lambda Calculus - Its Syntax and Semantics" by H.P. Barendregt (WorldCat) is this statement, the first sentence of chapter 2 after the introduction chapter, so in a way this sets the ...
- 5,131
1
vote
0
answers
31
views
What does "terms modulo" mean? [duplicate]
In "The Lambda Calculus - Its Syntax and Semantics" by H.P. Barendregt (WorldCat) the term "term modulo" is used, E.g.
The principal object of study in the λ-calculus is the set ...
- 5,131
7
votes
2
answers
3k
views
Is the Berkeley tutorial on Fibonacci trees using wrong figures?
I'm confused about the figures in a Berkeley tutorial on Fibonacci trees, which depicts fibtree(2) as
and fibtree(3) as
I thought fibtree(3) looks like the following
(the figure is adapted from ...
- 588