## COMP 5711 - Advanced Algorithms

Fall Semester 2022-23

Number of Students: 39

Average Rating by the Students: 4.58/5.0

## Covered topics

Amortized Analysis

Splay Trees

Disjoint Sets

Minimum Spanning Trees

Binomial and Fibonacci Heaps

Randomized Algorithms

QuickSort, QuickSelect, MinCut, Max-3-SAT, LazySelect

Randomized Complexity Classes

Markov, Chebyshev and Chernoff Bounds

The Probabilistic Method

Treaps and Skip Lists

Polynomial Identity Testing

Parameterized Algorithms

Branching and Color Coding

Kernelization and Iterative Compression

XP and FPT

Treewidth and Pathwidth

Algebraic Parameterized Algorithms

Approximation Algorithms

Register Allocation, Knapsack, Bin Packing, Makespan Minimization

LP-based Approximation

DNF Counting and Counting Perfect Bipartite Matchings

Markov Chains

## 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:

Giovanna Kobus Conrado, gkc@connect.ust.hk

Ahmed Zaher, akazaher@connect.ust.hk

## 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:

[KT] Algorithm Design, by Kleinberg and Tardos.

[CLRS] Introduction to Algorithms (3rd edition), by Cormen, Leiserson, Rivest, and Stein.

[MR] Randomized Algorithms, by Motwani and Raghavan.

[CF+] Parameterized Algorithms, by Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk and Saurabh.

## 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.

Models of Computation, especially Turing Machines, RAM and Word RAM

Modules 1 and 2 of https://www.udacity.com/course/computability-complexity-algorithms--ud061 (You can optionally watch modules 3, 4 and 5 if you are especially interested in this topic)

Asymptotic Notation (O, o, Θ, θ, Ω, ω)

Chapter 3 of CLRS

Basic Sorting (Selection Sort, Insertion Sort, Radix Sort)

Merge Sort and Quick Sort

Divide and Conquer Algorithms and Master's Theorem

Chapter 4 of CLRS

Heaps and Heapsort

Linked Lists

Binary Search Trees and AVL trees

Basic Dynamic Programming

Graph Traversal Algorithms (DFS and BFS)

Shortest-path Algorithms (Dijkstra, Floyd-Warshall, Bellman-Ford)

NP-hardness and NP-completeness

Modules 6, 7 and 8 of https://www.udacity.com/course/computability-complexity-algorithms--ud061

Basics of Discrete Probability and Enumerative Combinatorics

Basics of Linear Algebra

## Covered Topics

Module 1: Amortized Analysis

Lecture 1: Basics of Amortization, Vectors, Counters, Splay Trees

Lecture 2: Disjoint Sets with Union, Kruskal's Algorithm

Lecture 3: Heaps (Binary, Binomial and Fibonacci)

Module 2: Randomized Algorithms

Lecture 4: Randomized QuickSort and MinCut

Lecture 5: Randomized Complexity Classes

Lecture 6: Binary Min-Max Trees

Lecture 7: Game-theoretic Methods

Lecture 8: Markov and Chebyshev Inequalities, Coupon Collector

Lecture 9: Lazy Select

Lecture 10: Chernoff Bounds and the Probabilistic Method

Lecture 11: Treaps and Skip Lists

Lecture 12: Shortest Paths in an Unweighted Graph

Module 3: Parameterized Algorithms

Lecture 13: Introduction, FPT, XP

Lecture 14: Branching and Color Coding

Lecture 15: Kernelization and Iterative Compression

Lecture 16: Treewidth, Pathwidth and Treedepth

Lecture 17: Dynamic Programming and Kernelization using Treewidth

Lecture 18: Color Coding

Lecture 19: Polynomial Identity Testing

Module 4: Approximation Algorithms

Lecture 20: Greedy Algorithms, PTAS and FPTAS

Lecture 21: Register Allocation and Knapsack

Lecture 22: Bin Packing and Makespan Minimization

Lecture 23: Approximation by Linear Programming

Lecture 24: Approximate Counting, DNF

Lecture 25: Perfect Bipartite Matchings

## Grading

Homeworks: 4 x 10 points

You will normally be allowed to resubmit the exercises after receiving feedback from the TAs. However, we reserve the right to disallow resubmission if the original submission is of a very low quality or shows a lack of effort.

All solutions must be submitted as pdf files created by LaTeX. We do not accept any other format. Handwritten solutions are unacceptable. However, you can include hand-drawn figures in your solution if they help explain it more concisely.

Make sure you submit sufficiently before the deadlines to avoid any last-minute problems. Late assignments will not be accepted. We use Canvas as the source of truth and do not accept submissions by any other means.

Final exam: 60 points

This is a 3-hour open-book written exam at the end of the semester. You are allowed to bring as much printed or hand-written material on the day of the exam as you wish. Laptops, phones, and all other electronic devices are strictly prohibited.

## 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

Lecture 1: Amortization and Splay Trees (Video)

Recommended Reading: Chapter 17 of CLRS

Lecture 2: Disjoint Sets and Kruskal's Algorithm (Video)

Recommended Reading: Chapter 21 of CLRS, including 21.4

Lecture 3: Binary Heap, Binomial Heap, Fibonacci Heap (Video)

Recommended Reading: Chapter 19 of CLRS

## Randomized Algorithms

Lecture 4: Randomized QuickSort and MinCut (Video)

Recommended Reading: Sections 1.1 to 1.4 of MR

Lecture 5: Randomized Complexity Classes (Video)

Recommended Reading: Section 1.5 of MR and the videos on NP-hardness linked in the syllabus

Lecture 6: Binary Min-Max Trees (Video)

Recommended Reading: Section 2.1 of MR

Lecture 7: Runtime Bounds, QuickSelect, Max3SAT (Video)

Recommended Reading: Section 2.2 of MR

Lecture 8: Markov and Chebyshev Inequalities (Video)

Recommended Reading: Sections 3.1, 3.2 and 3.6 of MR

Recommended Watching: Expected Value of a Geometric Random Variable

Lecture 10: Chernoff Bounds and the Probabilistic Method (Video)

Lecture 11: Treaps and Skip Lists (Video)

Note: The example rotation I performed on the treap was wrong. The general version (with a, b, c, d, e vertices) is correct and should be followed instead. Sorry.

## Parameterized Algorithms

Lecture 16: Introduction to Treewidth and Pathwidth (Video)

Note: the definition of nice tree decomposition in lecture is incomplete. It is fixed in the notes.

Lecture 17: Dynamic Programming and Kernelization using Treewidth (Video)