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
1answer
86 views

When are edges adjacent?

What conditions must be fulfilled for two edges of a graph to be called adjacent? I found a lot about adjacent nodes, but our CS course script refers to adjacent edges, with no explanation.
1
vote
1answer
116 views

Terminology for property of recursion definitions

I have a question about generally accepted terminology (and whether it exists at all). Some recursive algorithms on hierarchical data structures (trees) have the property that they are expressed as a ...
3
votes
1answer
65 views

Why pointer dereference was once called “decrement”?

I'm reading McCarthy's paper Recursive Functions of Symbolic Expressions And Their Computation by Machine, where when the author describes the machine implementation of lists, he writes this: a. ...
2
votes
1answer
197 views

Is this book's definition of phrase correct?

I am fairly confident that my textbook (Concepts of Programming Languages 11th edition, international edition, Robert Sebesta) has an error in its definition of what a phrase is in the section on ...
1
vote
0answers
29 views

CFG grammar with fixed number of “distinguished” terminals

I would like to know if there is a name for CFG grammars (or grammars in general) in which there is a fixed number of "distingushed" terminals or in which there is a terminal that appears a fixed ...
9
votes
2answers
8k views

Computational complexity vs Computational cost

Is there a difference between the computational complexity and computational cost of an algorithm?
10
votes
2answers
186 views

Name of this rearranging/sorting problem?

You are given an array of length $n$. Each element of the array belongs to one of $K$ classes. You are supposed to rearrange the array using minimum number of swap operations so that all elements from ...
1
vote
1answer
104 views

How to compare the efficiency of two encoding schemes or hypothesis languages?

