Home Page > > Details

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.

Contact Us(Ghostwriter Service)

- QQ：99515681
- WeChat：codinghelp
- Email：99515681@qq.com
- Work Time：8:00-23:00

- Ghostwriter Crc Programming,Help With ... 2020-10-27
- Algorithms Programmingghostwriter ,Hel... 2020-10-27
- Help With 158.225 Course Programming,G... 2020-10-27
- Gui Programminghelp With ,Ghostwriter ... 2020-10-27
- 70015 Programminghelp With ,Ghostwrite... 2020-10-27
- Ghostwriter Data Programming Course,He... 2020-10-27
- Comp9021help With ,Python Programmingd... 2020-10-27
- Ghostwriter 159.172 Programming,Help W... 2020-10-27
- Help With Program Programming,Python P... 2020-10-27
- Ghostwriter Fnce90045,Help With Java P... 2020-10-27
- Help With Spss|Help With Processing|Gh... 2020-10-27
- C++ Programmingdebug ,Cs 130Aghostwrit... 2020-10-27
- R Programminghelp With ,Ghostwriter Da... 2020-10-27
- Ghostwriter Ssci 599 Course,Help With ... 2020-10-27
- Cits1001help With ,Java Programmingdeb... 2020-10-26
- Ghostwriter Cfrm 542 Programming,R Cou... 2020-10-26
- Math2392help With ,Ghostwriter R Cours... 2020-10-26
- Help With Comp10002 Programming,Ghostw... 2020-10-26
- Math2392 Programmingghostwriter ,Data ... 2020-10-26
- Cse 320Help With ,Ghostwriter Programm... 2020-10-25

Contact Us - Email：99515681@qq.com WeChat：codinghelp

© 2014 www.asgnhelp.com

Programming Assignment Help！