This course will cover the basic techniques in algorithm design, including greedy algorithms, divide-and-conquer, amortization, dynamic programming, hashing, randomization, and NP-Completeness. The techniques will be covered in-depth, and the focus will be on modeling and solving problems using these techniques.
I will assume prior knowledge of discrete mathematics, probability, and programming. You should meet me if you do not have this background. The emphasis is on abstraction, design, and analysis and NOT on programming.
Please use Piazza for Dicussion.
Textbooks:
[DPV] Algorithms
by S. Dasgupta, C. Papadimitriou, and U. Vazirani (Please click the link for a free draft).
[KT] Algorithm Design
by J. Kleinberg and E. Tardos (Optional).
[CLRS] Introduction to Algorithm Design
by T. Cormen, C. Leiserson, R. Rivest and C. Stein (Optional).
There will be 2 in-class exams of 100 points each (A,B)
The best 4 out of 5 homeworks will be worth a total of 100 points (C)
The final exam is of 200 points (D)
The final grade will be A + B + C + D for a total of 500 points.
All Assignments will be posted on Sakai.
Submission: Homeworks should be turned in at the beginning of the class on the day it is due.
LATE PENALTY: Seven points per day.
Collaboration: You may *NOT* share written work. To know more about What's OK and What's not OK in this class, please check the Honesty Matrix modified from the original one created by Prof. Ron Parr in our department.
Practice: In general, solve as many extra problems as you can. This course is all about developing problem solving skills, so the more you practice on your own, the better. So I strongly encourage you to form groups of 2-3 students, in order to discuss and solve extra problems from the textbooks. One member of the team should grade the other's solutions.
Note: The schedule might change frequently. Please always check the web page for the newest schedule.
| Lecture # | Date | Topics | Reference |
|---|---|---|---|
| 1 | Aug. 27 |
First example: Fibonacci numbers Time and Space Divide and Conquer, Memoization, and Dynamic Programming |
[DPV: 0.2, 2, 6] |
| 2 | Aug. 29 |
Asymptotic analysis of running times Dynamic Programming: Knapsack |
[DPV: 0.3, 6.4] |
| 3 | Sep. 3 |
Divide and Conquer: Mergesort Solving recurrence relations (master theorem) |
[DPV: 2.2, 2.3] |
| 4 | Sep. 5 |
Non-comparative Sorting Algorithms: Counting sort and Radix sort (LSD and MSD) |
[CLRS: 8.2, 8.3] |
| 5 | Sep. 10 |
Quicksort, Randomized Linear Selection, Deterministic Linear Selection |
[DPV: 2.4, KT: 13.5, CLRS: 7, 9.2, 9.3] |
| 6 | Sep. 12 |
Binary Search Binary Search Trees |
[DPV: 2.2, 6, KT: 2.3, 4.8, CLRS: 12, 13] |
| 7 | Sep. 17 |
Balanced Search Trees: Top-Down 2-3-4 Search Trees Splay Trees |
[CLRS: 18.1] | 8 |
Sep. 19 |
Amortized Analysis of Splay Trees |
[
Lecture Note and Recitation Note from Cornell] |
| 9 |
Sep. 24 |
Amortized Analysis with
the Potential Method Stacks and Heaps | [DPV: 4.4.3, 4.5 CLRS: 17.3] |
| 10 |
Sep. 26 |
Heaps: Continued Graph Representations: Adjacency Matrix and Adjacency List Breadth-First Search |
[DPV: 3.1, 4.2, 4.5] |
| 11 |
Oct. 1 |
Breadth-First Search: Continued Depth-First Search |
[DPV:4.2, 3.2, 3.3] |
| 12 |
Oct. 3 |
Guest Lecture:
Prof. Debmalya Panigrahi Depth-First Search: Continued Properties of the BFS and DFS solutions Dijkstra's Algorithm, Implementation using Heaps The Minimum Spanning Tree (MST) Problem: Cut and Cycle Properties Kruskal's and Prim's Algorithms |
[DPV:3.2, 3.3, 4.4, 4.5, 5.1] |
| 13 |
Oct. 8 |
Disjoint Sets An Application of Disjoint Sets: Connected Components Data Structures for Disjoint Sets: Linked List, Union by Rank, Path Compression Kruskal's Algorithm for MST: Continued |
[DPV:3.4, 5.1] |
| 14 | Oct. 10 | EXAM 1 (Lectures 1 - 10) | |
| FALL BREAK |
|||
| 15 |
Oct. 17 |
Guest Lecture:
Prof. Kamesh Munagala Divide and Conquer: Closest pair of points in 2-D |
[DPV:2, KT:5.4, CLRS:33.4] |
| 16 | Oct. 22 |
Guest Lecture:
Prof. Pankaj K. Agarwal Convex Hull Algorithms: Graham Scan, Gift Wrapping |
[CLRS:33.3] |
| 17 |
Oct. 24 |
Integer and Matrix Multiplication |
[DPV:2.1, 2.5] |
| 18 |
Oct. 29 |
Polynomial Multiplication and Fast Fourier Transform | [CLRS:30, DPV:2.6, Lecture Note from Iowa State University] |
| 19 | Oct. 31 | Lower bounds on Sorting Algorithms and Convex Hull Algorithms | [DPV:2.3 (page 62) CLRS:8.1, 33.3] |
| 20 | Nov. 5 |
Randomization: Linearity of Expectation Randomized Algorithms: Quicksort with random pivot Quickselect with random pivot |
[CLRS:7.3, 9.2, Lecture Notes from Yale (Sections 1.3, 3.4.1, 3.6.3, 3.6.4)] |
| 21 |
Nov. 7 |
Quickselect with random pivot: Continued A Monte Carlo algorithm: Karger's algorithm for minimum cut of undirected graph |
[DPV:6 (page 150), Lecture Notes from Yale (Sections 1.4, 2.3.1.2)] |
| 22 |
Nov. 12 | EXAM 2 (Lectures 10-13) |
|
| 23 |
Nov. 14 |
Parallel Algorithms | [ Prof. Bruce Maggs' paper] |
| 24 |
Nov. 19 |
Parallel Algorithms: Continued | [ Prof. Bruce Maggs' paper] |
| 25 |
Nov. 21 |
Two ways to use reductions Defnitions of P and NP based on search problems NP-Completeness and NP-Hardness SAT and 3SAT |
[DPV:8] |
| 26 |
Nov. 26 |
Approximation algorithms: Greedy Algorithm for Set Cover Christofides' Algorithm for TSP |
[DPV:9.2, 5.4, Leture Note from Sapienza University of Rome] |
| THANKSGIVING RECESS |
|||
| 27 | Dec. 3 |
Competitive Analysis for Online Algorithms: 2-Competitive Algorithm for Ski-rental Problem k-Competitive LRU Algorithm for Paging Problem |
[DPV:9] |
| 28 | Dec. 5 | TBD | |
| Friday, Dec. 13 |
2:00PM - 5:00 PM: FINAL EXAM |
