|
Below are links to the written exercises: There is one exercise corresponding to each lecture. Once the exercise moves above the "Exercises below have not yet been updated for Spring 2011" part of the table, no significant changes will be made. All readings refer to Algorithms, 4th edition by R. Sedgewick and K. Wayne unless otherwise specified.
| # | DUE | EXERCISE | READING | ||
|---|---|---|---|---|---|
| 1 | 9/20 | Union Find | 1.5 | ||
| 2 | 9/27 | Analysis of Algorithms | 1.4 | ||
| 3 | 9/27 | Stacks and Queues | Intro to Programming, 4.3 | ||
| 4 | 10/4 | Elementary Sorts | 2.1 | ||
| 5 | 10/4 | Mergesort | 2.2 | ||
| 6 | 10/11 | Quicksort | 2.3 | ||
| 7 | 10/11 | Priority Queues | 2.4 | ||
| 8 | 10/18 | Binary Search Trees | 3.2 | ||
| 9 | 10/18 | Balanced Search Trees | 3.3 | ||
| 10 | – | Hash Tables | 3.4 | ||
| 11 | – | – | – | ||
| 12 | 3/21 | Undirected Graphs | 4.1 | ||
| 13 | 3/28 | Directed Graphs | 4.2 | ||
| 14 | 3/28 | Minimum Spanning Trees | 4.3 | ||
| 15 | 4/4 | Shortest Paths | 4.4 | ||
| 16 | 4/4 | String Sorts | 5.1 | ||
| 17 | 4/11 | Tries | 5.2 | ||
| 18 | 4/11 | Substring Search | 5.3 | ||
| 19 | 4/18 | Regular Expressions - Updated 4/14 | 5.4 | ||
| 20 | 4/18 | Data Compression | 5.5 | ||
| 21 | 4/25 | Maxflow | 6 (pages 886-902) | ||
| 22 | 4/25 | Linear Programming | LP article | ||
| 23 | – | Reductions/Intractability | 6 (pages 903-921) | ||
| 24 | – | Combinatorial Search | – | ||
| Exercises below have not yet been updated for Spring 2011 | |||||
Submission policy.
You must submit your solutions in writing.
Be sure to print your name, login, and precept number at the top of every
exercise you submit.
Lateness policy. Written exercises are due at the beginning of lecture on the date given. Late exercises will not be accepted without a University-sanctioned excuse or approval by a preceptor.
Grading policy. Grades on the problem set questions will be: 4 (correct), 3 (minor mistake), 2 (major mistake), 1 (low comprehension) or 0 (all wrong or not submitted). Also, some of the exam questions will be based on these exercises, so it is to your advantage to complete them in a timely manner.
In calculating your course grade, we will drop your lowest two non-zero exercise scores.
Collaboration policy. You are permitted to collaborate on the exercises, provided you work jointly in contributing to the solutions.
