| instructor: | Christopher Painter-Wakefield | |
| office: | Room D343, LSRC | |
| phone: | 919-660-6564 | |
| mail: | paint007@cs.duke.edu | |
| office hours: | Mon 3:30-5:00, by appointment, or whenever I'm in my office. |
|
Monday |
Tuesday |
Wednesday |
Thursday |
Friday |
|
|
|
18 May Intro (notes) Homework 1 Assigned Read Chapters 0, 1 through section 1.2.
|
19 Asymptotic Analysis (notes) Divide & Conquer Recurrence Relations (notes) |
20 Sorting (notes) Read Chapter 2.1-2.5
|
|
23 Quicksort Read Herbert Edelsbrunner's notes on Quicksort and Order Statistics |
24 Medians and Order Statistics Homework 1 Due Homework 2 Assigned |
25 Binary Search Trees (notes) Balanced BSTs: AVL Trees (notes) Read Herbert Edelsbrunners notes on Heaps and Heapsort |
26 Heaps and Heapsort Graphs: Depth First Search Read Chapter 3 |
27 Graphs: Depth First Search on Directed Graphs |
|
30 Memorial Day - no class |
31 Graphs: Connected Components, Topological Sorting Office hours: 11:00-1:00 |
1 June Graphs: Breadth First Search, Shortest Path Algorithms Read Chapter 4 Homework 2 Due Homework 3 Assigned |
2 Greedy Algorithms Read Herbert Edelsbrunner's notes on Greedy Algorithms |
3 Read Chapter 5.1 |
|
6 Minimum Spanning Trees
|
7 Exam Review Homework 3 Due
|
8 Midterm |
9 Amortized Analysis; Union-Find Read Herbert Edelsbrunner's notes on Amortized Analysis
|
10 Union-Find, continued; Huffman Coding Read Chapter 5.2 Homework 4 Assigned |
|
13 Dynamic Programming; Longest Increasing Subsequence Reach Chapter 6 |
14 Edit Distance; Knapsack Homework 4 Due |
15 Chain Matrix Multiplication Homework 5 Assigned Additional files for homework 5 |
16 Maximum Flow; Bipartite Matching Read Chapter 26.1 – 26.3 in the optional text or read Herbert Edelsbrunner's notes on Maximum Flow; read chapter 7.3 |
17 Linear Programming Read Chapter 7.1-7.3 |
|
20 Easy and Hard Problems (notes) Read Chapter 8 |
21 NP-Complete; Reductions Homework 6 Assigned Homework 6 Answers |
22 Homework 5 Due Class meets in D344 |
23 Approximation Algorithms Read Chapter 9 Class meets in D344 |
24 |
|
27 Exam Review |
28 no class |
29 no class |
30 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 and can be turned in anytime before the last day of class.
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.