Questions tagged [terminology]

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

Filter by
Sorted by
Tagged with
1 vote
2 answers
47 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 ...
Mike Battaglia's user avatar
1 vote
0 answers
28 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 ...
Kyle Lin's user avatar
  • 111
1 vote
1 answer
22 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 ...
NooneAtAll3's user avatar
1 vote
1 answer
54 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 ...
Benicio Agüero's user avatar
0 votes
1 answer
27 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 ...
Vee Amona's user avatar
2 votes
1 answer
59 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 ...
Synesso's user avatar
  • 123
1 vote
1 answer
48 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 ...
licheng's user avatar
  • 231
1 vote
3 answers
147 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 ...
Aniruddha's user avatar
  • 143
0 votes
1 answer
54 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 ...
T-Tory's user avatar
  • 9
1 vote
1 answer
40 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 ...
Eris's user avatar
  • 13
1 vote
1 answer
57 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?
mathematrucker's user avatar
1 vote
1 answer
99 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 ...
Björn Lindqvist's user avatar
0 votes
0 answers
20 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 ...
Mr Giggles's user avatar
0 votes
0 answers
12 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 ...
Toothpick Anemone's user avatar
1 vote
2 answers
172 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 ...
BlakeMScurr's user avatar
0 votes
0 answers
92 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 ...
OomBen's user avatar
  • 1
-3 votes
2 answers
73 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
Shanel's user avatar
  • 1
0 votes
2 answers
63 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 ...
Santiago's user avatar
1 vote
1 answer
105 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 ...
Mikhail Genkin's user avatar
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). ...
Nht_e0's user avatar
  • 11
3 votes
1 answer
123 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 ...
matteo_c's user avatar
  • 133
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 ...
Antoine Pietri's user avatar
0 votes
3 answers
91 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 ...
user51462's user avatar
  • 113
1 vote
0 answers
31 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 ...
Duncan W's user avatar
  • 111
0 votes
0 answers
44 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 ...
user1039203's user avatar
3 votes
1 answer
87 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...] ...
eternalstudent's user avatar
1 vote
1 answer
92 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,...
JJJohn's user avatar
  • 588
0 votes
0 answers
50 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 ...
jokoon's user avatar
  • 101
6 votes
0 answers
41 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 $\{...
user avatar
1 vote
0 answers
24 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 ...
Brandon Hoane's user avatar
0 votes
0 answers
154 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 ...
Sanyo Mn's user avatar
  • 193
0 votes
0 answers
76 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
rashed a564's user avatar
0 votes
2 answers
58 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 ...
guest's user avatar
  • 1
0 votes
0 answers
127 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 ...
guest's user avatar
  • 1
2 votes
0 answers
134 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 ...
Chance Snow's user avatar
1 vote
0 answers
81 views

Is try...catch a control flow pattern?

Is try...catch a control flow pattern such as if-than-else-elseif or ...
alistro's user avatar
  • 11
3 votes
2 answers
101 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 ...
Guy Coder's user avatar
  • 5,091
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 ...
Guy Coder's user avatar
  • 5,091
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 ...
JJJohn's user avatar
  • 588
0 votes
1 answer
13 views

What is the name of this content-addressing scheme?

Git seems to use the two most significant hex digits of a content hash as a directory name for content-addressable objects. The same two digits are left out of normal file names. I'm assuming the ...
Sage Gerard's user avatar
8 votes
11 answers
4k views

Real life examples of *zero* weight edges in graphs

The meaning of edges with zero weight in a weighted graph questions me for a long time, and I even asked a related question previously. Yet, when I recently read here a question on real life example ...
Matthieu Latapy's user avatar
0 votes
1 answer
49 views

Understanding P, NP with an example decision problem

I was reading the definitions of p vs np in [this post] (What is the definition of P, NP, NP-complete and NP-hard?) and I was wondering about how to classify the example decision problem where you ...
CLEE's user avatar
  • 3
2 votes
1 answer
83 views

What is the outermost class 2^Σ* referring to on the Extended Chomsky Hierarchy?

After having searched a bit, it seems I can't find terminology or references for this outermost class, 2Σ* in blue -- see below. What is it describing?
Josh Hibschman's user avatar
0 votes
1 answer
17 views

What does it mean to 'provide' an API call?

So I have a database pre-loaded with data related to food recipes and the assignment says: 'Provide an API call that allows us to specify an ingredient or set of ingredients and return full recipes ...
michaelgz13's user avatar
2 votes
1 answer
42 views

Are bits (0/1) named "characters" anywhere in the literature?

I know that each character ("in the macro level") is comprised of at least two bits ("in the micro level"). But are these bits of this "micro, electrical-logical level" ...
Yorlandier's user avatar
0 votes
0 answers
24 views

What is BB(n) terminology precisely saying about symbols, states, space, and steps involved?

This question is mainly about the clarification of the terminology BB(n), not how busy beavers work. It seems common to refer to busy beaver numbers like ...
Josh Hibschman's user avatar
2 votes
1 answer
193 views

What makes 'interrupt vectors' vectors?

I've recently been learning about interrupt vectors, partly from this Wikipedia page. I've understood that different processors will have different types of interrupts, and the interrupt vector table ...
Joe's user avatar
  • 123
1 vote
2 answers
291 views

NFA has power to be in several states at once implies NFA has ability to guess about its input. How?

I agree that NFA has power to be in several states at once. It probably means that on same input, NFA can be on multiple states. But what I can't understand is how can we conclude from this that "...
silfeg's user avatar
  • 51
0 votes
1 answer
20 views

Word that describes text transformation into a code with data loss

I am working with a piece of software code which transforms a character array into a single integer. For example, if I have the array [ a, b, c ], then it becomes ...
MC Emperor's user avatar
8 votes
2 answers
144 views

Does the concept of "side-effect" predate functional programming?

When I was reviewing a book, I saw that there's a sentence claiming "side effect is a term coming from the domain of functional programming". I would think that the concept existed before ...
kolistivra's user avatar

1
2 3 4 5
23