Class Details

CSE 6311
ERB 228
Monday 4:00PM - 6:50PM

Instructor Details

Dr. Gautam Das
Microsoft Teams(preferable) or NH - Dean's office
Office Phone:
817 272 7595
gdas [AT) uta [DOT) edu
Office Hours:
Monday 3:00-4:00 pm (Microsoft Teams preferably) or by appointment
Faculty Profile:

GTA Details

Suraj Shetiya
ERB 509
suraj [DOT) shetiya [AT) MAVS [dot) UTA [dot) edu
Office Hours:
Monday 7:00-8:00 pm (ERB 509)
About this course
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.

Course Logistics
CSE 5311 or consent of instructor
3 non-cumulative exams worth 1/3 weight each
  • 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-JanMonday Course Introduction Complexity Hierarchy

Introduction to Reductions and Polynomial Reductions
30-JanMonday No class.
6-FebMonday Polynomial Reductions

NP Complete problems: 3SAT, Clique, Vertex Cover, Max Independent Set
8-FebWednesday MAKE-UP class,

Subset sum, 3 dimensional matching, Exact cover by 3 sets

Graph coloring, Subgraph isomorphism,Steiner tree
13-FebMonday Hamiltonian Cycle/Path, Scheduling

TSP, Knapsack, Bin Packing

NPHardness, PSPACE
20-FebMonday Review
27-FebMonday Exam 1

Exam 1 Discussion
6-MarMonday Introduction to Approximation algorithms, Vertex Cover and Maximum Independent Set

[Slides] [Video][Example]

[Slides] [Video]

13-MarMonday No Class - Spring Break
20-MarMonday 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-MarMonday FPTAS for Subset Sum

TSP 2-Approximation

TSP Christofides Algorithm
[Slides] [Video]

[Detailed video]

[Slides] [Video]

[Slides] [Video] [Detailed Video]

3-AprMonday Set cover approximation

[Slides] [Video]

10-Apr Monday Exam 2

Exam 2 Discussion
17-AprMonday Introduction to randomized algorithms, Las Vegas/Monte Carlo paradigms, Randomized Quicksort, Min cut

Probabilistic kth largest, Max 3 SAT
[Slides] [Video]

[Slides] [Video]
24-AprMonday Markov/Chebyshev inequalities,Chernoff bound and applications,

Probabilistic classes PP and ZPP
[Slides] [Video]

[Slides] [Video]

1-MayMonday Probabilistic routing

Randomized rounding (Max-SAT)

[Slides] [Video]

[Slides] [Video]

[T1Q1] [T2Q1] [T2Q2] [T3Q1] [T3Q2] [T4Q1] [T4Q2] [T4Q3] [T4Q4] [PDF]

8-MayFri 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.