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). 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 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 Thu 1:30pm - 2:15pm Science Center L1 Tutorials Session 1 Thu 11:30am - 12:15pm Science Centre LG23 Session 2 Thu 3:30pm - 4:15pm William M W Mong Eng 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 -- Warm Up 2 Performance Measurement by Worst Input -- There will be no more lecture notes.

Tutorial Material

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.

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.

Quizzes and Exams