Class Details

CSE 6311
WH 308
TuTh 3:30PM - 4:50PM

Instructor Details

Dr. Gautam Das
ERB 626
Office Phone:
817 272 7595
gdas [AT) uta [DOT) edu
Office Hours:
TuTh 2:30-3:30 pm or by appointment
Faculty Profile:

GTA Details

Sona Hasani
ERB 508
sona DOT hasani [AT) MAVS [dot) UTA [dot) edu
Office Hours:
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, 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
16-JanTue Course Introduction
18-JanThu Complexity Hierarchy
23-JanTue Polynomial Reductions
25-JanThu NP Complete problems: 3SAT, Clique, Vertex Cover, Max Independent Set
30-JanTue Subset Sum,3 dimensional matching, Exact cover by 3 sets
1-FebThu Graph coloring, Subgraph isomorphism,Steiner tree
6-FebTue Hamiltonian Cycle/Path, Scheduling
8-FebThu TSP, Knapsack, Bin Packing
13-FebTue NP hardness,PSPACE
15-FebThu Review
20-FebTue Exam 1
22-FebTue Exam 1 Discussion
27-FebThu Introduction to Approximation algorithms, Vertex Cover and Maximum Independent Set
1-MarThu Introduction to LP and ILP
6-MarTue ILP Approximation for Vertex Cover
8-MarThu FPTAS for Subset Sum
13-MarTue No Class - Spring Break
15-MarThu No Class - Spring Break
20-MarTue Set cover approximation
22-MarThu TSP Approximation
27-MarTue Submodular Functions and their optimization
29-MarThu Review
3-AprTue Exam 2
5-AprThu Exam 2 Discussion
10-AprTue Introduction to randomized algorithms, Las Vegas/Monte Carlo paradigms, Randomized Quicksort
12-AprThu Randomized Quicksort, Min cut
17-AprTue Max 3 SAT, Probabilistic kth largest
19-AprThu Markov/Chebyshev inequalities, Union bound
24-AprTue Chernoff bound and applications, Coupon Collector Problem
26-AprThu Probabilistic classes PP and ZPP, Occupancy problems
1-MayTue probabilistic routing, randomized rounding (Max-SAT)
3-MayThu Review
10-MayThu Final Exam, 2-4:30 PM

Apr 27, 2018
Practice questions for Exam 3: [PDF]
Feb 14, 2018
Mar 24, 2018
Practice questions for Exam 2: [PDF]
Feb 14, 2018
Additional practice questions for Exam 1: [PDF]
Feb 6, 2018
Practice questions for Exam 1: [PDF]
Jan 16, 2018:
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, 2018:
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, 2018:
Please take some time to read the University Policy and Ethics statement.