Questions tagged [definitions]
The definitions tag has no usage guidance.
43
questions
3
votes
2
answers
550
views
Number of leaves in complete binary tree
I got confused a bit about definitions and from reading in the different forums, does both complete binary tree (last level is not full) and perfect binary tree, number of leaves are ⌈n/2⌉ for a tree ...
- 31
-2
votes
2
answers
65
views
Precise definition of a brute force algorithm
What is the precise definition of a brute force algorithm?
Is it one that simply has non-polynomial runtime?
- 154
1
vote
1
answer
36
views
Seeking a reference for NP-hardness of optimization problems
Most optimization textbooks do not cover the concept of NP-hardness. Some examples include:
"Convex optimization" by Boyd and Vandenberghe
"Numerical Optimization" by Nocedal and ...
- 821
0
votes
0
answers
21
views
Why do the authors use the 'trigraph' to characterize some class of graphs?
I have read the series of papers about "the structure of claw-free graphs" (https://doi.org/10.1016/j.jctb.2008.03.002). Here the authors used the trigraph, that is the adjacency relation ...
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
0
votes
1
answer
73
views
Definition of the term "small systems" in computer science
What is the definition of the term "small systems" in the context of computer science? My professor didn't really define the term, they just gave examples of some small systems. I'm having a ...
- 101
0
votes
2
answers
100
views
What is the right name for a "map" data structure?
I'm trying to say this in my paper: "$M$ is a key-value store, where 1) all keys are unique, 2) $k \in M$ means that the $k$ key exists in the store, 3) $M + (k, v)$ is a new store equal to $M$ ...
- 113
3
votes
1
answer
85
views
Are two regularity properties on hypergraphs equivalent?
Let $H=\left( E_0 ,E_1 ,E_2 , \ldots , E_d \right)$ be a $d$-dimensional full-hyper graph/complex. That is to say, if for some $i\in \left[d \right]$ the hyper-edge $e_j \in E_i$ than for any $i-1$-...
- 140
2
votes
2
answers
156
views
Alternate definition of recursively enumerable languages
Exercise 9.2.3(c) of the book by Hoffman, Motwani, Ullman states
In fact a definition of the RE-but-not-recursive languages is that they can be enumerated but not in numerical order
How do we show ...
- 160
0
votes
4
answers
647
views
What is a procedure?
Non-computer scientist here, trying to understand what SICP (Structure and Interpretation of Computer Programs) means by a procedure, whether it matches the dictionary definition, and also how a ...
- 113
1
vote
1
answer
123
views
formal definition for "data type with larger range"
Wikipedia defines range of data type:
the set of possible values that that variable can hold.
Suppose we have two data types A and B. Now, with attention to
the ...
- 113
0
votes
1
answer
72
views
What's the difference between computation and symbolic manipulation?
I have lived my academic career thinking these two terms were interchangeable but something arose in me that said they're distinct. Are there any logical, formal definitions distinguishing between the ...
- 71
1
vote
2
answers
203
views
Formal definition of algorithm runtime
In the analysis of algorithms textbooks that I've seen, as far as I could tell, the runtime of an algorithm is defined intuitively. Is there a simple formal definition of this concept? I.e. a ...
- 4,062
0
votes
0
answers
186
views
Definition of the term "access efficiency" in the context of computer systems
In a two-level virtual memory, the memory access time for main memory, $t_M=10^{−8}$ sec, and the memory access time for the secondary memory, $t_D=10^{−3}$ sec. What must be the hit ratio, $H$ such ...
- 1,152
1
vote
1
answer
74
views
Probabilistic Turing Machine Transition Relation vs Transition Function
In wiki, PTM are defined with two transition functions and a fair coin toss which determines which one is used at each step. One can also define them, much like NDTM, using a transition relation where ...
2
votes
0
answers
50
views
Regarding the definitions of time-constructible functions on Wikipedia
I am reading the Wikipedia article on time-constructible functions and got confused by its definitions, given as follows:
There are two different definitions of a time-constructible function. In the ...
- 457
0
votes
1
answer
51
views
Same instances for different problems
According to the formal definition of an instance, it is a set of input data containing the values of the parameters of some problem (What is an instance of NP complete problem?).
So, two problems may ...
- 103
0
votes
2
answers
49
views
What's the error about the definition of NP?
Many sources (including Wolfram's MathWorld) say that NP problem is defined as a decision problem "verifiable in nondeterministic polynomial time" (check Google to see more sources).
But ...
- 503
2
votes
2
answers
796
views
What defines how many lookahead a lexer has?
if a lexical grammar has multiple token which start with the same character like > >> ...
- 21
0
votes
1
answer
88
views
Having trouble understanding blatantly non-private definition because of Little-o notation
I was pretty confident that I understand asymptotic notation until now. However, I am having a hard time understanding some basic definition that use asymptotic notation, specially little-o.
...
- 3
1
vote
0
answers
50
views
Language of all words of the form $ww$ is in $\mathsf{NTIME}(n)$
Show that the language $\{ ww \mid w \in \{0,1\}^* \}$ is in $\mathsf{NTIME}(n)$.
I have a doubt first of all how can I prove that. Secondly, what does NTIME mean? Can we use a $k$-Tape Turing ...
- 11
1
vote
1
answer
109
views
Can inputs in the decision tree model be computed?
The Wikipedia definition of the decision tree model says that it allows the sign functions of certain classes to be computed in constant time (and presumably also memory). My questions, still ...
- 115
2
votes
1
answer
55
views
On the definition of Error-Correcting Codes
Let us start with the following well-known definition:
Definition 1. Let $C\subseteq A^n$ be a code over $A$ and let $t\in \Bbb Z^+$ be a positive integer. We say that the code $C$ is
$\boldsymbol t$...
- 123
0
votes
1
answer
40
views
Isn't an improper subset of edges of a cyclic graph, cyclic and thus not a minimum spanning tree?
This is the formal definition of a minimum spanning tree taken from Algorithms by Dasgupta, Papadimitrious and U. Vazirani.
Input: An undirected graph $G = (V,E)$; edge weights $w_e$.
Output: A tree $...
- 659
0
votes
2
answers
88
views
PRECISE DPLL algorithm definition
I am confused about the precise definition of the DPLL algorithm. Various sources tend to define DPLL differently:
In pages 110-114 of the book Handbook of Satisfiability(Editors: Biere, A., Heule, M....
1
vote
1
answer
42
views
Equivalene of big O definitions (Limit Definition $\Longleftrightarrow$ Quantifier Definition)
I need to proof, that both definitions of the Big 0 notation are equiavlent, but I am not sure if my proof works both ways of the equivalence.
Definitions:
Let f,g be functions.
$f(n)\in \mathcal{O}(...
2
votes
1
answer
223
views
What is the difference between Hamming Distance and Manhattan Distance for non-binary data?
What is the difference between Hamming Distance and Manhattan Distance for non-binary data (specifically I am comparing points in $\mathbb{R}^2$)? I understand Manhattan sums the absolute difference ...
- 123
0
votes
0
answers
31
views
How isolate the last bit work on teory Binary Indexed Trees
I'm learning about the Binary Indexed Trees, and I understand how it works, but I'm interested in the theory that there is behind!
In particular, I don't understand what is meant the following ...
- 45
2
votes
1
answer
167
views
Why are $L$-reductions defined the way they are?
I was reading about $L$-reductions and there was one part in the definition that I thought was interesting. I wanted to know what motivated people who came up with it to have it included in the ...
- 413
1
vote
0
answers
44
views
A genral Turing model with one tape to define sublinear space (L,NL,..)
A genral Turing model with one tape to define sublinear space (L,NL,..)
Normally to define sub-linear space complexity we need special Turing models with many tapes, at least two: a read-only tape and ...
- 243
4
votes
0
answers
99
views
Understanding the Transition points of a BST
I'm trying to understand the definition of Transition point of a BST, as given in Demaine, Erik D., et al. "Dynamic optimality-almost." SIAM Journal on Computing 37.1 (2007): 240-251
...
2
votes
2
answers
605
views
Definition of NP-hardness for non-decision problems
As I understand, the term "NP-hardness" is applicable when we also talk about optimization or search problems (i.e. return the satisfying assignment for 3-SAT). How do we formally define NP-...
user114966
1
vote
1
answer
309
views
Nondeterministic polynomial time algorithm versus certificate/verifier for showing membership in NP
In this paper (https://arxiv.org/pdf/1706.06708.pdf) the authors prove that optimally solving the $n\times n\times n$ Rubik's Cube is an NP-complete problem. In the process, they must show that the ...
- 113
1
vote
1
answer
148
views
A question regarding definition of Deterministic Subexponential Time (SUBEXP)
First Look at the definition of SUBEXP from Complexity Zoo:
SUBEXP: (Deterministic Subexponential-Time)
The intersection of DTIME($2^{n^\epsilon}$) over all $\epsilon$>0. (Note that the algorithm ...
- 749
0
votes
1
answer
276
views
Sets in Mathematics are immutable but in Computer Science sets are mutable and called "Dynamic Sets" - truth of the statement
While reading the classic text Introduction to Algorithms by Cormen et. al. I came across the following claim:
Sets are as fundamental to computer science as they are to mathematics. Whereas ...
- 1,152
0
votes
1
answer
204
views
Clarifying statements involving asymptotic notations in soln of $T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2)$ using recursion tree and substitution
Below is a problem worked out in the Introduction to Algorithms by Cormen et. al.
(I am not having problem with the proof but only I want to clarify the meaning conveyed by few statements in the text ...
- 1,152
1
vote
1
answer
78
views
When does a Monte Carlo algorithm solve a problem?
When can we say that a Monte Carlo algorithm solves a problem?
To quote from Wikipedia on Monte Carlo algorithms
For instance, the Solovay–Strassen primality test is used to determine whether a ...
- 457
18
votes
11
answers
5k
views
Why do logic gates behave the way they do?
I am a Software Developer but I came from a non-CS background so maybe it is a wrong question to ask, but I do not get why logic gates/boolean logic behave the way they do.
Why for example:
...
- 317
0
votes
1
answer
260
views
Formal definition of hash function
I was reading through the classic CLRS with the intention of reviewing the hash tables theory, more specifically the hash function definition I just wanted a reference to quote.
I cannot find a ...
- 713
1
vote
1
answer
936
views
Difference between task and process
I'd like to know which is the difference between a task and a process in computer science. I'm studying a course on real-time systems and there are some definitions that I don't know.
Thank you in ...
- 113
3
votes
0
answers
51
views
What is the name of visiting an array starting at first element, then last element, then second, then last but one, then third, etc
For example if I have an array
[0, 1, 2, 3, 4, ..., n]
and I want to iterate over it in an order like
...
- 161
1
vote
0
answers
45
views
Randomized version of the class $APX$?
Is there a class which is to APX what BPP is to P?
I'm looking for a definition that is like the following:
"For $r > 0$, an $r$-RPCA (randomized polynomial-time constant-factor approximation) ...
- 384
7
votes
3
answers
2k
views
Simple cycles of length two in an undirected graph
Pedagogical question.
Background
A cycle in a graph can be defined as a sequence of vertices $v_1,\dots,v_n$ with $v_1=v_n$ such that, for each $i \in \{1,\dots,n-1\}$, the graph has an edge $(v_i,...
- 4,179