Midterm Flashcards
Preparation for the mid-term (18 cards)
When are Fibonacci trees used?
Constructing a priority queue with excellent amortized complexity for DECREASE-KEY
Dynamic optimality is a concept involving the comparison of
An online data structure to an offline data structure.
Suppose you already have 16 different coupons when there are 20 coupon types. What is the expected number of boxes
for obtaining a coupon different from the 16 you already have?
5
If the universe size at the root of a van Emde Boas tree is u, then the number of children is:
sqrt(u)
To support computing prefix sums of all keys that are no larger than some query key, an augmented binary search tree
stores the following at every node:
the sum of all keys in the left subtree
Which Fibonacci heap operation has Θ(log n) worst-case actual cost?
FIB-HEAP-DECREASE-KEY
What is the main contribution of leftist heaps?
The UNION is computed in Ο(logn) time
The number of potential probe sequences when using linear probing with a table with m entries (m is prime) is
m
Which of the following is not true regarding the amortized analysis of binary tree traversals.
SUCC had an amortized cost of 2.
data structure is not used to implement a dictionary?
Self organizing list
The reason for marking nodes in a Fibonacci heap is:
to indicate nodes that have lost a child since becoming a child themselves
If a Fibonacci tree appears as a subtree of an AVL tree, which nodes would be assigned a balance factor of 0?
None of them
The main difference between MTF and OPT for self-organizing linear lists is:
OPT is given the entire request sequence in advance, while MTF receives the requests one-at-a-time
To reduce the probability of having any collisions to < 0.5 when hashing n keys, the table should have at least this number
of elements.
n ln n
Harmonic numbers
Sum of the reciprocals
Load factor calculation
Number items / Array size
What is the golden ration?
(1+sqrt(5)) / 2 == 1.6
factorial formula for n choose k
n! / k! (n - k)!
