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

Basic Information

• Lectures: Mon-Wed-Fri 2:00-2:50pm, Thomas Beckham Hall 180F
• Instructor: Yu Cheng
• Email: yucheng2@uic.edu
• Office Hours: Wed 3:30-4:30pm in SEO 416 and on Zoom (or by appointment).
• TA/Graders:
• Hai Wang (hwang202@uic.edu). Office Hours: Thu 3-4pm on Zoom.
• Truong Vu (tvu25@uic.edu). Office Hours: Fri 5-6pm on Zoom.
• 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 10 (Fri).
• Homework 2, due at 2pm on Sep 27 (Mon).
• Homework 3, due at 2pm on Oct 11 (Mon).
• Homework 4, due at 2pm on Oct 22 (Fri).
• Homework 5, due at 2pm on Nov 15 (Mon).
• Homework 6, due at 2pm on Dec 1 (Wed).

Schedule

Hand-written lecture notes from Fall 2020.
The slides that accompany the textbook (created by Kevin Wayne and distributed by Pearson).


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

Grading

• Homeworks (35%): We have 6 homeworks. You are encouraged to discuss with other students, but you must acknowledge who you worked with and write up your solutions independently. Your lowest HW score will be dropped (and the remaining HW score will scale proportionally). Late homeworks are not accepted (exceptions with good reasons may be requested in advance).
• Midterm (25%): Oct 25th (Mon), 2:00pm - 2:50pm.
• Final (40%): Dec 8th (Wed), 1:00pm-2:30pm.
• Bonus (20%): There are bonus points for some homework and exam questions.

Coding Advice

This course does not train you to write code. As requested, the instructor is offering some recources that may help you get better at coding.
• For coding interviews: You can try websites like LeetCode and HackerRank. Solving the coding questions is not the only goal during the interview. Other aspects may be equally important, e.g., how to approach a problem, how to think out loud, etc.
• For competitive programming: You can check out websites like USACO, various Online Judges like POJ, and the websites that regularly host online programming contests like Topcoder and Codeforces. Topcoder and Codeforces can be good starting points because (1) there are editorials (like this one or this one) afterward that explain the solutions, (2) you can see other people's code and you can learn from the best, and (3) they offer different difficulty levels.
  If you are specifically interested in ACM-ICPC (International Collegiate Programming Contest), you can check out the problem sets from our ICPC Regional Contest (Mid-Central) on Kattis, and (perhaps at a much later time) read the problem sets of the ICPC World Finals.
• Taking advanced algorithms (e.g., approximation algorithms, randomized algorithms) and data structures courses (e.g., this MIT Open Course) can improve your algorithmic maturity and help you code better in the long run.

Disability Policies

Religious Holidays