CSE 6311: ADVANCED COMPUTATIONAL MODELS AND ALGORITHMS

This course aims at exploring advanced computation models, theory and advanced algorithm design and analysis techniques that have broad applicability in solving real-life problems in cross-disciplinary areas. The course will consist of three parts: (a) the theory of NP-completeness, (b) approximation techniques to cope with intractability, and (c) randomized techniques.

Prerequisites:

CSE 5311 or consent of instructor

Grading:

3 non-cumulative exams worth 1/3 weight each

References:

• Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022
• Michael R. Garey, David S. Johnson: Computers and Intractability: A guide to the theory of NP-completeness, 1979
• Jon Kleinberg, Eva Tardos: Algorithm Design, 2005
• Rajeev Motwani, Prabhakar Raghavan: Randomized Algorithms, 1995

As the instructor for this course, I reserve the right to adjust this schedule in any way that serves the educational needs of the students enrolled in this course --Gautam Das

Course Introduction

Complexity Hierarchy

Date	Day	Topic
23-Jan	Monday	Course Introduction Complexity Hierarchy Introduction to Reductions and Polynomial Reductions
30-Jan	Monday	No class.
6-Feb	Monday	Polynomial Reductions NP Complete problems: 3SAT, Clique, Vertex Cover, Max Independent Set
8-Feb	Wednesday	MAKE-UP class, Subset sum, 3 dimensional matching, Exact cover by 3 sets Graph coloring, Subgraph isomorphism,Steiner tree
13-Feb	Monday	Hamiltonian Cycle/Path, Scheduling TSP, Knapsack, Bin Packing NPHardness, PSPACE
20-Feb	Monday	Review
27-Feb	Monday	Exam 1 Exam 1 Discussion
6-Mar	Monday	Introduction to Approximation algorithms, Vertex Cover and Maximum Independent Set	[Slides] [Video][Example] [Slides] [Video]
13-Mar	Monday	No Class - Spring Break
20-Mar	Monday	Introduction to LP and ILP LP for shortest path ILP Approximation for Vertex Cover Introduction to PTAS, FPTAS Naive algorithm for subset sum	[Slides] [Video] [Example] [Shortest Path] [Slides] [Additional Slides] [Video] [Slides] [Video]
27-Mar	Monday	FPTAS for Subset Sum TSP 2-Approximation TSP Christofides Algorithm	[Slides] [Video] [Detailed video] [Slides] [Video] [Slides] [Video] [Detailed Video]
3-Apr	Monday	Set cover approximation Review	[Slides] [Video]
10-Apr	Monday	Exam 2 Exam 2 Discussion
17-Apr	Monday	Introduction to randomized algorithms, Las Vegas/Monte Carlo paradigms, Randomized Quicksort, Min cut Probabilistic kth largest, Max 3 SAT	[Slides] [Video] [Slides] [Video]
24-Apr	Monday	Markov/Chebyshev inequalities,Chernoff bound and applications, Probabilistic classes PP and ZPP	[Slides] [Video] [Slides] [Video]
1-May	Monday	Probabilistic routing Randomized rounding (Max-SAT) Review	[Slides] [Video] [Slides] [Video] [T1Q1] [T2Q1] [T2Q2] [T3Q1] [T3Q2] [T4Q1] [T4Q2] [T4Q3] [T4Q4] [PDF]
8-May	Fri	Final Exam, 4-6:50 PM

Apr 24, 2023

HW3: [PDF]

Feb 22, 2023

Scribe notes: [PDF]

Feb 9, 2023

Practice questions for Exam 1: [PDF]

Feb 6, 2023:

There will be a make-up class on Feb 8, 17:15 to 19:00. Location: ERB 228

Jan 28, 2023:

The class venue is changed to ERB 228 effective this week till end of the semester in order to make it more convenient for everyone.

Jan 16, 2023:

While emailing the TA please add the words "CSE6311" to the subject. For example, if you are sending an email to set up an appointment, the subject would be "CSE6311: Requesting Appointment". Please follow this convention in order to ensure that your email does not get categorized as spam.

Jan 16, 2023:

This website is the official page for all information to be conveyed to the class. Please keep an eye for any new announcement which is posted here.

Jan 16, 2023:

Please take some time to read the University Policy and Ethics statement.