CSCI3160 Design and Analysis of Algorithms

Offered by Yufei TAO, Fall 2023.

Tutors: Xilin Dang (xldang23@cse), Shiyuan Deng (sydeng@cse), Lijun Lang (ljlang23@cse), Ru Wang (rwang21@cse), Yuchen Zhong (yczhong23@cse).

Offices and Consultation Hours:
  • Yufei Tao: 3pm-4pm Tue, SHB 1019
  • Xilin Dang: 5pm-6pm Mon, SHB 921
  • Shiyuan Deng: 2pm-3pm Mon, SHB 1013
  • Lijun Lang: 5pm-6pm Mon, SHB 913
  • Ru Wang: 2pm-3pm Mon, SHB 1013
  • Yuchen Zhong: 3pm-4pm Mon, SHB 1013

Quick navigation links:
[Time and Venues][Lecture Notes][Tutorials][Regular Exercises][Special Exercises][Quizzes and Exams]
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 20 (4 Dec): You may now collect your Quiz 3 papers. To do so, please locate the TA assigned to your ID from the list given in News 8. The solutions can now be found in the "Quizzes and Exams" section of this page.

News 19 (28 Nov): We will arrange for you to review your final exam papers on Dec 18. Please follow the instructions below:
  • You must arrive at the office of Mr. Shiyuan Deng (SHB 1013) during 10am-11:59am or 2pm-5:30pm. Shiyuan will then tell you the TA responsible for your paper and how you can find that TA.
  • You cannot take away your exam paper and neither will you be allowed to take pictures of the paper.
  • We will not send you pictures of your paper.
  • No other paper-review sessions will be organized.
News 18 (24 Nov): Quiz 3 will start at the beginning of next Wed's lecture and will have a length of 25 minutes.

News 17 (23 Nov): The scope of Quiz 3 covers everything from Lect 16 to Lect 19.

News 16 (11 Nov): You may now collect your Quiz 2 papers. To do so, please locate the TA assigned to your ID from the list given in News 8. The solutions can now be found in the "Quizzes and Exams" section of this page.

News 15 (8 Nov): New Sick Leave Policy for Tests
In the unfortunate event that you are seriously ill on the day of a quiz or an exam, you can be absent from the test provided that the following conditions are satisfied.
  • You must email the instructor at least 4 hours before the start time of the lecture in which the test is administered.
  • You must provide a doctor's certificate within 12 hours after the test's end time. The certificate must state your illness clearly. The instructor generally accepts certificates indicating illnesses that are highly contagious, involve high fever, hamper movements, or require hospitalization, but rejects certificates for common illnesses such as cold, headaches, diarrhea, bronchitis, rashes, or gastroenteritis. You may be required to attend an interview with the instructor if deemed necessary.
Real emergency cases will be handled separately.

If your sick-leave is granted, you must take a make-up test on the day right after the rest period recommended by the doctor. The make-up test will be more difficult than the plenary test (because you have more time to prepare for the test). To arrange a make-up test, you must email the instructor your course schedule, and the instructor will pick a time slot according to your schedule. Failure to show up for the make-up test will result in a score of zero.

News 14 (8 Nov): Yuchen Zheng, who has performed excellently in his TA work, has been removed from this course. His TA duties will be shifted to other TAs. Previously, Yuchen was responsible for the student ID range 1155122310 – 1155173899. The new responsible TA is Shiyuan Deng.

News 13 (3 Nov): The make-up lecture has been scheduled for Dec 1, from 6:30pm to 8:15pm. The venue is ERB 703.

News 12 (3 Nov): The scope of Quiz 2 covers everything from Lect 10 to Lect 14.

News 11 (29 Oct): You may now collect your midterm papers. To do so, please locate the TA assigned to your ID from the list given in News 8. Then, visit their offices during the designated consultation periods. If needed, you may also consider reaching out to the TA via email to request a special appointment. Please note that it is at the TA's discretion to decide whether to grant your request. The midterm solutions can now be found in the "Quizzes and Exams" section of this page.

News 10 (12 Oct): In the midterm exam, 30% of the marks will come from problems from the special exercise lists. You will be allowed to bring in a single-sided, A4-sized, note sheet on which you can print/write anything you deem useful.

