## Instructor : Sandeep Sen

### Lectures:

Slot X, IIA 425 Tue, Fri 9 - 10:30 am

### Teaching Assistant:

• Shashank Sharma (shashank@cse.iitd.ac.in )

Prerequisite: COL 351 (Algorithms and Data Structures or equivalent

### Topics:

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.

### Organization:

Grading will be based on two minors (20% each), Major (35%) and Assignments (20%) including some group programming assignments. Note that it is a 3-0-2 course. Audit pass requirement Minimum 50% aggregate.

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.

### Reference books

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.

Sandeep Sen