CSCI3160 Design and Analysis of Algorithms

Offered by Yufei TAO, Fall 2024.

Tutors: Hao Chen (hchen22@link.cuhk.edu.hk), Xingyu Cui (xycui24@cse), Yifan Li (yfli24@cse), Zeju Li (lizeju@link.cuhk.edu.hk), Sipeng Sun (spsun24@cse), and Zhenxuan Xie (zxxie24@cse).

Offices and Consultation Hours:
  • Xingyu Cui: 10am-11am Mon, SHB 913
  • Zhenxuan Xie: 2pm-3pm Mon, SHB 913
  • Zeju Li: 4pm-5pm Mon, SHB 1026
  • Sipeng Sun: 2pm-3pm Tue, SHB 121
  • Yufei Tao: 3pm-4pm Tue, SHB 1019
  • Hao Chen: 4pm-5pm Wed, RM 404 Academic Building No. 1
  • Yifan Li: 5pm-6pm Fri, SHB 1024

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 17 (10 Dec): The final exam scores have been released on Blackboard. The solutions and statistics can be found in the "Quizzes and Exams" section of this page.

You may come to check your papers on Dec 13 from 10am to 4pm. The venue is Room 1021, Ho Sin-Hang Engineering Building. Please obey the following rules:
  • You cannot take your paper away. We are required to archive all the final exam papers.
  • You are not allowed to take pictures of the question paper or the answer book.
  • You may check the papers of your friends, provided that you can provide evidence of their consent.
No additional paper-checking sessions will be arranged. However, you may submit a grade appeal after the grade release in accordance with university guidelines.

News 16 (3 Dec): Quiz 3 scores have been posted on Blackboard. The solutions and statistics can be found at the bottom of the page. You may now collect your papers from the TAs assigned to your IDs (see News 9).

News 15 (21 Nov): Quiz 3 will start at 11:30am in the lecture of Nov 27. The scope covers Lecture 15 and Lectures 17-20.

News 14 (16 Nov): The final exam will start at 9:30am, Dec 9. We will arrange for you to review your final exam papers on Dec 13 from 10am to 4pm. The detailed instructions will be released later.

News 13 (12 Nov): Quiz 2 scores have been posted on Blackboard. The solutions and statistics can be found at the bottom of the page. You may now collect your Quiz 2 papers from the TAs assigned to your IDs (see News 9).

News 12 (31 Oct): Quiz 2 will start at 11:30am in the lecture of Nov 6. The scope covers everything from Lecture 10 to 14.

News 11 (22 Oct): The midterm scores have been released on Blackboard. The solutions and statistics can be found in the "Quizzes and Exams" section of this page. You may now collect your exam papers from the TAs assigned to your IDs (see News 9). To do so, visit their offices during the designated consultation periods.

News 10 (10 Oct): The midterm exam will take place in next Wed's lecture. The scope covers everything from "Warm up 1" to Lecture 9. Please search for "Style of Exams" on this page to learn more about the exam, in particular, about special exercises and the note sheet you can bring to the exam.

News 9 (1 Oct): Quiz 1 scores have been posted on Blackboard. The solutions and statistics can be found at the bottom of the page.

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.
  • Hao Chen: 1155141529 - 1155184202
  • Xingyu Cui: 1155184446 - 1155191560
  • Yifan Li: 1155191562 - 1155192627
  • Zeju Li: 1155192635 - 1155193579
  • Sipeng Sun: 1155193590 - 1155194531
  • Zhenxuan Xie: 1155194577 - 1155232957
News 8 (Sep 23): All quizzes in this course are open book.

News 7 (Sep 21): Quiz 1 will start at 11:30am in the lecture of Sep 25. The scope covers everything from Warm Up 1 to Lecture 2.

News 6 (Sep 15): Regular Exercise List 1 and Special Exercise List 1 have been released. There will be no announcements for exercise releases. Please check this page periodically.

News 5 (Sep 5): 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.

News 4 (Sep 5): Please note the test schedule for this course:

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

