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

HomeworkPost DateDue Date
Homework 19/129/27
Homework 29/2610/14
Homework 310/1011/2
Homework 411/111/15
Homework 511/1412/2
Homework 612/112/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:

Prerequisites: 

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

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:

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:

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 Notes
9/7 Dynamic Programming
Notes DPV 6, KT 6, CLRS: 15
9/12 Notes
9/14 Greedy Algorithm Notes
DPV 5, KT 4, CLRS: 16
9/19 Notes
Graph Algorithms
9/21
Graph representations and traversal Notes DPV 3, KT 3, CLRS 22
9/26 Notes
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
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
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
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