My question is pretty basic, I'm looking for a named method if you know one, but also proper terminology, further reading, and anything this reminds you of if you don't. (I'm new to this, don't have ...
0
votes
1answer
554 views

What are thin-core and fat-core processors

I am reading a paper called Back to Thin-Core Massively Parallel Processors by Ami Marowka (Computer, 44(12):49–54, 2011; IEEE Xplore). However I have a question about the title of the article: ...
1
vote
1answer
143 views

Name for tree where each node has the aggregate of its children

Is there a general name for a tree in which the leaves have some arbitrary values and the value of every other node is some "aggregate" function of its children? An example where the aggregate ...
1
vote
2answers
121 views

What kind of growth is $O(0.24\cdot K\cdot 2^w)$

I've calculated the running time of an algorithm I'm interested in to be $$O(0.24\cdot K\cdot 2^{w})\,,$$ where $K$ and $w$ are both variables. ($K$ is the number of elements in some set, ...
0
votes
1answer
218 views

The origin and the meaning of “Abstract Syntax Tree”

This question is closely related to Does an abstract syntax tree have to be a tree? and is partially answered there, but I would like to be more precise and to have more concise answers. What is the ...
2
votes
1answer
59 views

Which is better wording: x grows with $N^2$ or x grows with $O(N^2)$

Which of the following sounds better (or more rigorously): x grows with $N^2$ or x grows with $O(N^2)$ or x grows quadratically with $N$.
1
vote
1answer
157 views

Big O - Equivalence: “Standard” definition vs Limit definition

This question is related to: Landau Notation, Definitions: Limits vs. Cormen's. Consider functions $f, \ g : N \rightarrow R^{\geq0}$. For small-$o$, the definition: $$f(n)\in o(g(n)) \iff \forall ...
0
votes
0answers
37 views

Command line switches, flags, options

What is the difference between switches, flags and options when you want to specify something on the command line? Are they all synonyms? Are there any reasons why some terminals require: ...
7
votes
4answers
4k views

Simple (non-mathematical) definition of polynomial time?

Computational Complexity Theory is complex. My understanding of polynomial time is in relation to other time complexity classes, such as non-deterministic polynomial time. This is fine for engineers ...
0
votes
0answers
34 views

What is the nomenclature or theory for determining an overall status of multiple enumerations?

I am writing a method which evaluates multiple status enumerations and determines an overall status. I'm looking for what this process might be called and perhaps some theory on it. It may be best to ...
3
votes
2answers
12k views

What's the difference between Computer Science and Informatics?

The Terms are much used in actual IT (Information Technology). Is it possible to make a difference or are this terms nearly synonyms for the same fact?
0
votes
0answers
216 views

Iteration vs. recursion: what do these terms really mean?

Most of us know the typical answer to this question: if a function calls itself, it's recursion, if it's a loop, it's iteration. We also know that recursion can be simulated using iteration (by ...
1
vote
0answers
79 views

Formal definition of simulation

Assume that the model of computation is a standard Turing machine model with input alphabet $\Sigma = \{0,1\}$, work alphabet $\Gamma = \{0,1,\_\}$, 1 input tape, 1 work tape and 1 output tape. We ...
1
vote
1answer
57 views

Is there a name for the “tree” aproach to listing things?

I've only been studying computer science for a few weeks, so I apologize if this is a silly or naive question. Suppose we're trying to list all elements of the set $$C(r) = \{(x,y,z) \in \mathbb{N}^3 ...
5
votes
2answers
8k views

What is instruction throughput and instruction latency?

I was reading an article on an alternative method of modulo reduction and i couldn't understand the following excerpt (Those in bold) : "A single 32-bit division on a recent x64 processor has a ...
3
votes
2answers
58 views

Does “in-place” for $n$ items imply space dominated by $n$?

Does the characterisation of an algorithm for $n$ items as in-place imply space ∊ $ο(n)$ formally informally ("among coders")?
0
votes
2answers
141 views

What is the meaning of 'moderately exponential' running time?

I was reading some research paper where for hypergraph of bounded rank $k$ they have given moderately exponential algorithm. The runtime of the algorithm is $e^{ \mathcal {O}(k^2\sqrt n) \cdot poly(n)...
4
votes
0answers
133 views

Name for function in big O but not in little o?

Let $f(n) = O(g(n))$, but not $f(n) = o(g(n))$. That's a nice property, because it means that we cannot replace $g(n)$ with a substantially smaller function. Is there a name for this choice of $g(n)$? ...
1
vote
1answer
63 views

Is connected forest a spanning tree? [closed]

forest : set of disjoint trees. So a connected forest is a forest, a tree, a spanning forest and a spanning tree. Is that correct? Edit: disjoint trees in the forest are connected by single edge, ...
3
votes
1answer
31 views

When talking about the length of a path in a graph, what exactly is a skip?

I'm studying for a final and when looking for the shortest path in a graph from one vertex to another, what is meant by k-skips? One website defines it as the ability to change the weight of one edge ...
1
vote
1answer
89 views

Does this behavior have a formal name, and if so, what is it?

This is related to the issue asked about in this other question. For the sake of this question, let's assume that we have a variable v that can have any value from the set of values "a", "b", "c", ...
1
vote
0answers
32 views

What do you call a set which has the following enumeration-related machine?

A set $S$ of natural numbers is Recursively Enumerable if there exists a Turing machine which enumerates them, i.e. given no input, outputs the elements of $S$ in increasing order (never halting if $...
7
votes
1answer
387 views

Why are the laws of an applicative functor defined the way they are?

Let's recall the definition of an applicative functor. Throughout this question, I write $x: T$ to denote that the value $x$ has type $T$. Definition: An applicative functor consists of a type ...
1
vote
2answers
101 views

Are grandparent classes also parents?

Let's say I have three classes, Animal, Bird and Pigeon. If ...
1
vote
1answer
267 views

max, min gradient and other terms in Neural Network

This link contains a demo that trains a Convolutional Neural Network on the MNIST digits dataset in browser. I am not getting below terms- 1. max, min gradient in each layer. 2.max, min activation ...
4
votes
1answer
710 views

Definition of $\alpha$-approximation

I know this question is trivial. But I am looking for a concise formal definition of $\alpha$-approximation. Is it correct to say that "An algorithm is an $\alpha$-approximation to problem $X$, if ...
1
vote
1answer
483 views

How to proof a heuristic?

I am not very familiar with "heuristic", so please correct me if anything said by me is wrong. Per my understanding, Algorithm is an automatic steps which guarantee to give a correct solution ...
1
vote
1answer
49 views

Is the term page replacement actually a misnomer?

My understanding is that "page replacement" entails replacing the contents of a frame to bring in a new frame in it's place corresponding to a new page. Since it is not the page, but the frame that ...
3
votes
1answer
106 views

Is there a name for this traversal-optimized representation of a binary tree data structure?

I have used a purely functional binary tree structure in which there is a single node that is "marked". It allows for $O(1)$ access and modification of the marked node's value, as well as $O(1)$ ...
2
votes
1answer
63 views

General name for linked lists based on hashes

I am thinking of a particular datastructure, but don't know the name of it. A sequence of elements may be modeled by a collection of some X, where each X consists of: The element, serialized as a ...
1
vote
1answer
149 views

What does it mean for a problem to be solved in polynomial time “relative to” an oracle?

I came across the following theorem in page 12 of the following pdf : There exists an oracle relative to which there is a problem solvable in polynomial time (with bounded error probability) on a ...
5
votes
2answers
1k views

What is a fixpoint?

Could someone please explain me, what is a fix point? I caught the minimum explanation about fix point from the website: After infinitely many iterations we should get to a fix point where ...
13
votes
3answers
444 views

What's the difference between a calculus and a programming language?

I think I'm pretty confused about what's called a calculus and what's called a programming language. I tend to think, and might have been told, that a calculus is a formal system for reasoning about ...
13
votes
1answer
10k views

What is meant by the term “prior” in machine learning

I am new to machine learning. I have read several papers where they have employed deep learning for various applications and have used the term "prior" in most of the model design cases, say prior in ...
1
vote
0answers
49 views

Formal name of the product of product type

What is the formal name in type theory of the operation that creates a "matrix of types" from product types (such as std::tuple in C++)? For example if we consider ...
40
votes
4answers
8k views

What is the name the class of functions described by O(n log n)?

In "Big O", common notations have common names (instead of saying, "Oh of some constant factor"): O(1) is "Constant" O(log n) is "Logarithmic" O(n) is "Linear" O(n^2) is "Quadratic" O(n * log n) ...
2
votes
1answer
51 views

Constrained optimization topics

Given functions $f, p, c$, a matrix $X$, and vectors $C,D,E$. I want to maximize the multivariable function $f(X)$, where $X$ is a $p \times q$ binary matrix ($X_{ij}$ is 0 or 1). So, $p\cdot q$ ...
1
vote
1answer
29 views

Smaller approximation ratio for larger input size?

Is it possible for an approximation algorithm (for minimization optimization problem) to obtain smaller approximation ratios for inputs of larger size? For example, is $1/n$- or $1/\log n$-APX ...
0
votes
3answers
3k views

What is a type definition?

When reading about data types, "type definition" is often used without any prior explanation to what it means. For example, in https://en.wikipedia.org/wiki/Type_system, we have the sentence "... ...
1
vote
0answers
68 views

Definitions for Validity, Consistency, Integrity, Soundness and Completeness in Proof Systems

I have always tried to understand the difference between all the above, but I always ended up being confused. The field I am referring to is cryptography in particular, but I guess this question is ...
2
votes
1answer
6k views

MST: Are all safe edges, light edges?

Following are some definitions from CLRS: DEFINITIONS : 1. Cut (S ,V-S) : of an undirected graph G = (V,E) is a partition of V(as defined in CLRS Book) .You can think it as a line that divides ...
0
votes
0answers
154 views

Definition of profiling in information science

According to the Wikipedia articles, In information science, profiling refers to the process of construction and application of user profiles generated by computerized data analysis. This ...
1
vote
2answers
2k views

In algorithm analysis what does it mean for bounds to be “tight”

For example we could say alg(x) runs big omega(n) but this bound is not "tight". What is meant by "tight"? Is it that the bound isn't at its maximum? So maybe a tighter bound could be big omega (1)??...

1
3 4
5
6 7
22