Fall 2016 - 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

Homework 6 is posted. Due on Friday Dec. 9th.
Homework 5 is posted. Due on Friday Dec. 2nd.
Homework 4 is posted. Due on Tuesday Nov. 15th.
Homework 3 is posted. Due on Wednesday Nov. 2st
There will be No Recitation Friday Oct. 7th (due to Fall break)
Homework 2 is posted. Due on Friday Oct. 14th (due to Fall break)
Office hour LOCATION CHANGE! We are not allowed to use Link for office hours, see below for the new locations.
Homework 1 is posted. Due on Tuesday Sep. 27th.
Date for final exam modified to agree with the information on duke registrar.

Course Information

Homework

Homework	Post Date	Due Date
Homework 1	9/12	9/27
Homework 2	9/26	10/14
Homework 3	10/10	11/2
Homework 4	11/1	11/15
Homework 5	11/14	12/2
Homework 6	12/1	12/9

Instructor
Rong Ge
D226 LSRC
Email: rongge@cs.duke.edu
Office Hour: Tuesdays 3:00 - 5:00 PM at LSRC D226

Teaching Assistant
Yuan Deng
Email: yuan.deng@duke.edu
Office Hour: Thursdays 5:00 - 7:00 PM at LSRC D309

Undergraduate Teaching Assistants

Arun Ganesh
Email: arun.ganesh@duke.edu
Office Hour: Wednesdays 12:00 - 2:00 PM at LSRC D309

Bodong (Wilson) Zhang
Email: bodong.zhang@duke.edu
Office Hour: Mondays 10:00-11:00 AM at LSRC D301

Aditya Mukund
Email: am439@duke.edu
Office Hour: Mondays 5:00 - 6:00 PM at LSRC D301

Weiyao (Will) Wang
Email: ww109@duke.edu
Office Hour: Fridays 5:00 - 6:00 PM at LSRC D301

Fred Zhang
Email: h.z@duke.edu
Office Hour: Mondays 7:00 - 8:00 PM at LSRC D301

Lectures: Mondays and Wednesdays 3:05 - 4:20 PM, White Lecture Hall 107

Recitations: Fridays 3:05 - 4:20 PM, Physics 128

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, midterm exam and final exam. Both exams are in-class closed-book exams.

Homework (45%): There will be six homework assignments. Please read the guideline on collaboration.
Midterm Exam (25%): Midterm exam is scheduled on Oct. 17th in class.
Final Exam (30%): Final exam is scheduled on Dec. 17th.

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

Schedule

Date	Contents	Notes	References
8/29	Intro: Algorithms, Asymptotic Notations	Notes
Basic Algorithm Design Techniques
8/31	Divide and Conquer	Notes	DPV 2, KT 5, CLRS 4
9/5	Divide and Conquer	Notes	DPV 2, KT 5, CLRS 4
9/7	Dynamic Programming	Notes	DPV 6, KT 6, CLRS: 15
9/12	Dynamic Programming	Notes	DPV 6, KT 6, CLRS: 15
9/14	Greedy Algorithm	Notes	DPV 5, KT 4, CLRS: 16
9/19	Greedy Algorithm	Notes	DPV 5, KT 4, CLRS: 16
Graph Algorithms
9/21	Graph representations and traversal	Notes	DPV 3, KT 3, CLRS 22
9/26	Graph representations and traversal	Notes	DPV 3, KT 3, CLRS 22
9/28	Shortest Paths algorithms	Notes	DPV: 4.6, 6.6 KT: 6.8 CLRS: 24.1, 25
10/3	Minimum Spanning Tree	Notes	DPV: 5 KT: 4 CLRS: 16, 23
10/5	Bipartite Graphs, Maximum Matching	Notes	DPV 7 KT: 7 CLRS: 26
10/10	Fall break, No class
10/12	Review: How to find the right technique
10/17	Mid-Term Exam (in class) All materials in previous lectures.
Amortized Analysis
10/19	Dynamic Array	Notes	KT 4.6 CLRS 17, 20
10/24	Disjoint set	Notes	KT 4.6 CLRS 17, 20
Randomized Algorithms
10/26	Basic Probabilities, Quicksort revisited, fast selection	Notes	DPV: virtural chapger KT: 13 CLRS: 5, 11
10/31	Birthday Paradox, Coupon Collector, Balls in Bins	Notes
11/2	Hashing	Notes
Linear Programming
11/7	Linear Programming, Relaxations	Notes	CLRS 29
11/9	Duality	Notes	CLRS 29
11/14	Linear Programming Algorithms	Notes
Machine Learning Algorithms
11/16	Basic Machine Learning, Principled Component Analysis	Slides Notes
11/21	Gradient Descent and Least Squares	Notes
11/23	Thanksgiving
Intractability
11/28	P vs NP, reductions	Notes	DPV: 8 KT: 8 CLRS: 34
11/30	More reductions	Notes	DPV: 8 KT: 8 CLRS: 34
12/5	How to deal with NP-hard problems?	Notes
12/7	Review/Information about Exam	Slides Notes
12/17	Final Exam 2 pm - 5pm