CSCI3160 Design and Analysis of Algorithms

Offered by Yufei TAO, Fall 2022. Tutors: Shiyuan Deng (sydeng@cse), Zhihan Jiang (zhjiang22@cse), Fanbin Lu (fblu21@cse), Hao Wu (hwu@cse), Ru Wang (rwang21@cse). Offices and Consultation Hours: Yufei Tao: 3pm-4pm Tue, SHB 1019 Shiyuan Deng: 3pm-4pm Tue, SHB 1013 Zhihan Jiang: 4pm-5pm Wed, SHB101a Fanbin Lu: 10am-11am Tue, SHB 117 Ru Wang: 2pm-3pm Wed, SHB 1013 Hao Wu: 2pm-3pm Fri, SHB 1013 Quick navigation links: [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 12 (26 Nov): Quiz 3 will be canceled with a full mark given to every one. News 11 (18 Nov): Your Quiz 2 scores have been released in Blackboard. You can now collect your paper from the TA responsible for your ID (see News 7). News 10 (3 Nov): The scope of Quiz 2 covers Lect Notes 6-11. News 9 (26 Oct): Your midterm scores have been released in Blackboard. You can now collect your paper from the TA responsible for your ID (see News 7). News 8 (13 Oct): The scope of the midterm exam covers everything from "Warm Up 1" to Lect. Notes 7. During the exam, you will be allowed to consult only a single-sided, A4-sided, note sheet. The exam will start at 11:30 am on Oct 19 and will be 90 minutes long. News 7 (6 Oct): Your Quiz 1 scores have been released in Blackboard. You can now collect your Quiz 1 papers from the TAs. Each TA handles a specific range of student IDs, as listed below: 1155096482 - 1155141593: Shiyuan Deng 1155141594 - 1155157143: Ru Wang 1155157155 - 1155158247: Fanbin Lu 1155158254 - 1155159204: Hao Wu 1155159267 - 1155191131: Zhihan Jiang Please identify the TA responsible for your ID and go to her/his office during her/his consultation hour to collect your paper. The offices and consultation hours of all TAs can be found at the top of the course homepage. News 6 (26 Sep): All quizzes will be open-book. News 5 (24 Sep): We will adopt the following policy for quizzes and the midterm exam. All students must take the tests (i.e., quizzes and the midterm exam) in the classroom, except for cases in point 2 and 3. If you are Covid positive, you need to report your case to the HK government at this site. You will receive a confirmation after completing the case reporting. Send the confirmation to Prof. Tao, and he will arrange a special test session for you. If you plan to be absent from a test by citing health reasons, you must email Prof. Tao at least one hour before the test and follow up with a doctor's letter. You will be allowed to take a make-up test that may be harder than the plenary test (how much harder will depend on the number of extra days you have to prepare for the test). News 4 (21 Sep): The scope of Quiz 1 includes everything except matrix multiplication and Lecture Notes 3. News 3 (10 Sep): Please note the test schedule for this course: Quiz 1 (20 minutes): To be held in the lecture of Sep 28 (Wed, Week 4) Midterm (90 minutes): In the lecture of Oct 19 (Wed, Week 7) Quiz 2 (20 minutes): To be held in the lecture of Nov 9 (Wed, Week 10) Quiz 3 (20 minutes): To be held in the lecture of Nov 30 (Wed, Week 13) News 2 (28 Aug): No tutorials in the first week. News 1 (28 Aug): Hello, all.

Time and Venues

Lectures Wed 11:30am - 1:15pm Science Center L1 Zoom Link: https://cuhk.zoom.us/j/94956720979 Thu 1:30pm - 2:15pm Science Center L1 Zoom Link: https://cuhk.zoom.us/j/92811440453 Tutorials Zoom Link for all tutorials: https://cuhk.zoom.us/j/99663063805 Session 1 Thu 11:30am - 12:15pm Science Centre LG23 Session 2 Thu 3:30pm - 4:15pm William M W Mong Eng Bldg 703 Mong Man Wai Bldg 703 Session 3 Thu 4:30PM - 5:15PM Basic Med Sci Bldg LT 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, 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 Techniques: Recursion, Repeating, and Geometric Series (old version) (video 1) (video 2, start-23:00) Section 9.2 (the textbook's algorithm requires a more tedious analysis, as discussed in a regular exercise). 2 Divide and Conquer (video 1, 23:00-end) (video 2) (video 3) Sections 4.1 and 4.2 3 Greedy 1: Activity Selection (video, start-00:43) Section 16.1 4 Greedy 2: Minimum Spanning Trees (old version, typos on Slides 8 and 18) (video 1, 00:43-end) (video 2) Chapter 23 (you may skip Kruskal's algorithm) 5 Greedy 3: Huffman Codes (old version, simplification on Slide 19 and typo on Slide 22) (video 1) (video 2, start-25:30) Section 16.3 6 Dynamic Programming 1: Pitfall of Recursion (video 1, 25:30-end) (video 2, start-00:28) Section 15.1 7 Dynamic Programming 2: Rod Cutting (video, 00:28-01:22) Section 15.1 8 Dynamic Programming 3: Dependency (video 1, 01:22-end) (video 2) Section 15.4 9 Dynamic Programming 4: Longest Common Subsequence (old version, added a paragraph on Slide 7) (video, white board) Section 15.4 10 (Review) DFS and White Path Theorem (video, start-00:57) Section 22.3 11 Strongly Connected Components (old version, modified the turn-black order) (video 1, 00:57-end) (video 2) Section 22.5 12 (Review) SSSP with Non-Negative Weights: Dijkstra (old version, added equality in the edge relaxation def. on Slide 7) (video, start-1:08:00) Sections 24.2 and 24.3 13 SSSP with Arbitrary Weights: Bellman-Ford (old version, added equality in the edge relaxation def. on Slide 11) (video 1, 1:08:00-end) (video 2) Sections 24.1 and 24.5 14 All-Pairs Shortest Paths (Old version, modified Slide 9) (video 1) (video 2, start-27:00) Sections 25.2 and 25.3 15 Approximation Algorithms 1: Vertex Cover and Max-3SAT (video 1, 27:00-end) (video 2) Sections 35.1 and 35.4 (you can ignore linear programming) 16 Approximation Algorithms 2: Traveling Salesman (video) Section 35.2 17 Approximation Algorithms 3: Set Cover and Hitting Set (video) Section 35.3 18 (Bonus) Approximation Algorithms 4: k-Center (video) (Not testable) -- There will be no more lectures.

Tutorial Material

Week 2 Growth of Functions (presented by Shiyuan Deng) (video) Week 3 Three Basic Techniques (presented by Wu Hao) (video) Week 4 Divide and Conquer (Presented by Ru Wang) (video) Week 5 Implementation of Prim's (Presented by Fanbin Lu) (video) Week 6 Kruskal's Algorithm (Presented by Zhihan Jiang) (video) Week 7 Dynamic Programming: Function Evaluation (Presented by Shiyuan Deng) (video) Week 8 Dynamic Programming: Recursive Structures (Presented by Hao Wu) (video) Week 9 SCC: Further Insights (Presented by Ru Wang) (video) Week 10 Bellman-Ford: Negative Cycles (Presented by Zhihan Jiang) Proof for finding a negative cycle (not testable) (video) Week 11 Floyd-Warshall: Negative Cycles (Presented by Fanbin Lu) (video) Week 12 No tutorials (university congregation) Week 13 SC and HS: Further Insights (Presented by Shiyuan Deng) (video) 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) 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 There will be no more special exercises.

Quizzes and Exams

Quiz 1 Solutions , Avg = 81, Std. Dev. = 19 Midterm Solutions, Avg = 62, Std. Dev. = 12, Top 30 (class size around 210) Quiz 2 Solutions , Avg = 76, Std. Dev. = 21