Fall 2026 · CSCI 3160

Design and Analysis of Algorithms

Offered by Yufei TAO, Fall 2026.

Tutors: Duan Tingting, Lyu Haotian, Sangsiri Nawapon, Sun Chenya, Xiong Xinzhuang, and Xu Xiaoyu.

Offices and Consultation Hours:

Yufei Tao: 4pm-5pm Tue, SHB 1011
Duan Tingting: 4pm-5pm Wed, SHB 1013
Lyu Haotian: 3pm-4pm Thu, SHB 120
Sangsiri Nawapon: 2pm-3pm Fri, SHB 1013
Sun Chenya: 3pm-4pm Tue, SHB 1004
Xiong Xinzhuang: 2:20pm-3:20pm Mon, SHB 1013
Xu Xiaoyu: 10am-11am Tue, SHB 921

Brief Description

In this course, we will (i) introduce provably efficient algorithms for solving a set of classic problems that are frequently encountered in practice, (ii) extract from those algorithms the generic techniques that can be deployed to solve many other problems with strong performance guarantees, and (iii) study NP-hard/complete problems (that is, problems of which no polynomial time algorithms are known) and their approximation algorithms for NP-hard problems.

Announcements

News 7 (Oct 15): Quiz 1 scores have been released. The solutions can be found at the bottom of this page.

You may now approach TAs during their office hours to collect your papers. Please look for the name of the TA responsible for your student ID:

1155144802 - 1155214617: Sangsiri Nawapon
1155215102 - 1155233504: Tingting Duan
1155233704 - 1155235364: Haotian Lyu
1155235365 - 1155283828: Xiaoyu Xu.

If you took a make-up test for Quiz 1, please approach the instructor for your paper.

News 6 (Oct 14): Midterm will take place during the lecture on Oct 21 (Wed), from 1:30 pm to 3 pm (90 minutes). The scope will cover everything from Warm Up 1 through Dynamic Programming 4. The exam is closed book.

News 5 (Sep 24): Quiz 1 will take place during the lecture on Sep 30 (Wed), from 2:35 pm to 3:05 pm (30 minutes). The scope will cover everything from Warm Up 1 through Greedy 2.

News 4 (Sep 13): Sick Leave Policy for Tests
If you are medically unable to sit a quiz or examination, email the instructor at least 4 hours before the lecture where the test is held, where practicable, or as soon as possible in an emergency. Submit a medical certificate from a registered medical practitioner as soon as possible. Approved absences will be handled through a make-up or alternative assessment determined by the instructor and applicable University regulations. Centralized examinations are governed by Registration and Examinations Section procedures.

News 3 (Sep 13): Please note the test schedule for this course:

Quiz 1 will be held in the lecture of Sep 30 (Wed, Week 4).
The midterm will be held in the lecture of Oct 21 (Wed, Week 7).
Quiz 2 will be held in the lecture of Nov 11 (Wed, Week 10).
Quiz 3 will be held in the lecture of Dec 2 (Wed, Week 13).

News 2 (Aug 27): There will be no tutorials in Week 1.

News 1 (Aug 27): Hello, all.

Time and Venues

Lectures

Day	Time	Venue
Wednesday	1:30pm - 3:15pm	Mong Man Wai Building LT1
Thursday	1:30pm - 2:15pm	Lady Shaw Building LT1

Tutorials

Session	Day	Time	Venue
T01	Thursday	9:30am - 10:15am	William M. W. Mong Engineering Building 407
T02	Thursday	10:30am - 11:15am	Lady Shaw Building C4
T03	Thursday	4:30pm - 5:15pm	Wu Ho Man Yuen Building 408
T04	Thursday	5:30pm - 6:15pm	William M. W. Mong Engineering Building 803

Click here for a map of the campus.

Grading Scheme

In-Class Quiz 1: 8%
In-Class Quiz 2: 8%
In-Class Quiz 3: 8%
Midterm Exam: 26%
Final Exam: 50%

All quizzes and exams are closed-book.

Style of Exams:
During this course, the instructor will gradually generate a list of special exercises with no solutions given. In the midterm and final exams, about 35% of the marks will come from problems taken directly from that list. The rest 65%, however, will be from new problems.

Lecture Notes and Textbook

The instructor recommends the following textbook:
Introduction to Algorithms, 3rd Edition. By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

Ownership of the book is not compulsory. The instructor will make lecture notes available before each lecture. His notes will be self-contained, namely, containing all the details required in this course.

