Questions tagged [definitions]
The definitions tag has no summary.
53 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
0
votes
1
answer
45
views
Regular expression circular definition in Sedgewick's Algorithms 4th ed
In Sedgewick and et al.'s Algorithms 4th ed., I found the following definition for a regular express:
A regular expression (RE) is either
Empty
A single character
A regular expression enclosed in ...
0
votes
2
answers
127
views
What Precisely Is An Effective Method/Procedure?
As title. I'm, fortunately, reading the Wikipedia page titled "Effective Method", unfortunately. (1. I love the fact that it's open-source/available to everyone on Earth, 2. I hate ...
1
vote
1
answer
345
views
Definition of binary heap data structure
In the book Algorithms 4th edition, the authors, Kevin Wayne and Robert Sedgewick, (loosely) defines the binary heap data structure as follows:
The binary heap is a data structure that can ...
2
votes
2
answers
266
views
Why does it make sense to minimize regret?
In fields such as game theory and reinforcement learning, it is standard to consider the regret-minimization strategy. I don't get the motivation for the definition.
Yes, doing your best under worst-...
1
vote
1
answer
113
views
Explain why the condition "NIL need to be black" exists in RED-BLACK tree definition
I know there's another question asking the same in this website, but answers to that question was not clear; it did not help me.
In this wikipedia page, the 2nd property says "All NIL nodes are ...
0
votes
1
answer
93
views
What does weaker term mean in the definition of BigO
I am reading Computer Science Distilled book and in section 2.2 The Big-O Notation there is a line.
A function with fastest-growing term of 2ドル^n$ or weaker is $O(2^n)$
What does weaker mean here? ...
-1
votes
2
answers
109
views
Definition of semi-infinite tape Turing machine
What is the formal definition of a semi-infinite tape Turing machine? How do we define its transition function, to avoid going left when we are at the boundary?
2
votes
1
answer
99
views
Are classes $\textbf{NC}$ and uniform $\textbf{NC}$ the same?
On page 117 in Arora and Barak, the definition of class $\textbf{NC}$:
For every $d,ドル a language $L$ is in $\textbf{NC}^d$ if $L$ can be decided
by a family of circuits $\{C_n\}$ where $C_n$ has poly(...
0
votes
0
answers
51
views
Simple Notation to Say "A combination of" components?
I would like to delve into writing in a more scientific way to define my problems. My though is that it will help me see more similarities between problems faster.
Question
Hence, I would like to ...
3
votes
2
answers
1k
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 ...
2
votes
1
answer
276
views
Why there is no definition of cut vertices or articulation points in directed graphs?
We know cut vertex is an important definition in undirected graph, indicating a vertex which when removed, the number of connected components would increase. And we also have an efficient algorithm ...
-2
votes
2
answers
129
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?
1
vote
1
answer
69
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 ...
0
votes
0
answers
48
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.200803002). Here the authors used the trigraph, that is the adjacency relation ...
1
vote
1
answer
130
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 ...