Greedy Algorithms Flashcards
(10 cards)
what is the pedsucode for huffman codes
HUFFMAN(C):
1. n = |C| // Number of characters
2. Q = C // Priority queue of characters by freq
3. for i = 1 to n - 1:
4. allocate new node z
5. z.left = x = EXTRACT-MIN(Q)
6. z.right = y = EXTRACT-MIN(Q)
7. z.freq = x.freq + y.freq
8. INSERT(Q, z)
9. return EXTRACT-MIN(Q) // The root of the tree
what is the running time for huffman codes
Complexity: O(n log n) for n symbols, since you perform n - 1 INSERTs and EXTRACT-MINs
Build the Huffman Tree (Manual Simulation)
Generalize Huffman’s algorithm to ternary codewords (i.e., codewords using the
symbols 0, 1, and 2), and prove that it yields optimal ternary codes
TERNARY-HUFFMAN(C):
1. n = |C| // Number of characters
2. Q = C // Priority queue of characters by frequency
3. for i = 1 to n - 1:
4. allocate new node z
5. z.left = x = EXTRACT-MIN(Q) // Extract the node with the smallest frequency
6. z.middle = y = EXTRACT-MIN(Q) // Extract the second smallest frequency node
7. z.right = w = EXTRACT-MIN(Q) // Extract the third smallest frequency node
8. z.freq = x.freq + y.freq + w.freq // Sum of the frequencies of the three nodes
9. INSERT(Q, z) // Insert the newly created node back into the priority queue
10. return EXTRACT-MIN(Q) // Return the root of the ternary tree (final node)
what is the pedocode code for fractional knapsack?
Fractional - Knapsack (v,w,W)
load=0
i=1
while load<W and i<=n
if w_i <=W-load
take all of item i
else take (W-load)/w_i of item
add what was taken to load
what is running time for fractional knapsack
o(n)+0(nlogn) to sort
what is the psedocode for dynamic 0-1?
dynamic 0-1 knapsack(v,w,n,w)
let c[0…n,0…W] be a new array
for w = 0 to W
c[0,w]=0
for w =1 to W
if w_1 <= w
if v_i+c[i-1,w-w_i] > c[i-1,w]
c[i,w]=v_i+c[i-1,w-w_i]
else c[i,w]=c[i-1,w]
else c[i,w]=c[i-1,w]
what is the runiing time for 0-1 knapsack
O(NW)
Prove that the fractional knapsack problem has the greedy-choice property.
Show how to solve the fractional knapsack problem in O.n/ time