Department of Computer Science and Engineering, IIT Kanpur

CS345: Algorithm

Dr. R. K. Ghosh

Lecture Topics & Notes

Lecture notes will be typeset either in LaTeX or HTML. The lecture notes typeset in LaTeX are provided in postscript format which can be viewed by launching ghostview or can be printed by postscript printer. A few of these won't fit in width in portrait (P) mode. Therefore, are provided as separate postscript files marked as landscape (L).

These lecture notes are meant strictly for references to the students registered in Algorithms course during the semester 2003-2004-II. No part of the lecture notes should be reproduced in any form -- electronic or any other means -- without the express permission from the instructor.

  • Lecture 1-4: Computational Models

    RAM model, RASP model, Straightline programming model, Bitwise model, Multitape Turing machine.

pp. 1-56 (P)

  • Lecture 5-8: Divide and Conquer

    Median finding, Selection problem, Closest pair of points, Convex hull, Optimal sequence alignment. For other example recall interger multiplication, Strassen's matrix multiplication done in the first course.

pp. 130-141 (P) pp. 150-160 (P) pp. 161-176 (P) pp. 177-197 (P)

  • Lecture 9-12: Greedy Algorithms

    Greedy algorithms, Weighted Matroids, MST and unit time scheduling. Other examples: Hoffman coding and fractional knapsack done in the first course earlier.

pp 232-256 (P)

  • Lecture 13-16: Backtracking

    Exhaustive search versus backtracking, Backtracking solution templates (recursive and non-recursive), Turnpike reconstruction problem, Eight queens problem, Generation of permutation, Efficiency estimates of 8-queen algorithm, Knight's tour, Hamiltonian cycle, Graph coloring.

pp 311-343 (P), pp 344-356 (P) pp 357-373 (P)

  • Lecture 17-21: Branch and Bound

    Differences between backtracking and branch and bound approach. FIFO and LIFO branch and bound. 8-puzzle, properties of a cost function for bounding search, symmertic and asymmetric Traveling Salesman Problem.

pp 374-383 (P), pp 384 (P), pp 385-412 (P)

  • Lecture 22-27: Network flows

    Network flow graphs, Matrix Rounding and other applications, Ford-Fulkerson algorithm, Max-flow Min-cut theorem, Preflow push algorithm for network flows, bipartite matching, edge disjoint path in directed/undirected graphs (Menger's theorem).

pp 413-507 (P)

  • Lecture 28-32: Linear Programming

    Linear Programming, Simplex Method, Slack and Surplus variables, Geometric view of LPP.

pp 508-563 (P)

  • Lecture 33-35: Amortised Running Time

    Accounting method, and potential method. Examples: Multipop stack operation, and binary counter increment. UNION-FIND.

pp 583-617 (P)

  • Lecture 36-39: Graph Planarity

    Euler's Formula, Biconnected Components, Vertex Addition Algorithm, PQ-trees.

pp 618-660 (P)

  • Lecture 40-42: Parallel Algorithms

    Flynn's classifications, PRAM model, Prefxi sum, Pointer jumping.

pp 784-835 (P)

Page last updated 30 Jan, 2003 by R. K. Ghosh