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 NPhard/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 19. You will be allowed to bring in a singlesided, A4sized, 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 58. 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 handwritten 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., 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 onetoone makeup 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
Tutorials
Click here for a map of the campus. 

Grading Scheme  
InClass Quiz 1: 4% InClass Quiz 2: 6% InClass 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 singlesided, A4sized, 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 selfcontained, namely, containing all the details required in this course. Lecture attendance is vital to grasp the material taught.
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.
There will be no more lecture notes. 

Tutorial Material  
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 singlesided A4sized 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. Quiz 3 and the final exam are canceled following the university's announcement at Week 10 that the semester was terminated. 

