Chittaranjan Tripathy 
This undergraduate course, which is also colisted as a graduate level course for nonCS students (e.g. from Electrical and Computer Engineering, Computational Biology and Bioinformatics, Fuqua [Business] School), 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. This course covers the following topics indepth:
Instructor 
Chittaranjan Tripathy (please call me Chittu) email: chittu AT cs dot duke dot edu 
TA 
Sudhanshu Garg email: sgarg AT cs dot duke dot edu 
UTA 
Alessio Santoro email: alessio DOT santoro AT duke dot edu 
Lectures 
LSRC D106, Wed.Fri 10:05AM11:20AM 
Recitations 
LSRC D106, Mon 10:05AM11:20AM 
Office Hours 
Chittu: LSRC D301, Wed 3:30PM4:30PM, Thu 11:30AM12:30PM Sudhanshu: LSRC D229, Wed 5:00PM6:00PM, Thu 5:00PM6:00PM 
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 201 and 230, 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. Duke Honor Code applies to all the work you submit for evaluation. 
Writing and Submitting Assignments 
You are strongly encouraged to use LaTeX or other good word processor 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. 
Course Page, Email, Feedback 
Please check the course homepage frequently for any announcements, supplemental notes, readings, homework, etc. Important announcements will be sent by email. The following email id reaches every one in the class including the TAs and the instructor: compsci330 AT cs dot UniversityName dot edu. Please use this for posting general comments meant to be read by everyone in the class. Please use the instructor's or the TA's email id for specific questions. We welcome your suggestions and feedback on all aspects of the course. Your suggestions will improve the quality of the course. Please do not hesitate to provide your suggestions either in person, or via anonymous feedback. 
The schedule below is tentative (clearly not final before the day of the corresponding lecture). We will plan the individual lectures on weekly basis. The individual lectures will be added/modified/reprioritized 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  Aug 29, Wednesday  —  Introduction and Overview Administrativia History of Algorithms Models of Computation 
[DPV:0]  
L02  Aug 31, Friday  —  Asymptotic Notation Solving Recurrences 
Handwritten Note (L02) [DPV:0,2] [CLRS:3,4] For background on induction: [Er:Induction] 

Week 2  R01  Sep 03, Monday  —  More on Solving Recurrences  [DPV:2] [CLRS:4]  
L03  Spe 05, Wednesday  —  Solving Linear Recurrences Homogeneous Inhomogeneous 
Handwritten Note (L03) [DPV:0] 

L04  Sep 07, Friday  Homework 01 out  DivideandConquer Algorithms Merge sort Powering a number Computing nth Fibonacci number Matrix multiplication – Naive algorithms – Strassen's algorithm 
Handwritten Note (L04) [DPV:2] [CLRS:4] 

Week 3  R02  Sep 10, Monday  —  Problems on recurrences and Divideandconquer algorithms  Handwritten Note (L05) [DPV:2] [CLRS:4] 

L05  Sep 12, 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  Sep 14, Friday  Homework 01 due  Fast Fourier Transform (FFT) Application of FFT to polynomial multiplication 
Handwritten Note (L06) Examples [DPV:2] [CLRS:30] 

Week 4  R03  Sep 17, Monday  —  Problems on polynomials and FFT  [DPV:2] [CLRS:30]  
L07  Sep 19, Wednesday  —  DivideandConquer in Computational Geometry Convex hulls in 2D 
[DVP:2] [CLRS:33] [additional notes given in class] 

L08  Sep 21, Friday  Homework 02 out  DivideandConquer in Computational Geometry Convex hulls in 2D... Two Other Algorithms Graham Scan Jarvis's march (gift wrapping) 
[CLRS:12,13] [Ed:7]  
Week 5  R04  Sep 24, Monday  —  Problems on convex hulls, iNTro to probability  [CLRS:12,13] [Ed:7]  
L09  Sep 26, 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]  
L10  Sep 28, Friday  Homework 02 due Homework 03 out 
PruneandSearch: LinearTime Selection Randomized Deterministic 
[DPV:2] [CLRS:9] [Ed:3]  
Week 6  R05  Oct 01, Monday  —  Problems on randomized algorithms  —  
L11  Oct 03, Wednesday  —  Polynomial Identity Testing  
L12  Oct 05, Friday  — 
Number Theoretic Algorithms: Basics, Euclid's Algorithm  [DVP:1] [CLRS:31]  
Week 7  R06  Oct 08, Monday  Homework 03 due  Midterm1 review  
—  Oct 10, Wednesday  First Midterm Exam  Covers up to: PruneandSearch: LinearTime Selection  [Exam Information and Cheat Sheet]  
L13  Oct 12, Friday  —  ExtendedEuclid Algorithm, Modular Exponentiation  [DVP:1] [CLRS:31]  
Week 8  Oct 15, Monday  —  No Class: Fall Break  
L14  Oct 17, Wednesday  —  Primality Testing, RSA  [DVP:1] [CLRS:31] Handwritten Note: Number Theoretic Algorithms 