News 9 (5 Oct): The scope of the midterm covers everything from Warm Up 1 to Lect 9.

News 8 (1 Oct): You may now collect your Quiz 1 papers. To do so, please locate the TA assigned to your ID from the list provided below. Then, visit their offices during the designated consultation periods. If needed, you may also consider reaching out to the TA via email to request a special appointment. Please note that it is at the TA's discretion to decide whether to grant your request.
  • 1155122310 – 1155173899: Yucheng Zhong Shiyuan Deng.
  • 1155173905 – 1155175864: Lijun Lang
  • 1155175975 – 1155210574: Xilin Dang.
News 7 (1 Oct): Quiz 1 scores have been released on Blackboard. The solutions can now be found in the "Quizzes and Exams" section of this page.

News 6 (27 Sep): Sick Leave Policy for Tests
If you want to be absent from a quiz or the midterm exam by citing health reasons, you must
  • Email the instructor at least one hour before the test start time.
  • Submit a doctor's certificate within 12 hours of the test start time.
  • Take a make-up test on the day right after the rest period recommended by the doctor.
Further remarks:
  • The make-up test will be more difficult than the plenary test (because you have more time to prepare for the test).
  • You must approach the instructor to make an appointment for your make-up test. For that purpose, you will need to submit your course schedule. The instructor will pick a time slot according to your schedule. If you do not show up for your make-up test, your test score will be zero.
Real emergency cases will be handled separately.

News 5 (23 Sep): The scope of Quiz 1 includes everything from "Warm Up 1" to "Lecture 3" (Lecture 4 is not included). The quiz is open book.

News 4 (8 Sep): Regular Exercise 1 and Special Exercise 1 have been released. You can locate them at the bottom of this page. No more announcements will be made regarding the release of exercises. Please check this page regularly for updates.

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

Quiz 1 (20 minutes) is to be held in the lecture of Sep 27 (Wed, Week 4);
Midterm (90 minutes) is to be held in the lecture of Oct 18 (Wed, Week 7);
Quiz 2 (20 minutes) in the lecture of Nov 8 (Wed, Wed 10);
Quiz 3 (20 minutes) in the lecture of Nov 29 (Wed, Wed 13).

News 2 (6 Sep): The videos for the first lecture have been made available. Be aware that the university has resumed in-person classes, and the release of videos is not mandatory. We request that you view the videos as an additional resource, rather than considering them as a guaranteed provision. The decision to release a video is at the discretion of the instructor. There will be no further announcements for video releases.

News 1 (30 Aug): Hello, all.

Time and Venues

Lectures

Wed
11:30am - 1:15pm
William M W Mong Eng Bldg LT
Zoom Link: https://cuhk.zoom.us/j/93116022069

Thu
1:30pm - 2:15pm
William M W Mong Eng Bldg LT
Zoom Link: https://cuhk.zoom.us/j/97432795717

Tutorials
Zoom Link: https://cuhk.zoom.us/j/91329824212

Session 1 Thu 11:30am - 12:15pm Lady Shaw Bldg LT2
Session 2 Thu 2:30pm - 3:15pm Lady Shaw Bldg LT4
Session 3 Thu 3:30pm - 4:15pm Lady Shaw Bldg LT4
Session 4 Thu 4:30pm - 5:15pm Lady Shaw Bldg LT4

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%

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. In the midterm and the final exams, you will be allowed to bring in a single-sided, A4-sized, note sheet on which you can print/write anything you deem useful.

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

(video)

 --
Warm Up 2
Performance Measurement by the Worst Input

(The content is in the video of Warm Up 1)

--
1
Basic 1: Recursion, Repeating, and Geometric Series

