COMP 5711 - Advanced Algorithms
Fall Semester 2022-23
Number of Students: 39
Average Rating by the Students: 4.58/5.0
Fall Semester 2022-23
Number of Students: 39
Average Rating by the Students: 4.58/5.0
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
https://youtube.com/playlist?list=PLzZlJT-UOiwApHQGR03fu3M1WNdsrsVat&si=6bJUVJ4WXG1-F_bT
https://drive.google.com/drive/folders/1EXpt-IJ4s0LZf2NQO_gGmpva0amb3dsI
Scroll further down to the next section for the contents of the course.
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.
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
Tuesdays and Thursdays, 1:30 PM - 2:50 PM, Room 2407, Lift 17-18
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.
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
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
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.
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.
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.
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.
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
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.
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)