CSCI3160 Design and Analysis of Algorithms

Offered by Yufei TAO, Fall 2019. Tutors: Xiaojie GAO (xjgao@cse), Shangqi LU (sqlu@cse), Yi WANG (yiwang@cse), and Jianwen ZHAO (jwzhao@cse). 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.

Announcements

News 31 (28 Nov): The university will give you two more options regarding your grade in this course: (i) Option 1: You may do a LATE DROP. This means you will need to take the course again in a later semester; (ii) Option 2: You can opt for a PASS/FAIL grade. This means that the grade will not be included in your GPA calculation. News 30 (19 Nov): Following the university's announcement, there will be no more classroom lectures in this semester. The instructor will upload videos as a remedy. News 29 (7 Nov): Exercise List 10 and Special Exericse List 10 released. News 28 (4 Nov): This Thu's lecture will be canceled due to the university congregation. News 27 (2 Nov): Exercise List 9 and Special Exericse List 9 released. News 26 (2 Nov): You may now come to the instructor's office to collect your midterm papers. The stats and solutions can be found at the bottom of this page. News 25 (29 Oct): You may now come to the instructor's office to collect your Quiz 2 papers. The stats of Quiz 2 can be found at the bottom of this page. News 24 (25 Oct): The Midterm exam will be held in the Wed lecture next week (i.e., 30 Oct). It will start at 11:30pm and will be 40 minutes long. The scope covers everything in Lec Notes 1-9. 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 23 (25 Oct): Exercise List 8 and Special Exericse List 8 released. News 22 (18 Oct): Exercise List 7 and Special Exericse List 7 released. News 21 (14 Oct): Quiz 2 will take place in the Thu lecture next week (i.e., 24 Oct). It will start at 12:30pm and will be 20 minutes long. The scope covers everything in Lec Notes 5-8. The quiz is open book. News 20 (10 Oct): Exercise List 6 and Special Exericse List 6 released. News 19 (10 Oct): You may now come to the instructor's office to collect your Quiz 1 papers. The stats of Quiz 1 can be found at the bottom of this page. News 18 (9 Oct): Today's lecture will be given in the tutorials, namely, the lecture will be repeated 3 times. News 17 (4 Oct): Exercise List 5 and Special Exericse List 5 released. News 16 (30 Sep): Clarification of the Open Book policy: You can bring in any printed or hand-written material. Electronic products, however, cannot be used. News 15 (27 Sep): Exercise List 4 and Special Exericse List 4 released. News 14 (25 Sep): Quiz 1 will take place in the Thu lecture next week (i.e., 2 Oct 3 Oct). It will start at 12:30pm and will be 20 minutes long. The scope covers everything in Lec Notes 1-4. The quiz is open book. News 13 (19 Sep): Exercise List 3 and Special Exercise List 3 released. News 12 (15 Sep): No more lecture recordings will be made, unless the student union announces that the movement should continue. News 11 (14 Sep): A discussion forum has been created in the Blackboard system. The purpose of the forum is to facilitate discussions among the students. While the instructor and TAs would look at the forum and post answers to some questions , they do so on a voluntary base. For this reason, the forum is not a reliable channel for you to ask questions (neither is it intended to be one). You can make appointments with the instructor or TAs for that purpose. News 10 (14 Sep): Videos of this week's lectures posted. News 9 (11 Sep): There was an unfortunate typo about the day of Tutorial Session 2 -- it should be Wed, instead of Thu. It is my mistake (not a mistake of the TAs); and I apologize. Students of Session 2 can email me to make an appointment for a one-to-one make-up tutorial (taught either by me or by one of the TAs). News 8 (11 Sep): Exercise List 2 and Special Exercise List 2 released. News 7 (5 Sep): Video of the lecture on Sep 5 posted. News 6 (5 Sep): There has been a change of venue for tutorial Session 1: from Lady Shaw Bldg C2 to William M W Mong Eng Bldg 404. News 5 (5 Sep): Video of the lecture on Sep 4 posted. News 4 (5 Sep): Exercise List 1 and Special Exercise List 1 released. News 3 (4 Sep): There will be three quizzes in this course. Quiz 1, 2, and 3 will be held in the Thu lecture of Week 5, 8, and 13, respectively. The midterm exam will take place in the Wed lecture of Week 9. News 2 (3 Sep): No tutorials this week. News 1 (1 Sep): Hello, all.

Time and Venues

Lectures Wed 11:30am - 12:15pm William M W Mong Eng Bldg LT Thu 12:30pm - 2:15pm William M W Mong Eng Bldg LT Tutorials Session 1 Wed 12:30PM - 1:15PM William M W Mong Eng Bldg 404 Session 2 Thu Wed 2:30pm - 3:15pm William M W Mong Eng Bldg 803 Session 3 Wed 4:30PM - 5:15PM Lady Shaw Bldg LT4 Click here for a map of the campus.

Grading Scheme