(video)

 Section 9.2 (the textbook's k-selection algorithm requires a more tedious analysis, as discussed in a regular exercise).
2
Basic 2: Divide and Conquer

(video 1)
(video 2)

Sections 4.1, 4.2, and 28.2
3
Greedy 1: Activity Selection (updated at 10:10pm, 20 Sep, main changes)
(old version)

(video)

Section 16.1
4
Greedy 2: Minimum Spanning Trees

(video 1, 0:51:00-end)
(video 2)

Chapter 23 (you may skip Kruskal's algorithm)
5
Greedy 3: Huffman Codes

(video 1)
(video 2)

Section 16.3
6
Dynamic Programming 1: Pitfall of Recursion

(video)

Section 15.1
7
Dynamic Programming 2: Rod Cutting

(content in the video of Lect 6)

Section 15.1
8
Dynamic Programming 3: Dependency

(video)

Section 15.4
9
Dynamic Programming 4: Longest Common Subsequence

(content in the video of Lect 8)

Section 15.4
10
Dynamic Programming 5: Optimal BST

(video 1)
(video 2, start-00:28)

Section 15.5
11
Graph 1: (Review) DFS and White Path Theorem

(video, 00:28-end)

Section 22.3
12
Graph 2: Strongly Connected Components

(video 1)
(video 2)

Section 22.5
13
Graph 3: (Review) SSSP with Non-Negative Weights - Dijkstra

(video)

Sections 24.2 and 24.3
14
Graph 4: SSSP with Arbitrary Weights - Bellman-Ford

(video)

Sections 24.1 and 24.5
15
Graph 5: Max-Flow (non-testable)

(The first video of this lecture was not captured successfully)
(video 1)
(video 2)

Sections 26.1 and 26.2
16
Approximation Algorithms 1: Vertex Cover and Max-3SAT

(video)

Sections 35.1 and 35.4 (you can ignore linear programming)
17
Approximation Algorithms 2: Traveling Salesman

(video)

Section 35.2
18
Approximation Algorithms 3: Set Cover and Hitting Set

(video 1)
(video 2, start - 00:52:00)

Section 35.3
19
Approximation Algorithms 4: k-Center (updated at 11:44pm, 25 Nov, main changes)
(old version)

(video 1, 00:52:00 - end)
(video 2)

--

There will be no more lectures.

Tutorial Material


Week 2
Growth of Functions
(video, by Yuchen Zhong)
(video, by Shiyuan Deng)
Week 3
Three Basic Techniques
(video, by Ru Wang)
(video, by Lijun Lang)

Week 4
Divide and Conquer
(video, by Shiyuan Deng)
(video, by Xilin Dang)
Week 5
Implementation of Prim's
(video, by Ru Wang)
(video, by Yuchen Zhong)

Week 6
Dynamic Programming: Piggyback, Dependency, and Space
(video, by Shiyuan Deng)
(video, by Lijun Lang)

Week 7
Matrix-Chain Multiplication
(video, by Xilin Dang)
(video, by Ru Wang)

Week 8
Proof of the White-Path Theorem
(video, by Shiyuan Deng)
(video, by Yuchen Zhong)

Week 9
SCC: Further Insights
(video, by Ru Wang)
(video, by Lijun Lang)

Week 10
No tutorials (university congregation)

Week 11
Bellman-Ford: Negative Cycles
Proof for finding a negative cycle (non-testable)

(video, by Shiyuan Deng)
(video, by Xilin Dang)
Week 12
All Pairs Shortest Paths
(video, by Ru Wang)
(video, by Lijun Lang)

Week 13
Set Cover and Hitting Set
(video, by Xilin Dang)
(video, Shiyuan Deng)


There will be no more tutorial notes.

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)
List 8 (Solutions)
List 9 (Solutions)
List 10 (Solutions)
List 11 (Solutions)
List 12 (Solutions)
List 13 (Solutions)

There will be no more regular exercises.

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
List 8
List 9
List 10
List 11
List 12
List 13

There will be no more special exercises.

Quizzes and Exams

Quiz 1 Solutions, Avg = 87.9, Std. Dev. = 19.7
Midterm Exam Solutions, Avg = 66.5, Std. Dev. = 18.7, Top 30
Quiz 2 Solutions, Avg = 79.6, Std. Dev. = 24.8
Quiz 3 Solutions, Avg = 66.6, Std. Dev. = 15.9
Final Exam Solutions, Avg = 71.1 (full mark 125), Std. Dev. = 22.8, Top 30