The
Chinese University of Hong KongAnnouncements
2022.4.26 Final Exam Submission: Upload
Graphs are everywhere.
Do you see graphs and graph problems from the following: 3D printing, Rubik's cube, and pearl necklace?
How many vertices do you need as a certificate to convince a friend that a graph
contains a k-vertex cover, i.e., k vertices that cover all edges?
For a computer monitor where each pixel has one of three colours,
how to find in no time two same-coloured pixels of distance d apart?
What problem does the following algorithm solve?
Randomly mark each vertex of a graph, and return neighbours of marked vertices as output.
Lecture: M10:30-12:15 (Wu Ho Man Yuen 303) and T10:30-11:15 (Lee Shau Kee 302)
by Prof. CAI
Leizhen (Office hours: TBA) Grading scheme (tentative): Homework (50%), and Exam or Course Project (50%) The course discusses fundamental graph algorithms and FPT (fixed-parameter tractable) algorithms.
We focus on creative ideas and useful techniques in designing graph algorithms,
for instance, a general greedy paradigm for minimum spanning trees,
Johnson's reweighting technique for shortest paths, and
interesting applications of network flows. For about 2/3 of the course, we will discuss FPT algorithms
for solving NP-hard graph problems.
An FPT algorithm confines the exponential time of an algorithm for
an NP-hard problem to some part of the input, called parameter k,
and therefore solves the problem efficiently for small k,
which can be very useful in practice.
For instance, the classical problem of finding a vertex cover of size k
in an n-vertex graph can be solved in time O(1.2738exp(k) + kn) by an FPT algorithm of Chen, Kanj and Xia (2005),
which makes the problem solvable in practice for graphs with 1,000,000,000,000 vertices as far as k < 150.
We note that a straightforward exhaustive search algorithm takes around O(n exp(k)) time,
which can hardly handle instances with n = 100 and k = 10.
We will discuss various tools for designing FPT algorithms: from basic tools
(bounded search tree, and kernelization) to novel tools (iterative compression of
Reed, Smith and Vetta, colour coding of Alon, Yuster and Zwick,
and random separation of Cai, Chan and Chan).
We will also discuss the theory for fixed-parameter intractability,
which is akin to the theory of NP-completeness. Prerequisite: CSCI2110 and CSCI3160 or their equivalents.
Final Exam: Exam Paper.
2022.4.19 Final Exam: Open book by ZOOM (April 26, Tuesday 2-4pm).
Exam questions are no harder than homework questions, and the
style of the exam is similar to
Sample Exam Quesions.
2022.4.19 HW3 submission (due 5pm April 19): Closed
Late submission until 6pm with 20% deduction of marks.
In case you're unable to upload your file successfully,
please email it Su Chong (csu@cse.cuhk.edu.hk) with subject "5320HW4-SID".
2022.4.08 Homework 4 posted (due 5pm April 19)
2022.3.22 HW3 submission (due 5pm March 22): Closed
Late submission until 6pm with 20% deduction of marks.
In case you're unable to upload your file successfully,
please email it Su Chong (csu@cse.cuhk.edu.hk) with subject "5320HW3-SID".
2022.3.08 Homework 3 posted (due 5pm March 22)
2022.3.01 Pre-recorded lectures for the next two weeks (W9 and W10)
are available under Lecture Notes, just in case.
2022.3.01 HW2 submission (due 5pm March 1): Closed
Late submission until 6pm March 1 with 20% deduction of marks.
In case you're unable to upload your file successfully,
please email it Su Chong (csu@cse.cuhk.edu.hk) with subject "5320HW2-SID".
2022.2.16 All lecture videos are available under Lecture Notes, and you can
watch these lectures together with lecture notes in case I'm unable to teach online because of the worsening COVID-19 situation.
2022.2.15 Homework 2 posted (due 5pm March 1)
Submission of HW2-Q1 (5pm 21 Feb): Closed
2022.2.08 Homework 1 submission: Closed
Late submission of HW1 until 8pm Feb 14 with 50% deduction of marks.
In case you're unable to upload your file successfully,
please email it Su Chong (csu@cse.cuhk.edu.hk) with subject "5320HW1-SID".
2022.1.25 Homework 1 posted under "Assignments" (due 5pm Feb 14).
2022.1.24 Online class until further notice.
Zoom Class: https://cuhk.zoom.us/j/709267134?pwd=T3FFTXFiMWhsRk1QbDRRSTJ2RFRoZz09
Meeting ID: 709 267 134 Passcode: 009941
2022.1.21 Notes 2 and 3 updated.
2022.1.07 First Class.
Course Information
Course
Outline
References
