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 29/13/20179/20/2017Solution 2
Homework 39/20/20179/27/2017Solution 3
Homework 49/27/201710/4/2017Solution 4
Homework 510/18/201710/25/2017Solution 5
Homework 610/25/201711/1/2017Solution 6
Homework 711/1/201711/8/2017Solution 7
Homework 811/9/201711/15/2017See sakai for solutions after submission.
Homework 911/15/201711/29/2017

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:

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, two midterm exams and final exam. All 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:

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 Slides Board Notes
9/7 Dynamic Programming
Slides Board Notes
DPV 6, KT 6, CLRS: 15
9/12 Slides Board Notes
9/14 Greedy Algorithm Slides Board Notes
DPV 5, KT 4, CLRS: 16
9/19 Slides Board Notes
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 Slides Board Notes
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 Slides Board Notes
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
Linear Programming
11/9 Linear Programming, Relaxations Slides Board
CLRS 29
11/14 Duality Slides
11/16 Linear Programming Algorithms Slides Board
11/21 Mid-Term Exam 2 (in class)
Graph Algorithms + Amortized Analysis (Sample Exam)

11/23 Thanksgiving
Intractability
11/28 P vs NP, reductions

DPV: 8 KT: 8
CLRS: 34
11/30
More reductions

12/5 How to deal with NP-hard problems?

12/7 Algorithms in machine learning.

12/14 Final Exam 9 am - noon