Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Lecture Exercise 5 (document version 1.0)
Greedy Algorithms (Part Two)
This lecture exercise is to be completed and submitted by 11:59PM EDT on the due date
shown above.
This lecture exercise is to be completed individually. Do not share your work or answers
with anyone else.
For all lecture exercises, take the time to work through the corresponding video lectures to
practice, learn, and master the material. While the questions posed here are usually not
very difficult, they are important to understand before attempting to solve the more difficult
problems.
1. For the undirected weighted graph shown to
the right (Figure 5.9 of DPV; also from the
Prim’s Algorithm slide for July 12), show
the set of edges Ereq that will always be part
of any minimum spanning tree T for this
graph.
2. Again for the undirected weighted graph shown above (Figure 5.9 of DPV), which vertex (or
if multiple possibilities, which vertices) must we start from to guarantee that both Prim’s
Algorithm and Kruskal’s Algorithm select the same edges in the same order and therefore
produce the same minimum spanning tree.
If there is a “tie” in selecting the next edge, always select the edge with endpoint vertices
closer to the beginning of the alphabet.
3. For the table of symbols and relative frequencies
shown to the right, use the greedy algorithm
we covered in lecture to construct
an optimal Huffman encoding tree. Be sure
to use the same notation shown in lecture
(i.e., label leaf vertices accordingly and use
square brackets).
Symbol Frequency
---------------------------
Q 70 million
R 45 million
S 50 million
T 60 million
---------------------------
What to submit
Please submit a single PDF file called upload.pdf that neatly contains answers to the above
questions. You may include hand-drawn graphs and diagrams, etc. Be sure your answers are
clearly marked and concisely described.