- provide basic training in algorithm design for a future computer scientist and/or programmer, and
- expose future professionals in other disciplines to fundamental algorithmic paradigms.

Debmalya Panigrahi

LSRC D203

Email: debmalya@cs.duke.edu

Office Hours on

Teaching Assistants (TAs)

Reza Alijani

North 002

Email: alijani@cs.duke.edu

Office Hours on

Tianqi Song

North 208

Email: stq@cs.duke.edu

Office Hours on

Undergraduate Teaching Assistants (UTAs)

Jeremy Fox

Email: jeremy.daniel.fox@gmail.com

Office Hour on

Arun Ganesh

Email: ag310@duke.edu

Office Hour on

Billy Wan

Email: xw58@duke.edu

Office Hour on

Rex Ying

Email: zy26@duke.edu

Office Hour on

Haofeng Zhang

Email: h.z@duke.edu

Office Hour on

Mike Zhu

Email: mzhu22@gmail.com

Office Hour on

Lectures in

We will use Piazza for all correspondence and discussions related to the course. If you have a question about the course material or want to initiate a discussion, post it on Piazza allowing the entire class to view and participate in it. If you want to contact the course staff only, send a message via Piazza that is visible only to the relevant course staff.

- 5/5: The review sessions will be held tonight and tomorrow at 8-10 pm in North 311.
- 4/25: The deadline for HW6 is extended to the end of Wednesday 4/27.
- 4/13: The review session will be held tonight at 8-10 pm in LSRC B101.
- 4/12: Homework 6 is out.
- 4/12: Professor's office hour is cancelled today, instead Reza has an extra office hour at the same time in N002.
- 4/10: Homework 4 grades and solutions on Sakai.
- 4/7: Problem 2 in HW 5 has been changed.
- 4/6: The due date for Homework 5 changed to 4/19.
- 4/4: Mikes's office hour (April 5) canceled.
- 4/4: Jeremy's office hour rescheduled for 12-1 pm tomorrow (Tuesday, April 5) in the Link.
- 3/29: Homework 5 is out.
- 3/24: MST scribe note is updated.
- 3/22: Billy's office hours this Thursday will be 1:30-2:30pm
- 3/22: Problem 1 of HW4 is updated.
- 3/20: The deadline for Homework 4 exended to 3/29.
- 3/11: Homework 4 is out.
- 2/7: Homework 2 grades and solutions on Sakai.
- 3/6 Reza's office hour rescheduled for 9-10 am tomorrow (Monday, March 7) in North 002
- 2/24 Tianqi's office hour rescheduled for 7-8 pm at LSRC B101
- 2/24 Tianqi's office hour is cancelled due to tornado issue
- 2/23: Professor's office hour today at 4:30 - 5:30 will be in LSRC D344 instead of his office
- 2/21: Tianqi's office hour moved to 5:15-6:15 pm tomorrow (Monday, Feb 22).
- 2/18: Homework 3 is out.
- 2/18: Homework 1 grades and solutions on Sakai.
- 2/4: Homework 2 is out.
- 1/21: Homework 1 is out.
- 1/13: The recitation moved from Gross 103 to Gross 107.

- Introduction: History of Algorithms, Asymptotic and Worst-case Analysis
- Algorithm Design Techniques: Divide and Conquer (Recurrences), Dynamic Programming and Memoization, Greedy Algorithms
- Graph Algorithms: Graph Representations, Graph Traversal and Applications, Shortest Path, Minimum Spanning Tree, Network Flows
- Data Structures: Amortization and Potential Functions, Union-Find
- Computational Geometry: Convex hull
- Randomized Algorithms: Monte Carlo and Las Vegas Algorithms, Hashing
- Linear Programming: Simplex Algorithms, LP Duality
- Intractability: P and NP, NP-completeness, Polynomial-time Reductions, Approximation Algorithms

**COMPSCI 201 Data Structures and Algorithms****COMPSCI 230 Discrete Math for Computer Science**

- [DPV] S. Dasgupta, C. Papadimitriou, and U. Vazirani.
*Algorithms*. McGraw Hill, 2006. - [KT] J. Kleinberg and E. Tardos.
*Algorithm Design*. Addison Wesley, 2005. - [CLRS] T. Cormen, C. Leiserson, R. Rivest, and C. Stein.
*Introduction to Algorithms*. MIT Press, 2009.

