Spring 2019 - 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.

Course Information

Homework

Homework Post Date Due Date Solution
Homework 0 Example only; no need for submission Solution 0
Homework 11/17/20191/24/2019 (by 11:59 pm)Solution 1
Homework 21/24/20191/31/2019 (by 11:59 pm)Solution 2
Homework 31/31/20192/11/2019 (by 5 pm)Solution 3
Homework 42/21/20192/28/2019 (by 11:59 pm)Solution 4
Homework 52/28/20193/7/2019 (by 11:59 pm)
Homework 63/7/20193/21/2019 (by 11:59 pm)

Instructor
Rong Ge
D226 LSRC
Email: rongge@cs.duke.edu
Office Hour (tentative): Tuesdays 4:30 - 5:30 PM, Fridays 3:00 - 4:00 PM at LSRC D226

Teaching Assistant

Haoming Li
Email: haoming.li@duke.edu

Shweta Patwa
Email: sjpatwa@cs.duke.edu

Chenwei Wu
Email: cwwu@cs.duke.edu

TA office hours

Sundays: 5-7PM in Bio Sci 130 with Chenwei
        EXCEPT 1/13: Bio Sci 155
        EXCEPT 1/20: TBD (may be cancelled)

Mondays: 5-7PM in Bio Sci 155 with Alex

Tuesdays: 5-7PM in Bio Sci 155 with Shweta

Wednesdays: 5-7PM in Bio Sci 130 with Andres

Thursdays: 4-8PM in Bio Sci 130 with Shamikh (4-6PM) and Conrad (6-8PM)
        EXCEPT 2/28: Bio Sci 154

Fridays: 5-7PM in Bio Sci 130 with Haoming

Saturdays: NO office hours

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

Recitations: Check your individual recitation sessions.

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:

There will be 9 homeworks. In normal cases homeworks are due one week after they are posted. The worst grade out of 9 homeworks will be dropped.
Homework will be submitted through GradeScope. 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 Homework References
1/10 Intro: Algorithms, Asymptotic Notations Slides Board Scribe
Basic Algorithm Design Techniques
1/15 Divide and Conquer Slides Board Scribe
DPV 2, KT 5, CLRS 4
1/17 Slides Board Scribe
Homework 1
1/22 Dynamic Programming
Slides Board Scribe
DPV 6, KT 6, CLRS: 15
1/24 Slides Board Scribe
Homework 2
1/29 Slides Board Scribe
1/31 Greedy Algorithm Slides Board Scribe
Homework 3 DPV 5, KT 4, CLRS: 16
2/5 Slides Board Scribe
2/7 Slides Board Scribe
2/12 Review Slides Board
2/14 Mid-Term Exam 1 (in class)
All previous materials.
Practice Exam (Ignore Problem 4 as it is for randomized algorithms)
Graph Algorithms
2/19 Graph representations and traversal Slides Board Scribe DPV 3, KT 3, CLRS 22
2/21 Slides Board Board2 Scribe Homework 4
2/26 Shortest Path Algorithms
Slides Board Scribe DPV: 4.6, 6.6 KT: 6.8
CLRS: 24.1, 25
2/28 Minimum Spanning Tree Slides Board Scribe Homework 5 DPV: 5 KT: 4 CLRS: 16, 23
3/5 Slides Board Scribe
3/7 Bipartite Graphs, Maximum Matching Slides Board Homework 6 DPV 7 KT: 7 CLRS: 26
Fall Break
Linear Programming
3/19 Linear Programming, Relaxations Slides Board CLRS 29
3/21 Duality Homework 7
3/26 Linear Programming Algorithms
3/28Review
4/2Mid-Term Exam 2 (in class)
Graph algorithms and Linear Programming.
Topics: Randomized Algorithms and Amortized Analysis
4/4
Basic Probabilities, Quicksort revisited, fast selection
DPV: virtural chapger
KT: 13
CLRS: 5, 11
4/9 Hashing
4/11 Amortized Analysis Homework 8 KT 4.6 CLRS 17, 20
Intractability
4/16 P vs NP, reductions
DPV: 8 KT: 8
CLRS: 34
4/18
More reductions
Homework 9
4/23 Even more reductions
5/3 Final Exam 2:00 - 5:00 PM
Everything covered in class except for bipartite matching and amortized analysis