Fall 2017 - COMPSCI 330 - Design and Analysis of Algorithms

Algorithms are one of the foundations of computer science. Designing efficient algorithms under different resource constraint is a ubiquitous problem. In this course, we will study basic principals of designing and analyzing algorithms. In the class we will see classical examples of algorithms design including graph algorithms, data structures, Linear Programming and gradient descent. The goal of this course is to familiarize undergraduate students with algorithm design techniques that can be generalized to many application areas.

Announcements

There are some changes in UTAs and office hours. Please look below for the most updated information.
Office hours for new UTAs updated.
My office hours will be changed to Tuesdays and Fridays 4:30 - 5:30 PM to minimize conflictions. This will be effective from the second week.
TA office hours will start on Monday Sep. 4. Rong Ge's office hours start after the first lecture.

Course Information

Homework

Homework	Post Date	Due Date	Solution
Homework 0		Example only; no need for submission	Solution 0
Homework 1	9/5/2017	9/13/2017	Solution 1
Homework 2	9/13/2017	9/20/2017	Solution 2
Homework 3	9/20/2017	9/27/2017	Solution 3
Homework 4	9/27/2017	10/4/2017	Solution 4
Homework 5	10/18/2017	10/25/2017	Solution 5
Homework 6	10/25/2017	11/1/2017	Solution 6
Homework 7	11/1/2017	11/8/2017	Solution 7
Homework 8	11/9/2017	11/15/2017	See sakai for solutions after submission.
Homework 9	11/15/2017	11/29/2017	Solution 9
Homework 10	11/29/2017	12/8/2017	Solution 10

Instructor
Rong Ge
D226 LSRC
Email: rongge@cs.duke.edu
Office Hour: Tuesdays and Fridays 4:30 - 5:30 PM at LSRC D226

Teaching Assistant

Alex Steiger
Email: asteiger@cs.duke.edu
Office Hour: Mondays 3:00 - 5:00 PM, LSRC D301.

Keerti Anand
Email: kanand@cs.duke.edu
Office Hour: Wednesdays 3:00 - 5:00 PM, North 311.

Undergraduate Teaching Assistants

All undergraduate TA office hours will be at Physics 259.

Xingyu (Alex) Chen
Email: xingyu.chen@duke.edu
Office Hour: Mondays 7 - 8 PM

Rohith Kudi
Email: rohith.kuditipudi@duke.edu
Office Hour: Tuesdays 8 - 9 PM

Zachary Liu
Email: zachary.liu@duke.edu
Office Hour: Tuesdays 7 - 8 PM

William Long
Email: william.long@duke.edu
Office Hour: Sundays 7:30 - 8:30 PM

Weiyao Wang
Email: weiyao.wang@duke.edu
Office Hour: Tuesdays 7 - 8 PM

Will Wang
Email: weiyao.wang2@duke.edu
Office Hour: Mondays 7 - 8 PM

Haofang (Fred) Zhang
Email: h.z@duke.edu
Office Hour: Wednesdays 7 - 8 PM

Yumin Zhang
Email: yumin.zhang@duke.edu
Office Hour: Thursdays 7 - 8 PM

Lectures: Tuesdays and Thursdays 3:05 - 4:20 PM, Gross Hall 107

Recitations: Fridays 3:05 - 4:20 PM, Gross Hall 107

Text Book:

Lecture notes will be uploaded on the course website after every lecture. In addition, the following books cover most of the syllabus:

[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

If you do not satisfy these prerequisites, please contact the instructor.

Evaluation:

The grades will be determined by homework, two midterm exams and final exam. All exams are in-class closed-book exams.

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:

Please submit through sakai. 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:

This course covers the design and analysis of algorithms at an undergraduate level. The following is a tentative list of topics to be covered:

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

Date	Contents	Notes	References
8/29	Intro: Algorithms, Asymptotic Notations	Slides Board Notes
Basic Algorithm Design Techniques
8/31	Divide and Conquer	Slides Board Notes	DPV 2, KT 5, CLRS 4
9/5	Divide and Conquer	Slides Board Notes	DPV 2, KT 5, CLRS 4
9/7	Dynamic Programming	Slides Board Notes	DPV 6, KT 6, CLRS: 15
9/12	Dynamic Programming	Slides Board Notes	DPV 6, KT 6, CLRS: 15
9/14	Greedy Algorithm	Slides Board Notes	DPV 5, KT 4, CLRS: 16
9/19	Greedy Algorithm	Slides Board Notes	DPV 5, KT 4, CLRS: 16
Randomized Algorithms
9/21	Basic Probabilities, Quicksort revisited, fast selection	Slides Board Notes	DPV: virtural chapger KT: 13 CLRS: 5, 11
9/26	Rejection Sampling, Monte-Carlo estimation	Slides Board Notes
9/28	Hashing	Slides Board Notes

10/3	Review
10/5	Mid-Term Exam 1 (in class) All materials in previous lectures.
10/10	Fall Break
Graph Algorithms
10/12	Graph representations and traversal	Slides Board Notes	DPV 3, KT 3, CLRS 22
10/17	Graph representations and traversal	Slides Board Notes	DPV 3, KT 3, CLRS 22
10/19	Shortest Path Algorithms	Slides Board Notes	DPV: 4.6, 6.6 KT: 6.8 CLRS: 24.1, 25
10/24	Minimum Spanning Tree	Slides Board Notes	DPV: 5 KT: 4 CLRS: 16, 23
10/26	Minimum Spanning Tree	Slides Board Notes	DPV: 5 KT: 4 CLRS: 16, 23
10/31	Bipartite Graphs, Maximum Matching	Slides Board Notes	DPV 7 KT: 7 CLRS: 26
Amortized Analysis
11/2	Dynamic Array	Slides Board Notes	KT 4.6 CLRS 17, 20
11/7	Disjoint Sets	Slides Board Notes	KT 4.6 CLRS 17, 20
Linear Programming
11/9	Linear Programming, Relaxations	Slides Board Notes	CLRS 29
11/14	Duality	Slides Notes
11/16	Linear Programming Algorithms	Slides Board Notes
11/21	Mid-Term Exam 2 (in class) Graph Algorithms + Amortized Analysis (Sample Exam)
11/23	Thanksgiving
Intractability
11/28	P vs NP, reductions	Slides Board Notes	DPV: 8 KT: 8 CLRS: 34
11/30	More reductions	Slides Board Notes	DPV: 8 KT: 8 CLRS: 34
12/5	Even more reductions (Guest Lecture: Yu Cheng)	Slides Notes
12/7	How to handle NP-hard problems (Guest Lecture: Debmalya Panigrahi)
	Machine Learning Algorithms (promised last lecture but I will be at NIPS. This is what I do for research, will upload a video later, not related to exam, watch if you are interested.)
12/14	Final Exam 9 am - noon	Previous year exam