CSE 6311: ADVANCED COMPUTATIONAL MODELS AND ALGORITHMS

 

 

Class Details

Course:
CSE 6311
Location:
ERB 103
Timings:
TuTh 3:30PM - 4:50PM

Instructor Details

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

GTA Details

GTA:
Saravanan Thirumuruganathan
Office:
ERB 505
Email:
saravanan DOT thirumuruganathan [AT) MAVS [dot) UTA [dot) edu
Office Hours:
Fr 2-5pm or by appointment on Tu and Th
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
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, 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

Schedule
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
20-JanTue Course Introduction
22-JanThu Complexity Hierarchy
27-JanTue Polynomial Reductions
29-JanThu NP Complete problems: 3SAT, Clique, Vertex Cover, Max Independent Set
3-FebTue Subset Sum
5-FebThu 3 dimensional matching, Exact cover by 3 sets
10-FebTue Graph coloring, Subgraph isomorphism,Steiner tree
12-FebThu Hamiltonian Cycle/Path, Scheduling
17-FebTue TSP, Knapsack, Bin Packing
19-FebThu NP hardness,PSPACE
24-FebTue UTA Closed due to Snow!
26-FebThu Introduction to Approximation algorithms, Vertex Cover and Maximum Independent Set
3-MarTue Exam I
5-MarThu UTA Closed due to Snow!
10-MarTue No Class - Spring Break
12-MarThu No Class - Spring Break
17-MarTue TSP Approximation and PTAS
19-MarThu Set cover approximation
24-MarTue Submodular Functions and their optimization
26-MarThu Introduction to LP and ILP
31-MarTue ILP Approximation for Vertex Cover
2-AprThu FPTAS for Subset Sum
7-AprTue Exam II
9-AprThu Introduction to randomized algorithms, Las Vegas/Monte Carlo paradigms, Randomized Quicksort
14-AprTue Randomized Quicksort, Min cut
16-AprThu Exam 2 Discussion
21-AprTue Max 3 SAT, MAX-SAT, Probabilistic kth largest
23-AprThu Markov/Chebyshev inequalities, Union bound
28-AprTue Chernoff bound and applications, Coupon Collector Problem
30-AprThu Probabilistic classes PP and ZPP, Occupancy problems
5-MayTue Probabilistic Routing
7-MayThu Review
14-MayThu Final Exam, 2-4:30 PM

Announcements
Apr 28, 2015
Practice questions for Exam 3 is here [PDF] .
Mar 3, 2015
Practice questions for Exam 2 is here [PDF] .
Feb 9, 2015
Practice questions for Exam 1 is here [PDF] .
Jan 30, 2015:
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 30, 2015:
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 30, 2015:
Please take some time to read the University Policy and Ethics statement.