Here is a list of frequently asked questions about the course.
Although you may discuss the general approach to solving a problem with other people, you should not discuss the solution in detail. You must not take any written notes away from such a discussion. Also, you must list on the cover page of your solutions any people with whom you have discussed the problems. The solutions you hand in should be your own work. While writing them, you may look at the course textbook and your own lecture notes but no other outside sources.
Homework exercises | 10% |
Quiz | 5% |
Test #1 | 20% |
Test #2 | 20% |
Exam | 45% |
First class | Thursday, September 10 |
Quiz in CLH C | Thursday, October 1 |
Thanksgiving Day (no class) | Monday, October 12 |
Test 1 in CLH C | Thursday, October 15 |
Reading Day (no class) | Thursday, October 29 |
Last date to drop course without receiving a grade | Monday, November 9 |
Test 2 in CLH C | Thursday, November 19 |
Bonus quiz | Thursday, December 3 |
Last class | Monday, December 7 |
Exam period | December 9-23 |
Date | Topics | Reading in CLRS (3rd ed) | Suggested questions, mostly from CLRS (3rd ed) |
September 10 | Background Math | Chapter 3 and handout | Review questions and 3.1-1 to 3.1-6, 3.2-2, 3.2-7, 3-3(a), 3-4(a to d); see also chapter 2 and 3 of Parberry's book |
September 14 | Introduction | 1 | 1-1 |
September 16 | Proving correctness of recursive algorithms, divide and conquer | 2.3, 31.2 (up to Lame's Theorem), 4.0, 4.1 | 2-1, 31.2-4, 31.2-8, 4.1-1, 4.1-5; see also chapter 5.2 and 7 of Parberry's book |
September 23 | Proving correctness of loops | 2.1, 2.2 | 2.1-3, 2.1-4, 2.2-2, 2-2, 2-3; see also chapter 5.1 of Parberry's book |
October 5 | More divide and conquer, analysing running time of recursive algorithms | 4.2-4.5, 33.4, skim 4.6 | 2.3-3, 2.3-4, 2.3-6, 2.3-7, 4.2-3, 4.2-7, 4.3-1, 4.3-6, 4.4-2, 4.5-1, 4.5-4, 4-1, 4-2, 33.4-1, ; see also chapter 4 of Parberry's book |
October 14 | Sorting | pages 147-189 (a lot of this will be a review) | 6.1-1 to 6.1-7, 6.2-3, 6.2-6, 6.4-2, 6.4-3, 6.4-4, 6.5-4, 6.5-5, 6.5-8, 6-2, 7.2-4, 7.3-1, 7-1, 7-2 |
October 19 | Selecting kth smallest element from unsorted array | 9.1, 9.3 (and skim 9.2) | 9.1-1, 9.3-1, 9.3-5, 9.3-6, 9.3-7, 9.3-8, 9-1 |
October 21 | Sorting lower bound and sorting in linear time | All of chapter 8 | 8.1-1, 8.2-4, 8.3-1, 8.3-2, 8.3-3, 8.3-4, 8.4-4, 8-4 |
October 26 | Dynamic Programming | All of chapter 15 | 15.1-1 to 15.1-5, 15.2-2, 15.2-6, 15.3-2 to 15.3-6, 15.4-2, 15.4-5, 15-2 (in linear time), 15-5, 15-6, 15-9, 15-10, 15-11 |
November 9 | Greedy Algorithms | 16.1, 16.2 | 16.1-2, 16.1-3, 16.1-4, 16.2-1, 16.2-3, 16.2-5, 16.2-7 |
November 11 | Greedy Algorithms, including MST algorithms | 16.3, 23, 21.1-21.2 (for implementation of Prim's algorithm) | 16.3-1, 16.3-3, 16.3-4, 16.3-7, 16.3-9, 16-2, 16-4(a), 16-5(a,c), 23.1-1, 23.1-4, 23.1-6, 23.1-7, 23.2-2, 23.2-4, 23.2-5, 23.2-8, 23-4, 21.1-3, 21.2-2, 21.2-5, 21.2-6, |
November 18 | Graph Algorithms | 25.1, 25.2, 22 | 25.1-6, 25.1-7, 25.1-8, 25.2-4, 25.2-5, 25-1(a,b), 22.1-5, 22.2-6, 22.2-9, 22.3-2, 22.3-5, 22.3-7, 22.3-9, 22.4-3, 22.4-5, 22.5-1, 22.5-2, 22-2, 22-3, 22-4 |
November 30 | More Graph Algorithms | 24.0, 24.3 | 22.4-3, 22.4-5, 22.5-1, 22.5-2, 22-2, 22-3, 22-4, 24.3-1 to 24.3-4, 24.3-6, 24.3-8 |
December 2 | NP-completeness | 34.0-34.2 | 34.1-1, 34.1-5 |
Updated December 28, 2015