Reading...
Play button
Play button
Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
32 Cards in this Set
- Front
- Back
- 3rd side (hint)
|
g(n) = O( f(n) )
|
∃ positive constants C and N :
| g(n) | ≤ C∙f(n), ∀ n > N |
denotes "g(n) has order at most f(n)"
|
|
|
g(n) = Ω( f(n) )
|
∃ positive constants C and N :
| g(n) | ≥ C∙f(n), ∀ n > N |
denotes "g(n) has order at least f(n)"
|
|
|
g(n) = Θ( f(n) )
|
∃ positive constants C1, C2 and N :
C1∙f(n) ≤ g(n) ≤ C2∙f(n), ∀ n > N |
denotes "g(n) has the same order as f(n)"
|
|
|
∃
|
denotes "there exists"
|
|
|
|
∀
|
denotes "for all"
|
|
|
|
→
|
denotes "implies"
|
⊃ and ⇒ are alternative notations
|
|
|
⌝
|
denotes "not"
|
alternative notation is suberbar
|
|
|
⌃
|
denotes "and"
|
alternative notation is juxtaposition of statements, e.g. PQ
|
|
|
satisfiable
|
a boolean formula which is true under some assignment of boolean values for its variables
|
|
|
|
tautology
|
a boolean formula which is true under all assignments of boolean values for its variables
|
alternative vocabulary is "valid"
|
|
|
⌀
|
denotes the empty set
|
|
|
|
A ∩ B
|
set of all elements that are in both A and B
|
|
|
|
A ∪ B
|
set of all elements that are in A or in B or in both
|
|
|
|
(bar) A
|
set of all elements not in A that are in some specified universal set
|
|
|
|
| A |
|
the cardinality of A
|
|
|
|
cardinality (of a set)
|
a measure of the "number of elements of the set"
|
|
|
|
ϵ
|
an empty string
|
alternative notation is Λ
|
|
|
ST (string expression)
|
denotes the concatenation of S and T
|
|
|
|
concatenation (string)
|
the operation of joining two character strings end to end
|
|
|
|
S + T (string expression)
|
{ w | w ∈ S ^ w ∈ T }
|
alternative notation is S ∪ T or {S, T}
|
|
|
S^n (string expression)
|
denotes SS..S, with n factors
|
|
|
|
S^* (string expression)
|
denotes ϵ + S + S^2 + S^3 + ...
|
|
|
|
S^+ (string expression)
|
denotes S + S^2 + S^3 + ...
|
|
|
|
α → β (grammar)
|
a production in the grammar
|
|
|
|
α ⇒ β (grammar)
|
β can be derived from α by the application of exactly one production
|
|
|
|
α ⇒^* β (grammar)
|
β can be derived from α by the application of zero or more productions
|
|
|
|
preorder
|
recursively:
1. visit the root 2. traverse the left subtree 3. traverse the right subtree |
|
|
|
inorder
|
recursively:
1. traverse the left subtree 2. visit the root 3. traverse the right subtree |
|
|
|
postorder
|
recursively:
1. traverse the left subtree 2. traverse the right subtree 3. visit the root |
|
|
|
partially correct
|
for an algorithm, if an answer is returned it will be correct
|
for a program segment S and predicates P and Q, to say that the triple {P}S{Q} is PARTIALLY correct means that if P is true before initiation of S, then Q is true upon termination of S
|
|
|
totally correct
|
for an algorithm which terminates for all inputs, if an answer is returned it will be correct
|
for a program segment S and predicates P and Q, to say that the triple {P}S{Q} is TOTALLY correct means that it is partially correct and S terminates for all inputs for which P is true
|
|
|
loop invariant
|
an assertion that is true each time the guard B is evaluated during execution of the statement: while B do S
|
a condition that SHOULD true on entry into a loop, GUARANTEED to remain true at the end of every iteration of the loop, and is GUARANTEED true on exit from the loop (along with truth of the loop termination condition)
|
