CSE 6311: ADVANCED COMPUTATIONAL MODELS AND ALGORITHMS

 

 

Class Details

Course:
CSE 6311
Location:
ERB 228
Time:
Wed 4:00PM - 6:50PM

Instructor Details

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

GTA Details

GTA:
Sona Hasani
Office:
ERB 508
Email:
sona DOT hasani [AT) MAVS [dot) UTA [dot) edu
Office Hours:
Thu 10:00-11:30 am
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
16-JanWed Course Introduction

Complexity Hierarchy
23-JanWed Polynomial Reductions

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

Graph coloring, Subgraph isomorphism,Steiner tree
6-FebWed Hamiltonian Cycle/Path, Scheduling

TSP, Knapsack, Bin Packing
8-FebFri MAKE-UP class, 1:00 pm to 4:00 pm

Location: ERB 228
13-FebWed NP hardness,PSPACE

Review
20-FebWed Exam 1

Exam 1 Discussion
27-FebWed canceled
6-MarWed Introduction to Approximation algorithms, Vertex Cover and Maximum Independent Set

Introduction to LP and ILP
13-MarWed No Class - Spring Break
20-MarWed ILP Approximation for Vertex Cover

FPTAS for Subset Sum
27-MarWed Set cover approximation

TSP Approximation
3-AprWed Submodular Functions and their optimization

Review
10-Apr Wed Exam 2

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

Probabilistic kth largest, Max 3 SAT
24-AprWed Markov/Chebyshev inequalities,Chernoff bound and applications,

Probabilistic classes PP and ZPP
1-MayWed probabilistic routing, randomized rounding (Max-SAT)

Review
3-MayFri MAKE-UP. Location: NH 106. Time: 1:00 pm to 3:00 pm
10-MayFri Final Exam, 2-4:30 PM

Announcements
Apr 26, 2019
Practice questions for Exam 3: [PDF]
Apr 18, 2019
There will be a make-up class on Friday, May 3, 13:00 to 15:00. Location: NH 106.
Mar 28, 2019
Practice questions for Exam 2: [PDF]
Mar 19, 2019
Exam 2 is rescheduled to April 10!!
Feb 8, 2019
Practice questions for Exam 1: [PDF]
Feb 5, 2019:
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 28, 2019:
There will be a make-up class on Friday, Februry 8, 13:00 to 16:00. Location: ERB 228
Jan 16, 2019:
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, 2019:
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, 2019:
Please take some time to read the University Policy and Ethics statement.