Class Details

CSE 6311
GS 233
Mon 4:00PM - 6:50PM

Instructor Details

Dr. Gautam Das
ERB 626
Office Phone:
817 272 7595
gdas [AT) uta [DOT) edu
Office Hours:
Mon 3:00 PM-4:00 PM Or, By Appointment
Faculty Profile:

GTA Details

Shohedul Hasan
ERB 509
shohedul DOT hasan [AT) MAVS [dot) UTA [dot) edu
Office Hours:
Fri 1:00 pm-3:50 pm (Microsoft Team)
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
Weekly Quizzes(Combined) 10% weight and 3 non-cumulative exams worth 30% weight each
  • 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-JanMon Course Introduction

Complexity Hierarchy
3-FebMon Polynomial Reductions

NP Complete problems: 3SAT, Clique, Vertex Cover, Max Independent Set
10-FebMon Subset Sum,3 dimensional matching, Exact cover by 3 sets

Graph coloring, Subgraph isomorphism,Steiner tree
17-FebMon Hamiltonian Cycle/Path, Scheduling

TSP, Knapsack, Bin Packing
24-FebMon NP hardness,PSPACE

2-MarMon Exam 1

Exam 1 Discussion
9-MarMon No Class - Spring Break
16-MarMon No Class - Extended Spring Break
23-MarMon Introduction to Approximation algorithms and Vertex Cover

Discussion on Maximum Independent Set
[Slides] [Video][Example]

[Slides] [Video]

[Class Discussion]
30-MarMon 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-AprMon TSP 2-Approximation

TSP Christofides Algorithm

Set cover approximation

Quiz 1


Weekly Quiz
[Slides] [Video]

[Slides] [Video] [Detailed Video]

[Class Discussion] [Slides] [Video]

[Q1Q1] [Q1Q2] [Q1Q3] [Q1Q4] [Q1Q5]
13-AprMon Exam 2 Discussion

Weekly Quiz
20-AprMon 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-MayMon 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]
(Special Session)
04:00-05:00 PM
Discussion on Examination III [Final Discussion]
11-MayMon 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.