Due Date: Friday Dec. 13th at 1:30 PM
Submit all homework problems on myWPI
See course policy regarding late homework submissions
Homework Instructions:
- For this homework you must study:
- Sections 16.1-16.3 of your textbook (Greedy Algorithms).
- Chapter 22 of your textbook (Graph Algorithms).
- Sections 24.1-24.3 of your textbook (Greedy Algorithms Shortest Paths in Graphs).
-
Graph Algorithms materials posted on this course's Lecture Notes webpage.
-
Greedy Algorithms materials posted on this course's Lecture Notes webpage.
- This is an individual homework. No collaboration is allowed.
-
SUBMISSION INSTRUCTIONS:
Submit all of your homework problem solutions on myWPI.
No need to submit hardcopies of your solutions.
- Remember to show your work and explain your answers.
Correct answers without complete explanations won't receive full credit.
Incorrect answers with explanations may receive partial credit.
- See the course webpage for
the late homework submission policy.
Homework Problems:
- (40 Points) Problem I.
Exercise 16.2-3 page 427 of your textbook.
Efficient algorithm: 20 points. Complexity analysis: 10 points.
Correctness argument: 10 points.
- (40 Points) Problem II.
Problem 16.5 page 449 of your textbook.
Part a: 20 points. Part b: 10 points. Part c: 10 points.
- (20 Points) Problem III.
Exercise 24.3-5 page 663 of your textbook.
Directed graph: 10 points. Showing that Dijkstra's algorithm
relaxes the edges of a shortest path in the graph out of order: 10 points.