↢ Back to the List of Courses

COMP 5711 - Advanced Algorithms

Fall Semester 2022-23

Number of Students: 39

Average Rating by the Students: 4.58/5.0 

Covered topics

YouTube Playlist

https://youtube.com/playlist?list=PLzZlJT-UOiwApHQGR03fu3M1WNdsrsVat&si=6bJUVJ4WXG1-F_bT 

Course Files

https://drive.google.com/drive/folders/1EXpt-IJ4s0LZf2NQO_gGmpva0amb3dsI

Course Syllabus

Scroll further down to the next section for the contents of the course.

Course Description

This is a graduate course covering advanced topics in algorithm design and data structures. We will see a very wide variety of techniques and tools such as amortized analysis, randomization, parameterization, kernelization, and approximation algorithms.

People

Instructor: Amir Goharshady, goharshady@cse.ust.hk 

You can ask me any question at any time by email. I usually answer on the same day, but please be patient in case there is a large backlog of questions. My office hours are Wednesdays 1-3 pm. During this time, you can drop by my office at IAS 2003 (Institute for Advanced Study Building) with prior notice.

Teaching Assistants:

Time and Place

Tuesdays and Thursdays, 1:30 PM - 2:50 PM, Room 2407, Lift 17-18

Reference Books

The course is self-contained. Videos and lecture scribes will be provided to the students after each session. The following books are recommended for further reading:

Required Background and Self-Study

Students should already have a strong background in algorithms and data structures. For UST students, the necessary background is usually obtained by passing courses such as 2711H, 3711, and 3721. Since this is a core graduate course, it is expected that most students have done their UG studies elsewhere or are focused on non-algorithmic aspects of computer science. Nevertheless, we assume the students have working knowledge in the topics below. Students whose background in algorithms is not sufficient must obtain mastery of all the following topics by self-study. In each case, links are provided to youtube videos or other resources that cover the topic in the required depth. You are strongly advised to watch these videos before the course or in its first two or three weeks at the latest. Note that one truly learns an algorithm only by coding it. So, you should try and implement all the algorithms listed below, as well as the algorithms covered in the course, and experiment with them.

Covered Topics

Module 1: Amortized Analysis

Module 2: Randomized Algorithms

Module 3: Parameterized Algorithms

Module 4: Approximation Algorithms

 

Grading

 

 

Grade Appeals

You can appeal your grades by sending an email to goharshady@cse.ust.hk with the title "5711: Grade Appeal". The appeals must be submitted within 24 hours after receiving the grades for each assignment or exam. Late appeals will not be accepted.

 

Notes on Writing Algorithms and Proofs

Your solutions will be judged not only for correctness but also for the clarity and conciseness of your presentation. For questions that involve designing an algorithm, you should typically (i) give an overview of the main ideas, (ii) present pseudocode or plain language description of the algorithm, (iii) present an analysis (usually, of the running time) of your algorithm, and (iv) provide a proof or justification of correctness when correctness is not obvious. The TAs have the right to dismiss unusually long solutions and assign a grade of 0.

 

Zero-tolerance Policy on Plagiarism and Academic Misconduct

We will enforce a strict zero-tolerance policy on plagiarism and academic misconduct. Every single case of dishonest behavior in the homeworks and the final exam will lead to a grade of F and will be reported to the department/school, causing a cheating record on the offending student's transcript. Of course, the student will be allowed to appeal and there will be due process.

To be more clear about the rules, note that you are allowed to discuss the homeworks with other classmates, but each student has to write their own solution without any external input. Your solutions should not be just copies of each other or extremely similar. Moreover, you are allowed to google the problems and use any external source to solve them, as long as you write your final solution on your own. Writing the solution on your own means that you should open an empty LaTeX file and write everything from scratch, without copying even one word. Finally, note that your right to discuss the homeworks ends as soon as you receive feedback from us on your submission.

Amortized Analysis

 Randomized Algorithms

 Parameterized Algorithms

Approximation Algorithms