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:

Weekly Quizzes(Combined) 10% weight and 3 non-cumulative exams worth 30% weight each

References:

• Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009
• 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

Date	Day	Topic	Resources
27-Jan	Mon	Course Introduction Complexity Hierarchy
3-Feb	Mon	Polynomial Reductions NP Complete problems: 3SAT, Clique, Vertex Cover, Max Independent Set
10-Feb	Mon	Subset Sum,3 dimensional matching, Exact cover by 3 sets Graph coloring, Subgraph isomorphism,Steiner tree
17-Feb	Mon	Hamiltonian Cycle/Path, Scheduling TSP, Knapsack, Bin Packing
24-Feb	Mon	NP hardness,PSPACE Review
2-Mar	Mon	Exam 1 Exam 1 Discussion
9-Mar	Mon	No Class - Spring Break
16-Mar	Mon	No Class - Extended Spring Break
23-Mar	Mon	Introduction to Approximation algorithms and Vertex Cover Discussion on Maximum Independent Set	[Slides] [Video][Example] [Slides] [Video] [Class Discussion]
30-Mar	Mon	Introduction to LP ILP Approximation for Vertex Cover PTAS, FPTAS and naive algorithm for subset sum FPTAS for Subset Sum	[Slides] [Video] [Example] [Slides] [Additional Slides] [Video] [Slides] [Video] [Slides] [Video] [Detailed video] [Class Discussion]
6-Apr	Mon	TSP 2-Approximation TSP Christofides Algorithm Set cover approximation Quiz 1 Review Weekly Quiz	[Slides] [Video] [Slides] [Video] [Detailed Video] [Class Discussion] [Slides] [Video] [Q1Q1] [Q1Q2] [Q1Q3] [Q1Q4] [Q1Q5]
13-Apr	Mon	Exam 2 Discussion Weekly Quiz
20-Apr	Mon	Exam (Take-Home) 2 Introduction to randomized algorithms, Las Vegas/Monte Carlo paradigms, Randomized Quicksort Monte Carlo Algorithms, Min cut, Max 3 SAT	[Exam 2 Solutions Discussion] [Slides] [Video] [Slides] [Video]
27-Apr	Mon	Exam 2 Review Session Markov/Chebyshev inequalities,Chernoff bound and applications Probabilistic classes PP and ZPP	[Exam 1 and 2 grading discussion] [Slides] [Video] [Slides] [Video]
4-May	Mon	Weekly Quiz (Final Quiz - on topics uploaded by Friday, May 1st) Home Work 3 Discussion (on topics uploaded by Friday, May 1st) Final Exam Discussion Probabilistic routing Randomized rounding (Max-SAT)	[T1Q1] [T2Q1] [T2Q2] [T3Q1] [T3Q2] [T4Q1] [T4Q2] [T4Q3] [T4Q4] [PDF] [Slides] [Video] [Slides] [Video]
08-May (Special Session)	Fri 04:00-05:00 PM	Discussion on Examination III	[Final Discussion]
11-May	Mon	Final Exam (Take-home), 04:00 PM-08:00 PM

Apr 28, 2020

Practice questions for Exam 3: [PDF]

Apr 02, 2020

Practice questions for Exam 2: [PDF]

Feb 8, 2020

Practice questions for Exam 1: [PDF]

Jan 21, 2020:

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 21, 2020:

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 21, 2020:

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