| instructor: | Christopher Painter-Wakefield | |
| office: | Room D343, LSRC | |
| phone: | 919-660-6564 | |
| mail: | paint007@cs.duke.edu | |
| office hours: | Tu 11-Noon, Fri 3:30-5, and by appointment |
|
Monday |
Tuesday |
Wednesday |
Thursday |
Friday |
|
|
|
19 May Intro (notes) Homework 1 Assigned Read Chapters 0, 1 through section 1.2.
|
20 Asymptotic analysis (notes) |
21 Divide & Conquer, Recurrences (notes) Read 2.1 – 2.4
|
|
24 Sorting (notes) Homework 1 Due Read Herbert Edelsbrunner's notes on Quicksort and Order Statistics |
25 Quicksort Homework 2 Assigned |
26 Medians & Order Statistics Binary Search Trees (notes) |
27 Balanced BSTs: AVL Trees (notes) Read Herbert Edelsbrunner's notes on Heaps and Heapsort |
28 Heaps and Heapsort Quiz 1 |
|
31 Memorial Day - no class |
1 June Graphs: Depth First Search Read Chapter 3 Homework 2 Due Homework 3 Assigned |
2 Graphs: Connected Components, Topological Sorting
|
3 Graphs: Breadth First Search, Shortest Path Algorithms Read Chapter 4 |
4 Quiz 2 Greedy Algorithms; Spanning Trees Read Chapter 5 |
|
7 Minimum Spanning Tree Algorithms
|
8 Review Homework 3 Due |
9 Midterm |
10 Greedy Scheduling; Huffman Coding Read Herbert Edelsbrunner's notes on Greedy Algorithms |
11 Amortized Analysis; Union-Find Read Herbert Edelsbrunner's notes on Amortized Analysis Homework 4 Assigned |
|
14 Union-Find, continued |
15 Dynamic Programing; Longest Increasing Subsequence Read Chapter 6 Homework 4 Due |
16 Edit Distance; Knapsack Homework 5 Assigned |
17 Chain Matrix Multiplication; Planning |
18 Quiz 3 Read Sections 7.1 - 7.3 |
|
21 Maximum Flow |
22 Easy and Hard Problems Read Chapter 8 Homework 5 Due Homework 6 Assigned |
23 NP-Complete Problems; Reductions |
24
|
25 Approximation Algorithms Read Chapter 9 |
|
28 Wrap-up and Review Homework 6 Due |
29 no class |
30 no class |
1 July Final Exam 2-5 pm
|
|
Homeworks will generally be assigned each Tuesday and will be due the following Tuesday at the start of class. Late homework will be assessed a 50% penalty.
Homeworks will consist of two type of questions; basic questions must be answered by you alone, with no collaboration with classmates or assistance from other students or references outside the course materials. More challenging questions will be marked with an asterisk (*). For these questions, you may draw on any resources you wish, although I strongly encourage you to at least attempt them yourself first. Whatever resources you draw on, the write up must be your own. You may always consult with me on any questions regarding the homework.
Homework can be submitted electronically (PDF or PostScript only) or on paper. If you choose to submit electronically, please use LaTeX or some other appropriate software to ensure that equations are formatted properly. Paper submissions should be on unlined paper. Please include your name and the homework # at the top of the first page, and staple the pages together.
Quizzes and ExamsWe will have one midterm exam and a final exam. In addition, I will give a short quiz most Fridays. The quizzes will consist of 3 or 4 easy questions on the material in your reading and the previous week's homework; these are only worth a small percentage of your grade, and are mainly intended as a way of checking on your understanding of the material as we progress in the course.
Grading:All grades will be posted in Blackboard.
| Homework | 35% |
| Midterm exam | 30% |
| Final exam | 30% |
| Quizzes | 5% |
Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein.