CS 430
SUMMER
2008
Introduction
to Algorithms
Books:
Required: Introduction to Algorithms: Cormen, Leicerson, Rivest and Klein, MIT Press.
Further Reference: (i) Algorithm Design, Kleingberg and Tardos, Addison-Wesley.
PRE-REQUISITE: CS 330, CS331
Syllabus
The course is divided into 3 parts:
|
|
TOPIC |
|
|
PART 1: Introduction to Complexity and Design Techniques: |
1. Introduction to Algorithm Design, Complexity analysis including elementary tools like O-Notations, Recurrence Relations
|
Chapter 1-4 CLRS (Corman, Leicerson et al) |
|
2. Divide and Conquer: Searching and Sorting. - Quicksort, Mergesort, Heaps and Heapsort, Lower bound on sorting, Binary Search Trees, Balanced Binary Search Trees (AVL Trees, 2-3 trees/ Red-Black trees) |
Chapter 6-9 CLRS Chapter 12-13 CLRS |
|
|
3. Introduction to Dynamic Programming Application to the Traveling Salesman Problem, Knapsack Problem, Optimum Triangulation of Convex Polygons etc.. |
Chapter 15 CLRS |
|
|
4. Greedy Methods Huffman Encoding. MST etc. |
Chapter 16 CLRS |
|
|
5. Amortized Analysis |
Chapter 17 CLRS |
|
|
PART II: Data Structures and Analysis |
6. Searching I - Hash Functions and Hashing, |
Chapter 11 CLRS |
|
7. Advanced Structures: Binomial Heaps, Union Find data structures |
Chapter 19-21 CLRS |
|
|
PART III: Specific Problems and NP-Completeness |
8. Graph Algorithms I - Depth First Search, Breadth First search, Bi-connectivity, Topological Sort |
Chapter 22 CLRS |
|
9. Graph Algorithms II - Minimum Spanning Trees, Shortest Paths, All Pairs Shortest paths |
Chapter 23,24,25 CLRS |
|
|
10. NP-Completeness and coping with Hard Problems |
Chapter 34,35 CLRS |
The reading omits all sections marked * in CLRS, except when specified.
Home Assignments: 20%
Exams: 70%-There
will be 2 exams, July 2nd and July 23,
Project: -A small programming project-10%. Please plan for it in consultation with the TA /Instructor. Groups of 2 can be formed.
Homework Policy: All Home Assignments are to be done independently. If you must take help it must be acknowledged.
The project can be done in groups (groups of size 2 preferred) and would require design and implementation of an algorithm or an experiment comparing various algorithms. Each group decides on its own project in consultation with teaching staff.
Submission - If you are submitting a hardcopy, either hand it over to TA in his office hours or leave it in TA mailbox located in SB235.
If you are submitting a softcopy, use the digital drop-box in Black-Board. If you are a remote student, use (i) drop-box (ii) Fax: 312-567-5067
(iii) IITV courier.
Instructor:
Prof. Sanjiv Kapoor
e-mail: kapoor@iit.edu
telephone: 312-567-5329
Office Hours: Monday 11.30-12.30, 2.00-2.3.0, Wednesday,
Room: 228B SB
T.A.
Yogesh Vedpathak, yvedpath@iit.edu.