Computer Science 431
Algorithms
Spring 2015, The College of Saint Rose
Lecture 25: Huffman Codes; Graph Algorithm Wrapup
Date: Monday, April 27, 2015
Agenda
- Announcements
- Wraup up Problem Set 8: Dijkstra's Road Trip and
More [HTML] [PDF] this week
- Final exam: 1:30-4:00, Tuesday, May 5. Focus on topics
since Exam 2, but a little of everything.
- Huffman codes
- Graph algorithm wrapup
- Floyd's algorithm
- A greedy algorithm: Prim's algorithm (as part of lecture assignment recap below)
- Lecture 23 assignment recap
- Lecture 24 assignment recap
Lecture 25 Assignment
Due at the start of class, Wednesday, April 29.
Please submit answers to these questions
in Submission
Box under "LA25" or in hard copy by the
start of our next class. We will discuss these questions at the
start of class, so no late submissions are accepted. Please be sure
that your name is clearly indicated in all submissions.
- Levitin Exercise 9.4.1, p. 342 (6 points)
Terminology
- Floyd's algorithm
- all sources shortest path problem
- greedy algorithms
- (minimum) spanning tree
- Prim's algorithm
Examples
Links