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

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/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

Min Chul Kim
Email: min.chul.kim@duke.edu
Office Hour: Thursdays 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 - 8 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

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
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 
9/14 Greedy Algorithm Slides Board Notes
DPV 5, KT 4, CLRS: 16
9/19 Slides
Randomized Algorithms
9/21
Basic Probabilities, Quicksort revisited, fast selection DPV: virtural chapger
KT: 13
CLRS: 5, 11
9/26 Birthday Paradox, Rejection Sampling, Monte-Carlo estimation
9/28 Hashing
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 DPV 3, KT 3, CLRS 22
10/17
10/19 Shortest Path Algorithms
DPV: 4.6, 6.6 KT: 6.8
CLRS: 24.1, 25
10/24 Minimum Spanning Tree DPV: 5 KT: 4 CLRS: 16, 23
10/26
10/31 Bipartite Graphs, Maximum Matching
DPV 7 KT: 7 CLRS: 26
Amortized Analysis
11/2 Dynamic Array
KT 4.6 CLRS 17, 20
11/7 Disjoint Sets

Linear Programming
11/9 Linear Programming, Relaxations
CLRS 29
11/14 Duality
11/16 Linear Programming Algorithms
11/21 Mid-Term Exam 2 (in class)
All materials between the two mid-terms.

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