CS5800 Advanced Data Structures and Algorithms

July - Nov 2019

Coordinates

  • Where: CS 36
  • When: C slot; Mon (10 - 10.50 am), Tue (9 - 9.50 am), Wed (8 - 8.50 am), Fri (12 - 12.50 pm)

TAs

  • Amit Kumar (cs16s032@smail)
  • Amit Kumar Roy (cs18s022@smail)
  • Om Prakash (cs16d017@smail)
  • Sagar Bisoyi (cs17s020@smail)
  • Sampriti Roy (cs18s007@smail)
  • Shahbaz Husain (cs18m049@smail)

Objectives

The course is intended to provide the foundations of the practical implementation and usage of algorithms and data structures. One objective is to ensure that the student evolves into a competent programmer capable of designing and analyzing implementations of algorithms and data structures for different kinds of problems. The second objective is to expose the student to the algorithm analysis techniques, to the theory of reductions, and to the classification of problems into complexity classes like NP.

Contents

The course will introduce algorithm design techniques, methods to formally prove the correctness of algorithms, design of efficient data structures and techniques to analyse the running time of the algorithms. The skeleton of the topics covered in the course will be as follows. The order of the topics covered may vary.

  • Basics of algorithm design, techniques for analyzing worst-case time complexity of algorithms.
  • Divide-and-Conquer design technique.
  • Design and analysis of greedy algorithms.
  • Amortized analysis of algorithms.
  • Dynamic programming.
  • Cuts and flows.
  • Computational intractability - Why do some problems not have efficient algorithms?
  • Coping with computational intractability.

References

  • [CLRS]: Introduction to Algorithms - Cormen, Leiserson, Rivest and Stein, 3rd Edition.
  • [DPV]: Algorithms - Dasgupta, Papadimitrou, and Vazirani, 1st Edition.
  • [E]: Algorithms - Jeff Erickson
  • [KT]: Algorithm Design - Kleinberg and Tardos, 1st Edition.

Grading policy

  • Short-exams(Best 2/3): 20%
  • Quizzes: 2*20 = 40%
  • End-sem: 40%

Important dates

  • Tutorials: Aug 9, Aug 30, Sep 20, Oct 11, Nov 1
  • Short exams: Aug 23, Sep 27, Nov 8
  • Quizzes: Sep 7, Oct 19
  • End-sem: Nov 19

Course Materials