COL 757: Model centric Algorithm Design (3-0-2) Semester II 2016-2017 Instructor : Sandeep Sen

Lectures:

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.

  Preliminary Lecture Notes

  Assignments

  Problem Set 1
  Solutions

  Programming Assignment 1

  Minor 1 solutions

  Problem Set 2
  

  Minor 2 solutions

  Solutions

  Problem Set 3

  Problem Set 4
  

  Major solns

  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
  Last modified: Mon July 2006