CSE 5095: Approximation, Randomized, and Fixed Parameter Algorithms

Fall 2013

Instructor: Mukul Bansal, 359 ITEB, mukul@engr.uconn.edu

Time and place: Tu-Th 5:00--6:15 PM. CAST 201.

Office Hours: Mo 3:00--5:00 PM or by appointment.

Course Description

This is an advanced algorithms course designed for those students who have already previously taken the graduate level algorithms course CSE 5500. Topics covered in this course include approximation algorithms, randomized algorithms, and fixed parameter algorithms. This course will introduce students to new algorithmic ideas and teach them how to (i) develop effective, polynomial-time algorithms for NP-hard problems despite their computational intractability, and (ii) make use of randomness to design simpler and more efficient algorithms.

Prerequisites: CSE 5500

Syllabus and textbook: We will use the book "Algorithm Design" by Kleinberg and Tardos. Specifically, we will cover chapters 8, 10, 11, 12, and 13 from this book (as well as some material from previous chapters, as needed). This will be supplemented by other material from various sources.

Grading: Grading will be based on 6 or 7 homework assignments (60%), a final project (30%), and class participation (10%). Homework will be assigned bi-weekly. The final project will consist of reading a few algorithmic research papers and demonstrating your ability to understand and build on the ideas presented in them through a class presentation. Further details on the project as well as a list of papers will be made available approximately midway through the course. There will not be any exams in this course.

Course policies: Homework solutions can be either hand written or printed/typed and must be turned in at the beginning of class on the due date (or earlier). Late submission is allowed, but at a penalty of 20% of the maximum grade per day. Students are permitted to discuss general concepts and questions concerning the homework assignments, but sharing solutions with others or using solutions provided by others, in part or in whole, is prohibited.

Homework Assignments


A list of possible papers for the project is available here.

Final paper assignments are listed here.

Instructions and guidelines for the project are available here.

The presentation schedule is available here.

Last updated on Dec. 11, 2013