News 3 (Sep 5): The video for Wed's lecture is now available. There will be no more announcements regarding video releases. Please check this page periodically.

News 2 (Aug 30): There will be no tutorials in the first week.

News 1 (Aug 29): 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/94014851875

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

Tutorials

Session 1 Thu 11:30am - 12:15pm Lady Shaw Bldg LT2
Session 2 Thu Mon 2:30pm - 3:15pm 6:30pm - 7:15pm Humanities Building 213 ERB 803
Session 3 Thu Tue 2:30pm - 3:15pm 6:30pm - 7:15pm Science Centre L5 LSB LT3
Session 4 Thu 4:30pm - 5:15pm Humanities Building 114

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
(video)

--
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
(video)

Section 16.1
4
Greedy 2: Minimum Spanning Trees
(video)

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

Section 16.3
6
Dynamic Programming 1: Pitfall of Recursion
(video)

Section 15.1
7
Dynamic Programming 2: Rod Cutting
(video)

Section 15.1
8
Dynamic Programming 3: Dependency
(unfortunately, this video was not captured successfully)

Section 15.4
9
Dynamic Programming 4: Longest Common Subsequence
(video)

Section 15.4
10
Dynamic Programming 5: Optimal BST
(video)

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

Section 22.3
12
Graph 2: Strongly Connected Components
(video 1, 1:08:00-end)
(video 2)

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

Sections 24.2 and 24.3
14
Graph 4: SSSP with Arbitrary Weights - Bellman-Ford
(video, 00:56:00-end)

Sections 24.1 and 24.5
15
Graph 5: All-Pairs Shortest Paths - Johnson's
(video)

Sections 25.2 and 25.3
16
Graph 6: Max-Flow (postponed to Week 13, non-testable)
(video 1)
(video 2)
(video 3) (proof of the max-flow min-cut theorem)

Sections 26.1 and 26.2
17
Approximation Algorithms 1: Vertex Cover and Max-3SAT
(video 1)
(video 2)

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

Section 35.2
19
Approximation Algorithms 3: Set Cover and Hitting Set (updated at 2:45am, 20 Nov)
(Old version)

(video 1, 01:13:00-end)
(video 2)

Section 35.3
20
Approximation Algorithms 4: k-Center
(video)

--

There will be no more lectures.

Tutorial Material


-->
Week 2
Growth of Functions

(video by Sipeng Sun)
(video by Zhenxuan Xie)

Week 3
Three Basic Techniques

(video by Yifan Li)
(video by Xingyu Cui)

Week 4
Divide and Conquer

(video by Hao Chen)
(video by Zeju Li)
Week 5
Implementation of Prim's

(video by Sipeng Sun)
(video by Zhenxuan Xie)
Week 6
Kruskal's Algorithm

(video by Xingyu Cui)

Week 7
Dynamic Programming: Piggyback, Dependency, and Space

(video by Sipeng Sun)

Week 8
Matrix-Chain Multiplication

(video by Zeju Li)
(video by Zhenxuan Xie)

Week 9
SCC: Further Insights

(video by Xingyu Cui)
(video by Yifan Li)

Week 10
The Floyd-Warshall algorithm for APSP

(video by Zeju Li)
Week 11
Bellman-Ford: Negative Cycles

(video by Sipeng Sun)

Proof for finding a negative cycle (non-testable)
Week 12
Reductions for Proving NP-Hardness

(video by Xingyu Cui)
(video by Hao Chen)

Week 13
Set Cover and Hitting Set

(video by Zeju Li)
(video by Yifan Li)


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
List 14

There will be no more special exercises.


Quizzes and Exams

Quiz 1 Solutions, Avg = 70.8, Std. Dev. = 24.2
Midterm Exam Solutions, Avg = 55.1, Std. Dev. = 19.8, Top 30 scores (class size = 211)
Quiz 2 Solutions, Avg = 82.7, Std. Dev. = 23.0
Quiz 3 Solutions, Avg = 78.9, Std. Dev. = 20.9
Final Exam Solutions, Avg = 54.7, Std. Dev. = 15.2, Top 30 scores (class size = 211)