COMP 7713/8713 Advanced Topics Algorithms (Spring 2021)


Lecture hours and location

M W : 2:20 - 3:45 PM, DH 124.

Instructor Information

Name: Nirman Kumar
Office: Dunn Hall 307
Phone: (901) 678-3135
Home page : http://www.cs.memphis.edu/~nkumar/
Office hours : TBA

Course Description

The main focus of this course is algorithms whose aim is to combat intractability of problems. We will cover basic approximation algorithms, and some fixed-parameter algorithms. We will also cover the topic of randomization.


Textbook

We will mainly cover some material from "Algorithm Design by Jon Kleinberg and Eva Tardos". We will also use "Invitation to Fixed-Parameter algorithms by Rolf Niedermeier". See the Course Syllabus here.

Schedule (Tentative)

Date Item Relevant link
W Jan 20th Introduction to the course and Approximation algorithms. - 2 approx. Minimum Makespan sched. Sec 11.1 KT
M Jan 25th Approximation algorithms - MMS contd. (1.5 approx), k-center clustering Sec 11.1, Sec 11.2 KT
W Jan 27th Approximation algorithms - k-center clustering contd. Sec 11.2 KT
M Feb 1st Approximation algorithms - Set Cover Sec 11.3 KT
W Feb 3rd Approximation algorithms - Pricing Method (Vertex Cover) Sec 11.4 KT
M Feb 8th Approximation algorithms - Pricing method contd. (Disjoint paths) Sec 11.5 KT
W Feb 10th Approximation algorithms - LP and rounding (Vertex cover again) Sec 11.6 KT
M Feb 15th LECTURE CANCELLED - SNOW STORM
W Feb 17th LECTURE CANCELLED - SNOW STORM
M Feb 22nd LECTURE CANCELLED - CAMPUS WATER PROBLEM , HW1 HW1
W Feb 24th LP rounding : Generalized Load Balancing Sec 11.7 KT
M Mar 1st LP rounding wrap up and Local Search Sec 11.7 KT and Sec 12.1 KT
W Mar 3rd Local Search contd. and HW1 due Sec 12.2 KT and Sec 12.3 KT
M Mar 8th No Lecture
W Mar 10th Randomized algorithms Sec 13.1
M Mar 15th Randomized algorithms Sec 13.2
W Mar 17th Randomized algorithms Sec 13.3
M Mar 22nd Randomized algorithms and HW2 Sec 13.4, 13.9, and HW2
W Mar 24th Randomized algorithms Sec 13.10 and Sec 13.11
M Mar 29th Randomized algorithms Sec 13.11 wrap up
W Mar 31st FPT Sec 10.1 and Sec 10.2
M Apr 5th FPT and HW2 due and HW3 Sec 10.2 contd. and Sec 10.3, HW3
W Apr 7th FPT Sec 10.3 wrap up
M Apr 12th Lecture postponed
W Apr 14th Lecture postponed
F Apr 16th Special lecture cancelled HW3 due and HW4 HW4
M Apr 19th Tree decomposition Sec 10.4
W Apr 21st Tree decomposition contd. Sec 10.4 wrap up
M Apr 26th Tree decomposition contd. Sec 10.5
F Apr 30th 10 - 11:30 AM: Student presentations, and HW4 due