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 2002-2003-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: Summation

  Arithmetic, Geometric and Harmonic series sums. Sums using differentiation. Computing sums by telescoping, bounding terms, splitting. Approximation of sums by definite integrals. Converting product into sums.

pp. 1-18 (P)

• Lecture 2-3: Recurrence, Proof techniques

  Substitution, iteration techniques, Recursion tree, Master theorem, General solution of recurrence homogeneous and non-homgeneous equations, Invalid proof techniques, Proof by contradiction, Proof by induction.

pp. 19-40 (P), pp. 41-50 (P), pp. 51-65 (P)

• Lecture 4-6: Divide and Conquer

  Quick sort, Median finding, Selection problem, Integer multiplication, Strassen matrix multiplication, Closest pair of points, Convex hull.

pp. 66-82 (P) pp. 83-89 (P) pp. 90-109 (P)

• Lecture 7-8: Greedy Algorithms

  Greedy algorithms, Huffman coding scheme, Fractional Knapsack problem, Shortest Path problem, MST, Weighted Matroids.

pp. 110-122 (P), pp. 123-124 (L), pp. 125-133 (P), pp. 134 (L),
pp. 135-143 (P), pp. 144-156 (P)

• Lecture 9-12: Dynamic Programming Algorithms

  Dynamic Programming, Matrix chain product, Balanced parenthesization, Steps of dynamic programming, Optimal substructure property, Overlapping subproblems, Memoization, Longest common subsequence problem, Polygon triangulation.

pp. 157-165 (P), pp. 166 (L), pp. 167-176 (P), pp. 177(L), pp. 178-186 (P),
pp. 187(L), pp. 188-193 (P), pp. 194-203 (P), pp. 204(L), pp. 205-207 (P),
pp. 208(L), pp. 209-210 (P)

• Lecture 13-16: Backtracking

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

pp. 211-223 (P), pp. 224-240 (P), pp. 241-262 (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, Traveling salesman problem,

pp 263-272 (P), pp 273 (L), pp 274-283 (P), pp 284-294 (P)

• Lecture 21-22: Games

  Minimax: a framework for two player games, Tic-tac-toe. Nim, Alpha-beta pruning.

pp 295-313 (P)

• Lecture 23-24: Amortised Running Time

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

pp 314-334 (P)

• Lecture 25-29: NP Completeness

  P-time deterministic algorithms, Intractable problems, Decision problem, Converting optimization problems to decision problems, Encoding, Formal language framework, 1-tape Turing machine, Nondeterministic Turing machine, A Nondeterministic computational model, Nondeterministic polynomial time algorithms for sorting and satisfiability, Satisfiability, P, NP and their relatives, NP hard problems, Reducibility, Circuit satisfability, 3-SAT, 3-D Matching, Minimum vertex cover, Maximum independent set, Maximum clique.

pp 335-388 (P), pp 389-399 (P), pp 400-419 (P), pp 420-436 (P)

• Lecture 30-34: Parallel Algorithm

  Parallel algorithms, Parallel computational model, Taxonomy of parallel architetures: SISD, SIMD, MISD, MIMD, SPMD, and Handler's classifications, PRAM Models: EREW, CREW, and CRCW -- arbitrary, common, priority, collision, tolerant, combining, Balanced binary tree paradigm: broadcast, reduction, Parallel sums and prefix sums, pointer jumping, parallel merging, Amdhal's law, Gustafson-Barsis law, Distributed memory machine: Mesh n/w, Binary tree n/w, Pyramid n/w, Butterfly n/w, Hypercube n/w, Shuffle-exchange n/w.

pp 437-481 (P), pp 482-495 (P), pp 496-507 (P)