Lecture attendance is vital to grasp the material taught.

	Lecture Notes	Textbook Reading (If a Book is Owned)
Warm Up 1	The RAM Model	--
Warm Up 2	Performance Measurement by the Worst Input	--
Lecture videos on Sep 9: video 1, video 2
1	Basic 1: Recursion, Repeating, and Geometric Series	Section 9.2 (the textbook's k-selection algorithm requires a more tedious analysis, as discussed in a regular exercise).
Lecture video on Sep 10: video
2	Basic 2: Divide and Conquer	Sections 4.1, 4.2, and 28.2
Lecture videos on Sep 16: video 1, video 2 Lecture video on Sep 17: video
3	Greedy 1: Activity Selection	Section 16.1
The 1st half of the Sep 23 lecture: video The 2nd half of the Sep 23 lecture was not captured successfully
4	Greedy 2: Minimum Spanning Trees	Chapter 23 (you may skip Kruskal's algorithm)
5	Greedy 3: Huffman Codes	Section 16.3
Lecture video on Sep 24: video Lecture video on Sep 30: video
6	Dynamic Programming 1: Pitfall of Recursion	Section 15.1
7	Dynamic Programming 2: Rod Cutting	Section 15.1
8	Dynamic Programming 3: Dependency	Section 15.4
The lecture on Oct 7 was not recorded. Lecture video on Oct 8: video
9	Dynamic Programming 4: Longest Common Subsequence	Section 15.4
Lecture videos on Oct 14: video 1 (poor audio), video 2
10	Dynamic Programming 5: Optimal BST	Section 15.5
Lecture videos on Oct 15: video
11	Graph 1: (Review) DFS and White Path Theorem	Section 22.3
12	Graph 2: Strongly Connected Components	Section 22.5
13	Graph 3: (Review) SSSP with Non-Negative Weights - Dijkstra's	Sections 24.2 and 24.3
14	Graph 4: SSSP with Arbitrary Weights - Bellman-Ford	Sections 24.1 and 24.5
15	Graph 5: All-Pairs Shortest Paths - Johnson's	Sections 25.2 and 25.3
16	Graph 6: Max-Flow (postponed to Week 13, non-testable)	Sections 26.1 and 26.2
17	Approximation Algorithms 1: Vertex Cover and Max-3SAT	Sections 35.1 and 35.4 (you can ignore linear programming)
18	Approximation Algorithms 2: Traveling Salesman	Section 35.2
19	Approximation Algorithms 3: Set Cover and Hitting Set (updated at 2:45am, 20 Nov) (Old version)	Section 35.3
20	Approximation Algorithms 4: k-Center	--

Tutorial Material

Week 2	Growth of Functions
Week 2 tutorial video by Nawapon: video Week 2 tutorial video by Tingting: video
Week 3	Three Basic Techniques
Week 4	Divide and Conquer
Week 3 tutorial video by Nawapon: video Week 3 tutorial video by Tingting: video
Week 5	Kruskal's Algorithm
Week 5 tutorial video by Nawapon: video Week 5 tutorial video by Xiaoyu: video
Week 6	Dynamic Programming: Piggyback, Dependency, and Space
Week 8	Matrix-Chain Multiplication
Week 9	SCC: Further Insights
Week 10	The Floyd-Warshall algorithm for APSP
Week 11	Bellman-Ford: Negative Cycles Proof for finding a negative cycle (non-testable)
Week 12	Reductions for Proving NP-Hardness
Week 13	Set Cover and Hitting Set

Regular Exercises

The instructor believes that the following exercises are useful for you to consolidate your understanding of the course material. Unlike the "special" exercises (see the next section), solutions to these "regular" exercises are provided in full. Exercises carrying one or more stars ("*") may be difficult. The more stars, the more difficult.

List 1 (Solutions)
List 2 (Solutions)
List 3 (Solutions)
List 4 (Solutions)
List 5 (Solutions)
List 6 (Solutions)
List 7 (Solutions)

Special Exercises

Some problems in the midterm and final exams will be taken directly from the special exercise lists below. No solutions to these exercises will be given. You are free to look for the solutions in any way. Remember: during the exams, you will be allowed to consult only one piece of single-sided A4-sized paper; it is unrealisic to hope that you can write down all the solutions on that paper. Special exercises in general are easier than regular exercises.

List 1
List 2
List 3
List 4
List 5
List 6
List 7

Quizzes and Exams

Quiz 1 Solutions, Avg = 77.9, Std. Dev. = 17.7