- [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.

- Homework Assignments (six): 35%
- Midterm exams (two): 35%
- Final exam: 30%
- Both the midterms and the final exam will be in-class closed-book exams.

- Review the detailed guidelines on
collaboration.
**Any violation of these guidelines will be reported without exception to the relevant authorities.** - You will get 50% credit if you submit your homework within one week of the submission deadline, and no credit therefeafter.
In exceptional circumstances, you can contact the instructor
**before the submission deadline**to get an extension. Requests for extension are at the discretion of the instructor and can be refused. - We will use Sakai for homework submission.
- The homework solutions have to be typed. It is strongly encouraged that you prepare your homework submissions in LaTeX.
- Homework solutions must be submitted by 11:59 pm Durham (Eastern) time on the due date.
**Schedule**Homework 1 (Lectures 1-5) released on 1/21 due on 2/4 Homework 2 (Lectures 6-9) released on 2/4 due on 2/18 Homework 3 (Lectures 10-13) released on 2/18 due on ~~3/8~~3/10Homework 4 (Lectures 14-17) released on ~~3/8~~3/10due on ~~3/24~~3/29Homework 5 (Lectures 18-21) released on ~~3/24~~3/29due on ~~4/7~~~~4/12~~4/19Homework 6 (Lectures 22-25) released on ~~4/7~~4/12due on ~~4/26~~4/27

Lecture | Date | Topic | Scribe Notes | References |

Introduction |
||||

1 | Th 1/14 | History of Algorithms; Asymptotic Notation; Worst-case Analysis | Notes | DPV: 0, 2 KT: 2 CLRS: 1, 2, 3, 4 |

Algorithm Design Techniques |
||||

2 | Tu 1/19 | Divide and Conquer: Binary Search, Quick Sort, Merge Sort, Selection, Strassen's Matrix Multiplication | Notes | DPV: 2 KT: 5 CLRS: 4, 7, 8, 9, 28 |

3 | Th 1/21 | |||

4 | Tu 1/26 | Greedy Algorithms: Fractional Knapsack, Interval Scheduling, Huffman codes | Notes | DPV: 5 KT: 4 CLRS: 16 |

5 | Th 1/28 | |||

6 | Tu 2/2 | Dynamic Programming: Shortest Path in a DAG, Longest Increasing Subsequence, 0-1 Knapsack |
Notes | DPV: 6 KT: 6 CLRS: 15 |

7 | Th 2/4 | |||

Graph Algorithms |
||||

8 | Tu 2/9 | Graph Representations and Traversal: Depth First Search, Breadth First Search, Applications | Notes | DPV: 3 KT: 3 CLRS: 22 |

9 | Th 2/11 | |||

10 | Tu 2/16 | Shortest Path: Bellman-Ford, Dijkstra, All-Pairs Shortest Paths |
Notes | DPV: 4.6, 6.6 KT: 6.8 CLRS: 24.1, 25 |

11 | Th 2/18 | Network Flows: Maxflow Mincut Theorem, Augmenting Paths, Applications | Notes | DPV: 7 KT: 7 CLRS: 26 |

12 | Tu 2/23 | |||

Th 2/25 | Midterm 1: Lectures 1-12 |
|||

13 | Tu 3/1 | Minimum Spanning Tree: Kruskal, Prim | Notes | DPV: 5 KT: 4 CLRS: 16, 23 |

14 | Th 3/3 | Disjoint sets: Union by rank, amortized analysis: binary counters, the potential method | Notes | CLRS: 21 |

15 | Tu 3/8 | Disjoint sets: Path compression | CLRS: 17 | |

Randomized Algorithms |
||||

16 | Th 3/10 | Random processes: Birthday Paradox, Coupon Collector, Balls in Bins | Notes | DPV: virtual chapter KT: 13 CLRS: 5, 11 |

Tu 3/15, Th 3/17 | Spring Break: No Class |
|||

17 | Tu 3/22 | Las Vegas Algorithms | Notes | DPV: virtual chapter KT: 13 CLRS: 5, 11 |

18 | Th 3/24 | Monte Carlo Algorithms | ||

19 | Tu 3/29 | Hashing | Notes | DPV: virtual chapter KT: 13 CLRS: 5, 11 |

Linear Programming |
||||

20 | Th 3/31 | LP Formulations, Integer Linear Program | Notes | CLRS: 29 |

21 | Tu 4/5 | LP Duality | Notes | CLRS: 29 |

22 | Th 4/7 | LP Algorithms, Simplex Algorithms, Separation Oracles | ||

Computational Geometry |
||||

23 | Tu 4/12 | Convex Hull Algorithms Guest Lecturer: Dr. Kyle Fox |
Notes | CLRS: 33 |

Th 4/14 | Midterm 2: Lectures 13-23 |
|||

Intractability |
||||

24 | Tu 4/19 | Complexity Classes P and NP, Polynomial-time Reductions | Notes | DPV: 8 KT: 8 CLRS: 34 |

25 | Th 4/21 | Approximation Algorithms: Vertex Cover, Set Cover, TSP | Notes | DPV: 8, 9 KT: 8, 11 CLRS: 34, 35 |

26 | Tu 4/26 | LP Rounding | Notes | |

Sa 5/7 | Final Exam: All Lectures 2-5pm Time: Location: French Science 2231 |