- 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

Graduate Teaching Assistants (TAs)

Sam Haney

LSRC D122

Email: shaney@cs.duke.edu

Office Hours on

Nat Kell

LSRC D122

Email: kell@cs.duke.edu

Office Hours on

Kevin Sun

North 003

Email: ksun@cs.duke.edu

Office Hours on

Undergraduate Teaching Assistants (UTAs)

Xingyu Chen

Email: xingyu.chen@duke.edu

Office Hours on

Feng Gui

Email: feng.gui@duke.edu

Office Hours on

Katherine Guo

Email: katherine.guo@duke.edu

Office Hours on

Aninda Manocha

Email: aninda.manocha@duke.edu

Office Hours on

Vinit Ranjan

Email: vinit.ranjan@duke.edu

Office Hours on

Erin Taylor

Email: erin.c.taylor@duke.edu

Office Hours on

Haofeng (Fred) Zhang

Email: h.z@duke.edu

Office Hours on

Yumin Zhang

Email: yumin.zhang@duke.edu

Office Hours on

Lectures

Section 01D:

Section 02D:

Section 03D:

Section 04D:

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.

- Nat will hold extra office hours on 4/26 at 5 - 8 pm, and Kevin will hold extra office hours on 4/27 at 3 - 6 pm, both in North 306.
- There will be no office hours on 4/25, due to LDOC. Instead, Kevin, Aninda, and Erin will have office hours on 4/24 at 4:30 - 6:30 pm in North 306 (the usual room).
- Kevin and Nat will be holding extra office hours on Tuesday 3/20 at 6 - 9 pm, in North 306.
- In addition to his usual office hour (on 3/19), Prof. Panigrahi will have an office hour on Wednesday 3/21 at 3 - 4 pm.
- Prof. Panigrahi will not have office hours on 3/5.
- Prof. Panigrahi will not have office hours on 2/26. Instead, Kevin's office hours on 2/26 will start at 3:30 pm, in North 306.
- Kevin's 1/29 office hour (4 - 5 pm) will be moved to 25 minutes before and after his recitation on 1/26, in Social Sciences 136.
- Due to the school closings, the due date for Homework 1 has been changed from 1/22 to 1/24.
- In case any of you cannot access Sakai or Piazza, please email Kevin (ksun@cs.duke.edu) or Nat (kell@cs.duke.edu) immediately.
- No class on Monday 1/15 because of MLK day (university holiday).

- 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 (11 required (need to be submitted) + 1 for practice (should not be submitted)): 35%
- Midterm exams (two): 35%
- Final exam: 30%
- Both the midterms and the final exam will be in-class closed-book exams.

**Collaborations and Honesty:**Review the detailed guidelines on collaboration.**Any violation of these guidelines will be reported without exception to the relevant authorities.**This has led to disciplinary action in the past, so better be safe than sorry.**Late Submissions:**Homework solutions must be submitted by 11:59 pm Durham (Eastern) time on the due date. You will get no credit if you submit your homework after the submission deadline. A submission will be considered late if the submission website (Sakai) marks it as late. This means that it is in your best interest to submit sufficiently early so that there is no possibility of the Sakai server receiving it after 11:59 pm.**Extensions:**In exceptional circumstances, you can contact the instructor**before the submission deadline**to request an extension. You should send an email to the instructor if you are requesting an extension, with a clearly stated reason for your request. Requests for extension are at the discretion of the instructor and may be refused. This implies that last-minute requests for extension are at your own peril, since the original deadline will stand if the request is denied. Only the written consent of the instructor granting an extension will be considered valid. Nobody other than the instructor (TA, UTA, etc.) is authorized to grant an extension.**Submission Website:**We will use Sakai for homework submission.**Submission Format:**The homework solutions have to be typed. It is strongly encouraged that you prepare your homework submissions in LaTeX.**Schedule**

Homework 1 released on 1/15 due on ~~1/22~~1/24Homework 2 released on 1/22 due on 1/29 Homework 3 released on 1/29 due on 2/5 Homework 4 released on 2/5 due on 2/12 Homework 5 released on 2/12 due on 2/26 Homework 6 released on 2/26 due on 3/5 Homework 7 released on ~~3/5~~3/6due on ~~3/19~~3/21Homework 8 released on 3/19 due on 3/26 Homework 9 released on 3/26 due on 4/2 Homework 10 released on 4/2 due on ~~4/16~~4/18Homework 11 released on ~~4/16~~4/17due on 4/25 Homework 12 released on ~~4/25~~4/24Optional

