Spring 2020 - COMPSCI 330 - Design and Analysis of Algorithms

Course Information

Homework

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

TA office hours

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:

• [DPV] S. Dasgupta, C. Papadimitriou, and U. Vazirani. Algorithms. McGraw Hill, 2006.
• [KT] J. Kleinberg and E. Tardos. Algorithm Design. Addison Wesley, 2005.
• [CLRS] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2009.

Prerequisites: 

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

• COMPSCI 201 Data Structures and Algorithms
• COMPSCI 230 Discrete Math for Computer Science

Evaluation:

• Homework (35%): Expect roughly 1 problem set per week. Please read the guideline on collaboration.
• Midterm Exams (30%): There will be two in-class midterm exams on 2/17 and 4/1.
• Final Exam (30%): Final exam is scheduled on 4/30, 2 pm - 5pm.
• Recitation Attendance (5%).

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 (55%): Expect roughly 1 problem set per week. Please read the guideline on collaboration. Two homeworks with lowest score will be dropped. You will also have one late-pass so you can submit your homework two days late without any reason (just submit the form on piazza).
  
• Exams (40%): Final exam is scheduled on 4/30. Final exam will be online (on gradescope) and open book/open notes. You can pick any 3 hours during a 24-hour period to finish the exam (with possibly more time if you need accomodations). Second midterm is cancelled.
  
• Final exam counts as two scores, together with your midterm score, the lowest one of the three will be dropped. That is, if your final score is higher, that will be your exam score; if your final score is lower, the average of that and the midterm is going to be your exam score.
  
• Recitation Attendance (Prior to spring break) (5%). Note that we will no longer check attendance for recitations after spring break. Attending recitations (or at least watching the recorded material) is still strongly recommended.
  

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:

• Introduction: History of Algorithms, Asymptotic and Worst-case Analysis
• Algorithm Design Techniques: Divide and Conquer (Recurrences), Dynamic Programming and Memoization, Greedy Algorithms
• Graph Algorithms: Graph Representations, Graph Traversal and Applications, Shortest Path, Minimum Spanning Tree, Maximum Matching
• Data Structures: Amortization and Potential Functions, Union-Find
• Algorithms for Machine Learning: Principled Component Analysis, Least Squares, Gradient descent 
• Randomized Algorithms: Monte Carlo and Las Vegas Algorithms, Hashing
• Linear Programming: Simplex Algorithms, LP Duality
• Intractability: P and NP, NP-completeness, Polynomial-time Reductions, Approximation Algorithms

Tentative Schedule