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)