Chittaranjan Tripathy 
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 indepth:
Instructor 
Chittaranjan Tripathy (please call me Chittu) email: chittu AT cs dot duke dot edu 
TA 
No TA 
Lectures 
LSRC D106, Mon.Tue.Wed.Thu 2:00PM3:15PM 
Recitations 
LSRC D106, Fri 2:00PM3:15PM 
Office Hours 
LSRC D240, Tue.Wed 3:30PM4:30PM 
Textbooks 
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. 
Prerequisites 
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 Inclass Closedbook Midterm Exam. [15 points] Second Inclass Closedbook Midterm Exam. [15 points] Inclass Closedbook 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 MSWord for typing the solutions to the assignments, and submit them in PDF or PS file format. If you prefer to handwrite them, then write the solutions clearly and legibly. Please note that short and tothepoint 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.
Week, Lecture(L)/Recitation(R) 
Homework Due 
Topics Covered/To be Covered 
References/Readings 

Week 1  L01  May 16, Wednesday  —  Introduction and Overview Administrativia History of Algorithms Models of Computation 
[DPV:0] 
L02  May 17, Thursday  Homework 01 out  Asymptotic Notation Solving Recurrences 
[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 Homogeneous Inhomogeneous 
[DPV:0] 
L04  May 22, Tuesday  —  DivideandConquer Algorithms Merge sort Powering a number Computing nth Fibonacci number Matrix multiplication – Naive algorithms – Strassen's algorithm 
[DPV:2] [CLRS:4]  
L05  May 23, Wednesday  —  Integer Multiplication Naive algorithms Karatsuba multiplication ToomCook generalization Polynomial Multiplication Naive algorithms Divideandconquer polynomial multiplication Introduction to Fast Fourier Transform (FFT) 
[DPV:2] [CLRS:30]  
L06  May 24, Thursday  Homework 01 due Homework 02 out Homework 02 out 
Fast Fourier Transform (FFT) Application of FFT to polynomial multiplication 
[DPV:2] [CLRS:30]  
R02  May 25, Friday  —  FFT Continued...  [DPV:2] [CLRS:30]  
Week 3  —  May 28, Monday  No Class Today  —  — 
L07  May 29, Tuesday  —  DivideandConquer in Computational Geometry Convex hulls in 2D Closest pair of points in 2D 
[CLRS:33] [additional notes given in class] 

L08  May 30, Wednesday  —  Randomized Algorithms Las Vegas Monte Carlo Atlantic City Quicksort Deterministic Randomized Analysis of running time Lower Bounds for ComparisonBased Sorting Algorithms 
[DPV:2] [CLRS:7,8] [Er:Lower Bounds]  
L09  May 31, Thursday  Homework 02 due Homework 03 out 
PruneandSearch: LinearTime Selection Randomized Deterministic 
[DPV:2] [CLRS:9] [Ed:3]  
R03  Jun 01, Friday  —  Binary Search Trees, RedBlack Trees  [CLRS:12,13] [Ed:7]  
Week 4  —  Jun 04, Monday  First Midterm Exam  Covers L01L09, R01R02  [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  [DPV:4] [CLRS:6,20,21]  
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 Representations Directed Graphs Breadthfirst search Depthfirst search 
[DPV:3] [CLRS:22]  
L16  Jun 13, Wednesday  —  Graphs Continued... Topological sort Strongly connected components 
[DPV:3] [CLRS:22]  
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]  
Week 6  
—  Jun 18, Monday  Second Midterm Exam  Covers L10L17, R03R04  [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 NPCompleteness  [DPV:9] [CLRS:35]  
Week 7  
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.