Learning Objectives

This is an intermediate course on algorithm design. The first part of this course is intended to make students familiar with some basic graph algorithms and their efficiency analysis. The second part of this course course will provide a detailed introduction to different algorithm design paradigms with illustrative problems. The third part of this course is looking at designing algorithms for the classical network flow problem. The last part of this course will deal with computationally hard problems and tackling them using approximation algorithms.

Learning Outcomes

  • To develop the ability to analyze the running time and prove the correctness of basic algorithms.
  • To be able to design efficient algorithms for moderately difficult computational problems, using various algorithm design techniques taught in the course.
  • To be able to prove the hardness of NP-Hard problems using simple reductions.
  • To be able to do performance analysis of simple approximation algorithms.

Syllabus

Review - asymptotic notation, graph search algorithms, topological sorting, computing shortest paths in unweighted graphs.

Graph Algorithms: minimum spanning tree algorithms - cut property, Kruskal's algorithm using disjoint sets, Prim's algorithm. Shortest path algorithms - Dijkstra's algorithm, Bellman-Ford algorithm, Floyd-Warshall algorithm.

Design paradigms: greedy algorithms - greedy choice, fractional knapsack, Huffman coding. Dynamic programming - optimal substructure and overlapping sub-problems, coin changing, integral knapsack. Backtracking eight-queen's problem.

Network Flow: max-flow min-cut theorem, Ford Fulkerson algorithm, Edmond's shortest path heuristic, bipartite matching using max-flow.

Complexity: NP-completeness, polynomial time reductions, classes NP and P, NP-complete problems.

Approximation algorithms: vertex cover via maximum matching, greedy algorithm for set cover.

Textbook

  1. Introduction to Algorithms (3rd Edition) by Thomas H. Cormen, Charles E. Leiserson, Ronald L Rivest, Clifford Stein. PHI Learning, 2009. ISBN:978-81-203-4007-7.
  2. Algorithm Design by Jon Kleinberg and Eva Tardos. Pearson, 2015. ISBN:978-93-325-1864.

Reference

  1. The Design and Analysis of Algorithms by Dexter C Kozen. Texts and Monographs in Computer Science, Springer, 1992. ISBN:0-387-97687-6.
  2. Algorithms by Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani. McGraw- Hill Education, 2006. ISBN: 978-0073523408.

Metadata

Proposing Faculty: Dr. Jasine Babu. Department: Computer Science and Engineering Programme: B.Tech Proposing date: Approved date: Proposal type: Offerings: