QUIZ 1
Q1: [2] What is the complexity of the left-rotate operation in a
BST that has N nodes and height H ? Express it in O( ) notation.
- 2 rotations , local constant time operations , do not depend on N or H
- therefore O(1)
Q2: [2] What is the expected height of a treap with N nodes?
Express it in O( ) notation.
treap with O(logn) base 2 . lg(N) <- expectation not guaranteed
controlling height with RB and treaps
Q3: [2] What is the height of a Red-black tree with N nodes?
Express it in O( ) notation.
O(lg(N)) <- guaranteed
Q4: [2] Given a BST with N nodes, what would be its height in (a)
the worst case, (b) the best case? Express your answers in O( )
notation.
worst case O(N)
best case O(lgN)
- Q5: [2] Suppose we perform a right-rotate operation with respect
to two nodes X and Y on a BST T 1 and obtain BST T 2 . Next we
perform a left-rotate operation with the same two nodes on the
BST T 2 and obtain BST T 3 . Now, what differences or similarities
are there between the initial BST T 1 and the final BST T 3 ? - right rotate left rotate inverses of each other
- so T1 =T3
……………………………………………………………………………
QUIZ 2
Q1: [2] Why is the branching factor of a B-tree quite large?
Purpose of b tree to support large amount of data even going in to the disk, we want to keep disk accesses low, height of tree is large more disk accesses , if we can make the tree shorter we can reduce disk accesses, to reduce tree height and maintain same number of high data we need to increase branching factor.
Q2: [1] For a B-tree with N keys and min degree t, what is its
height?
lg N base t
Q3: [2] For a B-tree with N keys and min degree 4, what is the
(a) minimum, (b) maximum, number of keys a node can have?
2t-1 = 7
t-1 = 3
Q4: [1] In a splay-tree with N nodes, if M operations are
performed in sequence, what will be the total time taken?
M lgN
Q5: [4] Suppose we insert keys 1, 2, 3, 4, 5 in that order into (a) a
normal BST, and (b) a splay tree. In each case (a), (b), at the end,
what will be the (i) key in the root? (ii) height of the tree?
bst — root 1 — tree height 4–4 edges
splay — root 5–4 height
what happens with n nodes , time taken total
bst — keys are in increasing order , go all the way down and add it there , therefore time to add is proportional to height. traversing the tree all the way down just to add. O(n2)
splay — at everypoint insertion happens at top , as right child of root , we are not traversing whole tree , add at top and left rotate , which is constant time.
n * O(1) = O(n)
…………………………………………………………………………………
QUIZ 3
Q1: [2] What are the two reduction rules used to obtain an
ROBDD?
node x eliminated if both edges point to same thing
isomorphic subgraphs — same variable merge them together
• Q2: [2] What is meant by “BDDs are canonical representations of
logic functions”?
standard representation — for a given logic function representation is unique.
when u fix the ordering , unique bdd obtained
• Q3: [2] Express the Shannon’s expansion formula with respect to
the variable x2 for the function f(x1, x2, …,xn) of n variables. ….
f() = x2 . f(x1,1,…xn) + x2' .f (x2 , 0, ….,xn)
2 literals x and x’ logic and with cofactor of each situation
• Q4: [2] What is meant by “the variable ordering problem” in
BDDs?
bdd provide compact representations of even large complex functions.execution time of variable operations depend on bdd size . smaller bdd size is desirable. bdd size may differ according to the variable ordering , bad ordering may end up giving us a large bdd. better order can give us a smaller bdd. it will be good to find which variable. finding the correct ordering that gives us the smallest bdd size is hard and it is an np complete problem.
finding best ordering is hard
• Q5: [2] Give one benefit we gain by using negative edges in
BDDs
reduce the size of a bdd by 50%. size of bdd matters for operations
when we reduce size
in a function , f’(complement of f) is readily available , can get it in constant time.
…………………………………………………………………….
quiz 4
Q1: [4] Suppose we perform a task with M operations on a data structure that has size N. One operation takes 200N time, another operation takes 25N,
while each of the other operations take 1 unit of time.
– (a) [2] Based on the traditional worst-case analysis, what is the estimated total time for the task?
– (b) [2] What is the amortized cost per operation?
worst case: 200N * M (worst case cost to all operations)
amortized : (1*200N + 1*25N + (M-2) *1)/M
take all different costs of all operations , divide by # of ops
• Q2: [3] In the accounting method for amortized analysis, let the amortized cost and the actual cost of i-th operation be A_i and C_i, respectively. What is the key invariant to be maintained?
amortized cost > actual cost
summation A_i ≥ summation C_i (in the worst case equals)
should be true for any i value , after 5 operations encounter expensive operation , by then you should have accumulated enough money to spend for the expensive operation.
• Q3: [3] In the potential method for amortized analysis, what are the properties
that the potential function should satisfy?
Di is the data structure that results from i th operation
potential(D0) = 0
potential(Di) ≥ 0
………………………………………………………………………………………
QUIZ 5
Q1: Suppose we throw two fair (unbiased) 6-sided dice together,
each with numbers 1,…,6 on the sides. What will be the expected
value of the total (sum) of numbers rolled?
1/36 *( 1+2+..6) =21/6
• Q2: Suppose the input to an algorithm is an integer in the range 1–100, and every value in the range is equally likely. The algorithm takes 5s (seconds),10s, 20s and 30s to complete for the input ranges 1–10, 11–30, 31–70 and 71-100, respectively. What will be the average running time of the algorithm?
5*10/100 + 10 * 20/100 + ………….
• Q3: In HIRE-ASSISTANT algorithm, assuming that the n candidates are
presented in a random order, what is the probability that you hire:
– (a) exactly one time?
– (b) exactly n times?
1/n
1/n!
You will hire exactly one time if the best candidate is at first. There are (n−1)!orderings with the best candidate being at first, so the probability that you hire exactly one time is (n−1)!/n!=1/n
You will hire exactly n times if the candidates are presented in increasing order. There is only an ordering for this situation, so the probability that you hire exactly n times is 1/n!.
