MCS/CS 401: Computer Algorithms I (Fall 2020)

Basic Information

• Lectures: Mon-Wed-Fri 2:00-2:50pm
• Instructor: Yu Cheng
• Email: yucheng2@uic.edu
• Office Hours: Wed 3-4pm and by appointment.
• Graders:
• Hai Wang (hwang202@uic.edu). Office Hours: Tue 3-4pm.
• Sayan Mukherjee (smukhe2@uic.edu). Office Hours: Thu 2-3pm.
• Textbook (Required): Algorithm Design, First Edition. Jon Kleinberg and Éva Tardos
• Fun Reading: Introduction to Algorithms, Third Edition. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

Homeworks

Warning: the following assignments and due dates are from the past. If you are taking MCS 401 this semester, please refer to the current course webpage.

• Homework 1, due at 2pm on Sep 21 (Mon).
• Homework 2, due at 2pm on Sep 28 (Mon).
• Homework 3, due at 2pm on Oct 28 (Wed).
• Homework 4, due at 2pm on Nov 2 (Mon).
• Homework 5, due at 2pm on Dec 2 (Wed).
• Homework 6, due at 2pm on Dec 7 (Mon).

Schedule

• Week 1 (Aug 24), Stable Matching:
• Introduction to the Course
• Stable Matching (Chapter 1.1) (Lecture 2, Lecture 3)
• Week 2-3 (Aug 31), Basics of Algorithm Analysis:
• Worst-Case Running Times (Chapter 2.1), Asympototic Notations (Chapter 2.2) (Lecture 4, Lecture 5)
• Arrays and Linked Lists, Implementing Stable Matching (Chapter 2.3) (Lecture 6, Lecture 7)
• Common Running Times (Chapter 2.4) (Lecture 8)
• Week 4-5 (Sep 14), Graphs:
• Basic Definitions (Chapter 3.1) (Lecture 9)
• Breadth-First Search (BFS), Depth-First Search (DFS) (Chapter 3.2) (Lecture 10)
• Stacks and Queues, Implementing DFS and BFS (Chapter 3.3) (Lecture 11)
• Applications of BFS and DFS (Chapter 3.4) (Lecture 12)
• Connectivity in Directed Graphs (Chapter 3.5) (Lecture 13)
• Topological Ordering (Chapter 3.6) (Lecture 14)
• Week 6-8 (Sep 28), Greedy Algorithms:
• Midterm Exam 1 Review (Lecture 15)
* Midterm Exam 1: Sep 30th (Wed), 2:00pm - 2:50pm.
• Interval Scheduling (Chapter 4.1) (Lecture 17)
• Scheduling to Minimize Lateness (Chapter 4.2) (Lecture 18)
• Shortest Path, Dijkstra's Algorithm (Chapter 4.4) (Lecture 19 and 20)
• Minimum Spanning Tree, Kruskal's Algorithm, Prim's Algorithm, Union-Find (Chapter 4.5, 4.6) (Lecture 21, 22, and 23)
• Week 9-10 (Oct 19), Divide and Conquer:
• Mergesort, Counting Inversions (Chapter 5.1, 5.3) (Lecture 24 and 25)
• Master's Theorem (Chapter 5.2) (Lecture 26)
• Closest Pair of Points (Chapter 5.4), Delaunay Triangulation (Lecture 27)
• HW3 Solutions (Lecture 28)
• Integer Multiplication, Fast Fourier Transform (Chapter 5.5, 5.6) (Lecture 29)
• Week 11-13 (Nov 2), Dynamic Programming:
• Midterm Exam 2 Review, Dynamic Programming (Chapter 6.2) (Lecture 30)
* Midterm Exam 2: Nov 4th (Wed), 2:00pm - 2:50pm.
• Weighted Interval Scheduling (Chapter 6.1) (Lecture 32)
• Segmented Least Squares (Chapter 6.3) (Lecture 33)
• Subset Sum and Knapsack (Chapter 6.4) (Lecture 34)
• Midterm 2 Solutions (Lecture 35)
• Shortest Path, Bellman-Ford Algorithm (Chapter 6.8) (Lecture 36, 37 and 38)
• Week 14 (Nov 23), Network Flow:
• Maximum Flow, Ford-Fulkerson Algorithm (Chapter 7.1) (Lecture 39)
• Minimum Cut, Max-Flow Min-Cut Theorem (Chapter 7.2) (Lecture 40)
• Week 15 (Nov 30), NP and NP-Complete:
• Polynomial-Time Reductions (Chapter 8.1), NP and NP-Complete (Chapter 8.3, 8.4) (Lecture 41 and 42)
• Reductions via Gadgets (Chapter 8.2), Hamiltonian Cycle, Graph Coloring (Chapter 8.5, 8.7) (Lecture 43)
* Final Exam: Dec 9th (Wed), 1:00pm-2:30pm.

Grading

• Homeworks (30%): We will have 5-7 homeworks. You are encouraged to discuss with other students, but you must acknowledge who you worked with and you must write up your solutions independently. Late homeworks are not accepted in general (exceptions with good reasons may be requested in advance).
• Midterm 1 (20%): Sep 30th (Wed), 2:00pm - 2:50pm.
• Midterm 2 (20%): Nov 4th (Wed), 2:00pm - 2:50pm.
• Final (30%): Dec 9th (Wed), 1:00pm-2:30pm.

Disability Policies

Religious Holidays