COL 757: Model centric Algorithm Design (3-0-2)Semester II 2016-2017Instructor : Sandeep Sen |
Prerequisite: COL 351 (Algorithms and Data Structures or equivalent
The design and analysis of algorithms is critically dependent on the model (environment) that it is running, where as, most of our learning is limited to textbook models (sequential RAM). For the same problem, the notions of upper and lower bounds depend on the model and therefore the conventional textbook algorithms often do not perform satisfactorily. We will take up some common environements and some basic problems and revisit designing algorithms in a more general paradigm. The nature of the course will be theoretical and like an algorithms course. The topics covered in the course will include:
1. The RAM model and its limitations, Introduction to alternate algorithmic models Parallel models like PRAM and Interconnection networks; Basic problems like Sorting, Merging, Routing, Parallel Prefix and applications, graph algorithms like BFS, Matching
2. Memory hierarchy models; Caching, Sorting, Merging, FFT, Permutation, Lower bounds Data Structures - searching, Priority queues
3. Streaming Data models: Distinct items, frequent items, frequency moments, estimating norms, clustering
4. On line algorithms: competitive ratio, list accessing, paging, k-server, load-balancing, lower-bounds.
Attendence related Scribing and class participation will count for 5%. Note that students having less than 75% attendence will be reported for possible penal action according to the attendence rules of the institute.
An introduction to Parallel Algorithms by Joseph Ja Ja , Addison Wesley
Introduction to Parallel Algorithms and Architectures, F.T. Leighton, Morgan Kauffman.
Algorithms and data structures for external memory , Jeff Vitter, pub: NOW.
Data Stream Algorithms Amit Chakravarti, Dartmouth College.