Lecture | Date | Topic | Scribe Notes | References |

Introduction |
||||

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

Algorithm Design Techniques |
||||

Mo 1/15 | Martin Luther King, Jr. Holiday: No class | |||

We 1/17 | School closed due to snow | |||

2 | Mo 1/22 | Divide and Conquer: Binary Search, Quick Sort, Merge Sort, Integer Multiplication, Linear-time Selection. | Notes | DPV: 2 KT: 5 CLRS: 4, 7, 8, 9, 28 |

3 | We 1/24 | |||

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

5 | We 1/31 | |||

6 | Mo 2/5 | Dynamic Programming: Longest Increasing Subsequence, 0-1 Knapsack, Maximal Independent Set on Trees |
Notes | DPV: 6 KT: 6 CLRS: 15 |

7 | We 2/7 | |||

Graph Algorithms |
||||

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

9 | We 2/14 | |||

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

We 2/21 | Midterm 1: Lectures 1-10 |
|||

11 | Mo 2/26 | Minimum Spanning Tree: Kruskal, Prim, Union-Find Data Structure | Notes | DPV: 5 KT: 4 CLRS: 16, 23 |

12 | We 2/28 | |||

13 | Mo 3/5 | Amortization and Potential Method | Notes | DPV: 5 CLRS: 17 |

14 | We 3/7 | Network Flows: Augmenting Paths Algorithm, Max-Flow Min-Cut Theorem | Notes | DPV: 7 KT: 7 CLRS: 26 |

Mo 3/12, We 3/14 | Spring Break: No Class |
|||

15 | Mo 3/19 | Max Flows (continued from 3/7) Random Processes: Geometric Random Variables, Coupon Collector |
Notes | |

Randomized Algorithms |
||||

16 | We 3/21 | Random Processes: Birthday Paradox, Monte Carlo and Las Vegas Algorithms | Notes | DPV: virtual chapter KT: 13 CLRS: 5, 11 |

17 | Mo 3/26 | |||

18 | We 3/28 | Hashing | Notes | DPV: virtual chapter KT: 13 CLRS: 5, 11 |

Linear Programming |
||||

19 | Mo 4/2 | LP Formulations, Integer Linear Program | Notes | CLRS: 29 |

20 | We 4/4 | LP Duality | Notes | CLRS: 29 |

21 | Mo 4/9 | |||

We 4/11 | Midterm 2: Lectures 11-21 |
|||

22 | Mo 4/16 | LP Algorithms, Simplex Algorithms, Separation Oracles | ||

Intractability |
||||

23 | We 4/18 | Complexity Classes P and NP, Polynomial-time Reductions | Notes | DPV: 8 KT: 8 CLRS: 34 |

24 | Mo 4/23 | Approximation Algorithms: Vertex Cover, Set Cover, TSP | Notes | DPV: 8, 9 KT: 8, 11 CLRS: 34, 35 |

25 | We 4/25 | |||

26 | ||||

Mo 4/30 | Final Exam: All Lectures Time: Monday April 30, 2 - 5 pm Location: French Science 2231 |

Discussion | Date | Topic | Discussion Notes |

1 | Fr 1/12 | Induction, big-Oh notation | Notes |

2 | Fr 1/19 | ||

3 | Fr 1/26 | Divide and Conquer | Notes |

4 | Fr 2/2 | Greedy Algorithms | Notes |

5 | Fr 2/9 | Dynamic Programming | Notes |

6 | Fr 2/16 | All Pairs Shortest Path | |

7 | Fr 2/23 | Strongly Connected Components | |

8 | Fr 3/2 | MST Algorithms | |

9 | Fr 3/9 | Ford-Fulkerson Review; Bipartite Matching | |

10 | Fr 3/23 | Resource Contention; Balls and Bins | |

11 | Fr 3/30 | Randomized Quicksort Revisited | Notes |

12 | Fr 4/6 | LP Duality. Dual Fitting | |

13 | Fr 4/13 | Bipartite Matching LP Rounding | |

14 | Fr 4/20 | NP-hardness: Longest Path, Dominating Set |