Exam Questions Flashcards
1
Q
What is the logarithm change of base trick?
A
2
Q
What is the logarithm change of exponential base trick?
A
3
Q
What is the Geometric series?
A
4
Q
What are the steps the recursion tree method?
A
- Draw the tree
- Calculate the work per level, continue until level k
- Find the number of levels: Find for which k you only have one element left (thus just n/(b^k) = 1)
- Sum work: So just sum from 0 until what you found in step 3
- Bound this sum
5
Q
How do you find the number of levels in the recursion tree method?
A
You have a formula by which n decreases per layer. I.e.
n/(b^k). Equate this to one, and solve.
6
Q
What is the Master theorem if a = b^d?
A
O(n^d log_2 n)
7
Q
What is the Master theorem if a < b^d?
A
O(n^d)
8
Q
What is the Master theorem if a > b^d?
A
O(n^(log_b a))
9
Q
How to use the substitution method if T(n) = [..]T(n-a)[..]?
A
10
Q
What are the inductive steps when proving a looping/recurring algorithm?
A
- Loop/Recurring invariant
- Initialization
- Maintenance
- Termination
11
Q
How to prove the correctness of an algorithm?
A
By induction, but they do not really ask for high quality proofs.
