This undergraduate course covers the basic techniques for designing algorithms and data structures for a wide range of problems, and analyzing their time and space complexity. The emphasis of this course is on problem solving, algorithm design and analysis, not on programming. The course covers the following topics in-depth:
Chittaranjan Tripathy (please call me Chittu)
email: chittu AT cs dot duke dot edu
||LSRC D106, Mon.Tue.Wed.Thu 2:00PM-3:15PM|
||LSRC D106, Fri 2:00PM-3:15PM|
||LSRC D240, Tue.Wed 3:30PM-4:30PM|
Required: [DPV] Algorithms. S. Dasgupta, C. Papadimitriou and U. Vazirani.
Optional: [CLRS] Introduction to Algorithms, Third Edition. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein.
Either CPS 100 and 102, or equivalent courses, or prior knowledge of discrete mathematics, probability, and programming; else, talk to the instructor.
|Workload and Grading
Class Interaction. [5 points] |
Weekly Homework Assignments. [30 points]
First In-class Closed-book Midterm Exam. [15 points]
Second In-class Closed-book Midterm Exam. [15 points]
In-class Closed-book Final Exam. [35 points]
|Late Homework Policy
||No credits for late submissions.|
|Collaboration on Homework Assignments and the Duke University Honor Code
||You will learn the most if you solve as many extra problems as you can. All homework assignment solutions submitted for grading purpose should be your own. You are encouraged to form small groups to discuss and solve the problems from the textbooks or homework assignments, but you must write up your own solutions. Please indicate clearly in your solution sheet who you collaborated with, or what other written material (not listed in the course website) you have consulted, in order to solve each homework problem. You may not consult solutions on the internet or any other electronic sources.|
|Writing and Submitting Assignments
||You are strongly encouraged to use LaTeX or MS-Word for typing the solutions to the assignments, and submit them in PDF or PS file format. If you prefer to hand-write them, then write the solutions clearly and legibly. Please note that short and to-the-point answers often get more credits than long and rambling answers.|
We will plan the individual lectures on weekly basis. The individual lectures will be added (weekly) as the course progresses. Please check back often to get the latest schedule.
Topics Covered/To be Covered
|Week 1||L01||May 16, Wednesday||—|| Introduction and Overview
History of Algorithms
Models of Computation
|L02||May 17, Thursday||Homework 01 out|| Asymptotic Notation
| [DPV:0,2] [CLRS:3,4]
For background on induction: [Er:Induction]
|R01||May 18, Friday||—||More on Solving Recurrences||[DPV:2] [CLRS:4]|
|Week 2||L03||May 21, Monday||—|| Solving Linear Recurrences
|L04||May 22, Tuesday||—|| Divide-and-Conquer Algorithms
Powering a number
Computing nth Fibonacci number
– Naive algorithms
– Strassen's algorithm
|L05||May 23, Wednesday||—|| Integer Multiplication
Divide-and-conquer polynomial multiplication
Introduction to Fast Fourier Transform (FFT)
|L06||May 24, Thursday|| Homework 01 due
Homework 02 out Homework 02 out
| Fast Fourier Transform (FFT)
Application of FFT to polynomial multiplication
|R02||May 25, Friday||—||FFT Continued...||[DPV:2] [CLRS:30]|
|Week 3||—||May 28, Monday||No Class Today||—||—|
|L07||May 29, Tuesday||—|| Divide-and-Conquer in Computational Geometry
Convex hulls in 2D
Closest pair of points in 2D
[additional notes given in class]
|L08||May 30, Wednesday||—|| Randomized Algorithms
Analysis of running time
Lower Bounds for Comparison-Based Sorting Algorithms
|[DPV:2] [CLRS:7,8] [Er:Lower Bounds]|
|L09||May 31, Thursday|| Homework 02 due
Homework 03 out
| Prune-and-Search: Linear-Time Selection
|[DPV:2] [CLRS:9] [Ed:3]|
|R03||Jun 01, Friday||—||Binary Search Trees, Red-Black Trees||[CLRS:12,13] [Ed:7]|
|Week 4||—||Jun 04, Monday||First Midterm Exam||Covers L01-L09, R01-R02||[Exam Information and Cheat Sheet ]|
|L11||Jun 05, Tuesay||—||Skip Lists||[Er:Skip Lists]|
|L12||Jun 06, Wednesday||—||Amortized Analysis||[CLRS:17] [Er:Amortized Analysis]|
|L13||Jun 07, Thursday|| Homework 03 due
Homework 04 out
| Priority Queue Data Structures |
Data Structures for Disjoint Sets
|R04||Jun 08, Friday||—||Dynamic Programming||[DPV:6] [CLRS:15]|
|Week 5||L14||Jun 11, Monday||—||Greedy Algorithms||[DPV:5] [CLRS:16]|
|L15||Jun 12, Tuesay||—|| Graphs
|L16||Jun 13, Wednesday||—|| Graphs Continued...
Strongly connected components
|L17||Jun 14, Thursday|| Homework 04 due
Homework 05 out
|Minimum Spanning Tree Algorithms||[DPV:5] [CLRS:23]|
|R05||Jun 15, Friday||—||Shortest Path Algorithms||[DPV:4,6] [CLRS:24,25]|
|—||Jun 18, Monday||Second Midterm Exam||Covers L10-L17, R03-R04||[Exam Information and Cheat Sheet]|
|L18||Jun 19, Tuesay||—||Shortest Path Algorithms Continued...||[DPV:4,6] [CLRS:24,25]|
|L19||Jun 20, Wednesday||—||Intractability and NP Completeness||[DPV:8] [CLRS:34]|
|L20||Jun 21, Thursday|| Homework 05 due
Homework 06 out (will not be graded)
|Intractability and NP Completeness Continued...||[DPV:8] [CLRS:34]|
|R06||Jun 22, Friday||—||Coping with NP-Completeness||[DPV:9] [CLRS:35]|
|L21||Jun 25, Monday||—|| Advanced Topics
Review of the Course
|—||Jun 28, Thursday||Final Exam||Covers Everything||[Exam Information and Cheat Sheet]|
[CLRS] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2009.
MIT Video Lectures on Introduction to Algorithms Course
[KT] J. Kleinberg and Éva Tardos. Algorithm Design. Addison Wesley, 1 edition, 2006.
[AHU] A. Aho, J. Hopcroft, and J. Ullman. Design and Analysis of Algorithms. Addison Wesley, 1974.
[Ed] H. Edelsbrunner. CPS230 Lecture Notes. Duke University, 2008.
[Er] J. Erickson. CPS473G: Algorithms Lecture Notes. UIUC.
[Ta] R. E. Tarjan. Data Structures and Network Algorithms. Society for Industrial Mathematics, 1987.
[BB] G. Brassard and P. Bratley. Fundamentals of Algorithmics. Prentice Hall; 1996.