L15  Oct 19, Friday  —  Binary Search Trees, RedBlack Trees  [CLRS:12,13] [Ed:7] Handwritten Note: BSTs and RedBlack Trees 

Week 9  R07  Oct 22, Monday  Homework 04 out  Skip Lists  [Er:Skip Lists] Handwritten Note: Skip Lists 

L16  Oct 24, Wednesday  —  Amortized Analysis  [CLRS:17] [Er:Amortized Analysis] Handwritten Note: Amortized Analysis 

L17  Oct 26, Friday  —  Data Structures for Disjoint Sets  [DPV:4] [CLRS:6,20,21]  
Week 10  R08  Oct 29, Monday  —  Dynamic programming  [DPV:6] [CLRS:15] Handwritten Note: Dynamic Programming 

L18  Oct 31, Wednesday  Homework 04 due Homework 05 out 
Greedy Algorithms  [DPV:5] [CLRS:16] i Handwritten Note: Greedy Algorithms 

L19  Nov 02, Friday  —  Graphs Representations Directed Graphs Depthfirst search (DFS) Properties of DFS 
[DPV:3] [CLRS:22] Handwritten Note: DFS 

Week 11  R09  Nov 05, Monday  —  Graphs Continued... Topological sort Strongly connected components 
[DPV:3,5] [CLRS:15,22] Handwritten Note:SCC 

L20  Nov 07, Wednesday  Homework 05 due  Minimum Spanning Tree Algorithms Two Greedy Algorithms: Prim's Algorithm and Kruskal's Algorithm 
[DPV:3] [CLRS:22] Handwritten Note: MST 

L21  Nov 09, Friday  Homework 06 out  Minimum Spanning Tree Algorithms Continued... Shortest Paths in Graphs 
[DPV:5] [CLRS:23]  
Week 12  R10  Nov 12, Monday  —  Problems on MST and SP  [DPV:3,5] [CLRS:15,22]  
L22  Nov 14, Wednesday  —  Shortest Path Algorithms BellmanFord Algorithm Dijkstra's Algorithm Breadthfirst search (BFS) as simplified Dijkstra's Algorithm 
[DPV:4,6] [CLRS:24,25] Handwritten Note: SSSP 

—  Nov 16, Friday  Second Midterm Exam  Covers L13L21, R07R10  [Exam Information and Cheat Sheet]  
Week 13  R11  Nov 19, Monday  —  Allpairs Shortest Paths FloydWarshall algorithm Problems on shortest paths 
[DPV:4,6] [CLRS:24,25] Handwritten Note: APSP 

Nov 21, Wednesday  —  No Class: Thanksgiving break  
Nov 23, Friday  —  No Class: Thanksgiving break  
Week 14  R12  Nov 26, Monday  —  Problems on shortest paths  [DPV:8] [CLRS:34]  
L24  Nov 28, Wednesday  —  Intractability and NP Completeness, Reductions  [DPV:8] [CLRS:34]  
L25  Nov 30, Friday  Homework 06 due Homework 07 out 
More on Reductions  [DPV:9] [CLRS:35]  
Week 15  R13  Dec 03, Monday  —  Problems on Reductions  —  
L26  Dec 05, Wednesday  —  Coping with NPCompleteness Approximation Algorithms 
[DPV:8] [CLRS:34]  
L27  Dec 07, Friday  Homework 07 due  Approximation Algorithms... Review of the Course 
[DPV:9] [CLRS:35]  
Week 16  —  Satruday Dec 15 2:00 PM  5:00 PM Also see this 
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.
For background material in discrete mathematics and writing proofs, the following material can be useful:[LLM] E. Lehman, F. T. Leighton, and A. R. Meyer. Mathematics for Computer Science (MIT 6.042) . 2012.
[Ro] K. H. Rosen. Discrete Mathematics and Its Applications. 7th Edition; McGrawHill; 2011.
[Ve] D. J. Velleman. How to Prove It: A Structured Approach. 2nd Edition; Cambridge University Press; 2006.