# CSCI 2300 Lecture Exercise 5

CSCI 2300 — Introduction to Algorithms

Lecture Exercise 5 (document version 1.0) — DUE July 16, 2020
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 frequen￾cies shown to the right, use the greedy al￾gorithm 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