CS 535 SPRING-2009 
Design and Analysis of Algorithms

TR 5-6.15

Books:

Introduction to Algorithms: Cormen, Leicerson, Rivest and Stein (CLRS) , MIT Press

Algorithm Design and Analysis: Dexter Kozen, Springer-Verlag

Algorithm Design: Kleinberg and Tardos, Addison-Wesley.

Algorithms by Dasgupta, Papadimtriou and Vazirani.

Combinatorial Optimization: Papadimitriou and Steiglitz, Dover.                                                                                                                                                                  

PRE-REQUISITE: CS430

Students are expected to know elementary algorithms and data structures for
Searching and  sorting, heaps
Introductory applications of greedy , divide and conquer and dynamic programming techniques.
Graph problems

Homework 0 (hw0-que.txt) - this homework is to check your  own fluency with the prerequisites, in turn, to self-assess whether you should take CS535 

 

Syllabus

Part 1 Design techniques and data structures advances :

(o) Motivation for Algorithm Design-

Minimum Spanning Tree

            (i)  Advanced schemes for selection and sorting

Binomial Heaps

Fibonacci heaps and applications in Minimum Spanning Trees             

(ii) Divide and Conquer: advanced applications. 

(iii) Greedy Method and Matroids

(iv) Dynamic programming- applications in shortest paths

(v) Linear programming and Duality-applications in shortest paths.

(vi) Randomized algorithms and Data structures

 

Part 2: Specific Problems and techniques 

(vii) Graph Algorithms—bi-connectivity, strong-connectivity, planarity*

 (viii) Flows in Networks, Matching.

 (ix) String Matching

Part 3: Complexity and intractability  

(x) Lower Bounds*

(xi) NP-Complete Problems   

(xii) Approximation Algorithms*

•   advanced topics  to be covered time-permitting.

 

Course  Requirements

Homeworks- 40%- Homework Policy: Students are allowed to discuss with each other but write individual answers. All consultation must be documented. No consultation of the web is allowed.

Exams: 60%- Two exams. The exams would primarily be Take-Home exams. Take-Home exams will be required to be submitted within 24 hours. I will announce more on this later. The exams must represent individual work only.

Exams / Homeworks

Submission - If you are submitting hardcopy, either hand it over to TA in his office hours or leave it in TA mailbox located in SB235.  If you are submitting softcopy, use digital dropbox in blackbox. 

       

Links to relevant papers

 

Reading List

Instructor:

Sanjiv Kapoor
e-mail: kapoor@iit.edu
telephone: 312-567-5329
Office Hours:  Tuesday, Thursday, 3-4.30p.m. and by appointment.
Room: 228B SB

Teaching Assistant:

TBA