Spring 2019 - COMPSCI 330 - Design and Analysis of Algorithms

Course Information

Homework

Instructor
Rong Ge
D226 LSRC
Email: rongge@cs.duke.edu
Office Hour (tentative): Tuesdays 4:30 - 5:30 PM, Fridays 3:00 - 4:00 PM at LSRC D226

Teaching Assistant

Haoming Li
Email: haoming.li@duke.edu

Shweta Patwa
Email: sjpatwa@cs.duke.edu

Chenwei Wu
Email: cwwu@cs.duke.edu

TA office hours

Recitations: Check your individual recitation sessions.

Text Book:

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

Prerequisites: 

There are two hard prerequisites (equivalent courses are also acceptable):

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

Evaluation:

• Homework (40%): Expect roughly 1 problem set per week. Please read the guideline on collaboration.
• Midterm Exams (30%): There will be two in-class midterm exams on Oct. 5 and Nov. 21.
• Final Exam (30%): Final exam is scheduled on Dec. 14.

Homework:

There will be 9 homeworks. In normal cases homeworks are due one week after they are posted. The worst grade out of 9 homeworks will be dropped.
Homework will be submitted through GradeScope. Homework should be typed and submit as a PDF file. Latex is highly preferred.
Please make sure to read the guideline on collaboration. Every incidence of cheating will be reported.
Questions about homework problems should be posted to Piazza (instead of emailing the TAs or the instructor).

Synopsis:

• 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, Maximum Matching
• Data Structures: Amortization and Potential Functions, Union-Find
• Algorithms for Machine Learning: Principled Component Analysis, Least Squares, Gradient descent 
• 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

Tentative Schedule