Greedy Algorithms Flashcards

(10 cards)

1
Q

what is the pedsucode for huffman codes

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

what is the running time for huffman codes

A

Complexity: O(n log n) for n symbols, since you perform n - 1 INSERTs and EXTRACT-MINs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Build the Huffman Tree (Manual Simulation)

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

what is the pedocode code for fractional knapsack?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

what is running time for fractional knapsack

A

o(n)+0(nlogn) to sort

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

what is the psedocode for dynamic 0-1?

A

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]

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

what is the runiing time for 0-1 knapsack

A

O(NW)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Prove that the fractional knapsack problem has the greedy-choice property.

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Show how to solve the fractional knapsack problem in O.n/ time

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly