CSCI 2300代写、Algorithms代写、Python，Java，c/c++程序语言代做

日期：2020-07-18 11:15

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 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.