Spring 2020 - 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 and Linear Programming. 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 1
1/15/2020
1/22/2020, by 11:59 pm
Solution 1
Homework 2
1/29/2020
2/5/2020, by 11:59 pm
Solution 2
Homework 3
2/5/2020
2/12/2020, by 11:59 pm
Solution 3
Homework 4
2/26/2020
3/4/2020, by 11:59 pm
Solution 4
Homework 5
3/4/2020
3/25/2020, by 11:59 pm
Solution 5
Homework 6
4/1/2020
4/8/2020, by 11:59 pm Solution 6
Homework 7
4/8/2020
4/15/2020, by 11:59 pm
Solution 7
Homework 8
4/15/2020
4/22/2020, by 11:59 pm Solution 8

Instructor
Rong Ge
D226 LSRC
Email: rongge@cs.duke.edu
Office Hour: Tuesdays 1:00 - 2:00 PM, Fridays 11:00 AM - 12:00 at LSRC D226 (First office hour Friday 1/17)

After Spring break: I'm going to keep the Tuesdays 1 - 2 PM office hour on zoom. Instead of the Friday office hour, I will offer two 30-min sessions where I will be on piazza trying to answer all questions posted (First two will be Thursday 3-3:30 pm and Friday 10:30-11:00 am, 4/2 and 4/3). For the first two office hour Tuesday 3/24 and 3/31 I need to change the time to 12:30 - 1:30 PM.

Teaching Assistants

Haoming Li
Xiaonan Hong
Mo Zhou
Xiaoming Liu
Abraham Frandsen

Check here for detailed information for all the TAs.

TA office hours

Physics 259 6:30 - 8:30 PM Sundays and Tuesday 2/4
Physics 130
6:30 - 8:30 PM Mondays, Tuesdays (except 2/4), Wednesdays

After Spring break: See this post on piazza.


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

After Spring break: same time but on zoom, please check Sakai for a link to the zoom lectures.

Recitations: Check your individual recitation sessions.

After Spring break: See this post on piazza, you are recommended to stay with your section if your TA is still teaching at the same time and it's possible for you to attend. If you have any difficulty, you can go to a different recitation session that is most convenient for you. We will also record one of the session so you can watch it offline even if you cannot attend.

For most recent recitation materials please check this folder on Sakai.

Notice: The first recitation will be a review of materials already covered in 230 and is optional. Only some of the sessions will be open, you should go to the classroom based on your time.
1:25 pm and 4:40 pm in LSRC D106, 3:05 pm in Soc. Psych. 126

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.

Updated Evaluation:

Note: According to school policy, the course is defaulted to S/U grading. All of you should expect to get an S as long as you continue to work on the homework/exams to your capacity, and I'd be happy to discuss with anyone who has more difficulties. If you do want a letter grade, you need to submit a form by April 22 (the form is required by Trinity so check your email for the exact date).

Homework:

There will be 8 homeworks. In normal cases homeworks are due one week after they are posted. The worst two grade out of 8 homeworks will be dropped.
Homework will be submitted through GradeScope. Homework should be typed and submit as a PDF file. LateX is highly preferred.
If you are not familiar with LaTeX and want to learn, I learned how to use it by reading this (but there are also other resources you can find online).
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/8 Intro: Algorithms, Asymptotic Notations Slides Notes Scribe


Basic Algorithm Design Techniques
1/13 Divide and Conquer Slides Notes Scribe

DPV 2, KT 5, CLRS 4
1/15 Slides Notes Scribe
Homework 1
1/20
Martin Luther King, Jr. Day holiday. No classes are held.
1/22 Dynamic Programming
Slides Notes Scribe

DPV 6, KT 6, CLRS: 15
1/27 Slides Notes Scribe

1/29 Slides Notes Scribe
Homework 2
2/3
Greedy Algorithm Slides Notes Scribe

DPV 5, KT 4, CLRS: 16
2/5 Slides Notes Scribe
Homework 3
2/10 Slides Notes Scribe

2/12 Review Slides Notes


2/17 Mid-Term Exam 1 (in class)
All previous materials.
Previous midterm


Graph Algorithms
2/19 Graph representations and traversal Slides Notes Scribe

DPV 3, KT 3, CLRS 22
2/24 Slides Notes Scribe

2/26 Shortest Path Algorithms
Slides Notes Scribe
Homework 4 DPV: 4.6, 6.6 KT: 6.8
CLRS: 24.1, 25
3/2
Minimum Spanning Tree Slides Notes Scribe

DPV: 5 KT: 4 CLRS: 16, 23
3/4 Slides Notes Scribe
Homework 5
3/9,11,16,18
Spring Break
Linear Programming
3/23 Linear Programming, Relaxations Slides Notes Scribe

CLRS 29
3/25 Duality Slides Notes Scribe

3/30 Bipartite Matching, Max Flow
Slides Notes Scribe

4/1
Linear Programming Algorithms Slides Notes Scribe
Homework 6
Topics: Randomized Algorithms and Amortized Analysis
4/6
Basic Probabilities, Quicksort revisited, fast selection Slides Notes Scribe

DPV: virtural chapter
KT: 13
CLRS: 5, 11
4/8 Hashing Slides Notes Scribe
Homework 7
Intractability
4/13P vs NP, reductionsSlides Notes Scribe

DPV: 8 KT: 8
CLRS: 34
4/15 More reductions Slides Notes Scribe
Homework 8
4/20
Even more reductions Slides Notes Scribe

4/22 Amortized Analysis Slides Notes

KT 4.6 CLRS 17, 20
4/30 Final Exam
Everything covered in class
Previous Second Midterm
Previous Final