In-Class Quiz 1: 4% In-Class Quiz 2: 6% In-Class Quiz 3: 8% Midterm Exam: 32% Final Exam: 50% Style of Exams: During this course, the instructor will gradually generate a list of special exercises without the 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 of the lecture on Sep 4 -- Warm Up 2 Performance Measurement by Worst Input Video of the lecture on Sep 5 -- 1 Recursion 1: Hanoi Tower and GCD (Updated at 1:45pm, 11 Sep) Main changes: included the proofs of the claims "GCD(n, m) = GCD(n, m-n)" and "GCD(n, m) = GCD(n, m mod n)". Old Version Section 31.2 2 Recursion 2: k-Selection Video of the lecture on Sep 12 Section 9.2 (the textbook's algorithm requires a more tedious analysis, as discussed in a regular exercise). 3 Divide and Conquer: Counting Problems and Matrix Multiplication Video of the lecture on Sep 13 Sections 4.1 and 4.2 (actually the problem in Sec 4.1 is a regular exercise) 4 Greedy 1: Activity Selection Section 16.1 5 Greedy 2: Minimum Spanning Trees Chapter 23 (you may leave out Kruskal's algorithm) 6 Greedy 3: Huffman Codes (Updated at 10am, 4 Oct) Major changes: Formalized the notion of "code tree" on Slide 7. Old version Section 16.3 7 Dynamic Programming 1: The First Example Section 15.1 (the core of the section will be discussed in a regular exercise) 8 Dynamic Programming 2: Optimal BST Section 15.5 9 Dynamic Programming 3: Edit Distances (Updated at 3pm, 17 Oct) Major changes: Simplified the proof in Slides 22-32. Old version 2 Major changes: Revised the proof in Slides 22-32. Old version 1 Section 15.4 (the core will be discussed in a regular exercise) 10 Graph 1: Positive-Weight Shortest Paths Sections 24.2 and 24.3 11 Graph 2: Arbitrary-Weight Shortest Paths (Updated at 9:30pm, 8 Dec) Major changes: On slide 22, the value for f should be -7 after relaxing (g, f). Old version Sections 24.1 and 24.5 12 Graph 3: All-Pairs Shortest Paths Sections 25.2 and 25.3 Following the university's announcement, the remaining lectures have been canceled due to the social unrest. The instructor will release online videos as a remedy. 13 Computational Complexity 1: Decision Problems and P Lecture video Section 34.1 14 Computational Complexity 2: NP Lecture video Section 34.2 15 Computational Complexity 3: NP-Complete and NP-Hard Lecture video (Optional) Sections 34.3 and 34.4 16 Computational Complexity 4: NP-Completeness of the Clique Problem Lecture video Section 34.5.1 17 Aproximation Algorithms: Vertex Cover and Set Cover Lecture video Sections 35.1 and 35.3 There will be no more lecture notes.

Tutorial Material

Week 2 Growth of Functions and Solving Recurrences The instructor will attend Session 1. Week 3 Deterministic k-Selection (not required in quizzes and exams) The instructor will attend Session 2. Week 4 Material prepared by Yi Wang: Achieving O(n log n) time for Counting Problems The instructor will attend Session 3. Week 5 Material prepared by Xiaojie Gao: Fast Implementation of Prim's Algorithm The instructor will attend Session 1. Week 6 Material prepared by Jianwen Zhao: Fractional Knapsack (not required in quizzes and exams) The instructor will attend Session 2. Week 7 Material prepared by Shangqi Lu: Rod-Cutting The instructor will attend Session 3. Week 8 Material prepared by Yi Wang: Verifying Edit Distances (not required in quizzes and exams) The instructor will attend Session 1. Week 9 Material: DFS The instructor will attend Session 2. Week 10 Material prepared by Jianwen Zhao: SSSP on DAGs and Negative Cycle Detection The instructor will attend Session 3. Week 11 Material: Finding Strongly Connected Components The instructor will attend Session 1. No more tutorials after the university terminated the semester at Week 10.

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) (Updated on 23 Oct). List 6 (Solutions). List 7 (Solutions). List 8 (Solutions). List 9 (Solutions). List 10 (Solutions). No more exercises are required after the university terminated the semester at Week 10.

Special Exercises

As mentioned earlier, 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 (e.g., you may discuss them with your friends, the tutors, or even the instructor himself). Remember: during the exams, you will be allowed to consult only one piece of single-sided A4-sized paper. In other words, it is unrealisic to hope that you can write down all the solutions on that paper. You will need to comprehend the solutions to make sure you can answer them correctly in the exams. Special exercises in general are easier than regular exercises. List 1. List 2 (Updated on 25 Sep). List 3. List 4 (Updated on 17 Oct). List 5. List 6. List 7. List 8. List 9. List 10. No more exercises are required after the university terminated the semester at Week 10.

Quizzes and Exams

Quiz 1 Solutions Quiz 2 Solutions Midterm Solutions Quiz 1 Stats: max = 100, average = 70.1, standard deviation = 27.2. Quiz 2 Stats: max = 100, average = 84.3, standard deviation = 19.6. Midterm Stats: max = 100, average = 54.6, standard deviation = 23.4. Top 25 scores (class size 169). Updated top 25 scores Quiz 3 and the final exam are canceled following the university's announcement at Week 10 that the semester was terminated.