Algorithm Analysis & Design 

Algorithm Analysis Book 1 (Pages 89)

Introduction to Algorithm Analysis, Role of Algorithms in Computing, Insertion Sort, Analysing algorithms using the RAM model, Selection sort, Merge Sort, Growth of Functions, O-notation (Big_O), Gamma notation, Asymptotic notations in equations and inequalities, Little-O notation, Little Omega notation, Properties of Asymptotic functions, Monotonic functions, Floor and Ceil functions, Modular arithmetic, Casting out 9s, Polynomials & Exponentials, Arithmetic progression, Exponential Functions - e^x, Sum of squares - derivation, Choosing between exact and approximate problem solving, Methods of specifying algorithms, Units for measuring running times, Orders of growth, Program to calculate the running times, Sum of first odd/even numbers, Best case, Worst case and Average case efficiencies, Asymptotic notations and basic efficiency classes, O-notation, Gamma-notation, Theta-notation, Useful properties involving asymptotic notations, Using limits in orders of growth, Basic efficiency classes, Asymptotic behaviour of polynomials, Analysing complexity of naive matrix multiplication, Recurrence relations, Factorial, Tower of Hanoi.

Algorithm Analysis Book 2 (Pages 99)

Tower of Hanoi (continued from Book_1), Insertion Sort, Questions, Sieve of Eratosthenes, Radix Sort, Greedy & Brute Force, Bubble Sort, Cocktail Sort, Linear Search/Sequential Search, String matching - brute force, Closest pair problem - Greedy technique, Closest pair problem - Divide & Conquer technique, Brute Force Technique, Divide & Conquer Technique, Master's Theorem, GCD using Euclid's algorithm, Quicksort, Space & Time tradeoff in algorithms, String searching algorithms - comparisons, Rabin Karp String search algorithm, Dynamic Programming, Matrix Chain multiplication - using dynamic programming.

Algorithm Analysis Book 3 (Pages 80)

Qn: Find the least number of multiplications required for matrices with given orders, Constructing optimal BST, Problems: Off-topic: 'A students creativity' - A real life story, Decision problems, Robert Floyd, Heap Data Structure, Binary heap, insertion into heap, deletion of root, Some problems on heap, Max-heapify function, Build-max-heap function - Floyd's linear algorithm, Heap sort algorithm, heap-delete, heap-extract-max, max-heap-insert, Algorithm to find the leader in an array, Algorithm for median in a sorted array, Horner's rule for evaluation polynomials, Matrix multiplication, Strassen's algorithm for matrix multiplication: O(n^(log 7 to base 2)), Block matrix, Elementary graph algorithms, even bridges of Konigsberg, Variation of the puzzle, Breadth First Search (BFS), Depth Fist Search (DFS), Strongly Connected Components in a graph, Kosaraju's algorithm.

Algorithm Analysis Book 4 (Missing)

Selection Algorithm (Pages 63)

Overview, min, max, median, quickselect and quicksort, selection by sorting, unordered partial sorting, partial selection sort, partial-based selection, Quickselect algorithm, partition function, sample run of partition function, select algorithm, sample run of the select algorithm, time complexity of quickselect, median selection by pivot strategy, incremental sorting by selection, using data structures to select in sub-linear time, order static tree, hash-table based select strategy, language support, nth_select in C++, Median of medians algorithm, selecting the pivot element, when group size is 5, 30-70 split of elements, T(n) = T(n/5) + T(7n/10) + O(n) = O(n), computing the complexity, does group size of 3 work?, Group size of 7?.
  • The 1972 paper (by Blum, Floyd, Pratt, Rivest and Tarjan) on the PICK algorithm that uses median or medians technique to get a linear upper bound can be found here. It's interesting to note that all of the authors, except Pratt, have won the Turing award.

Bellman-Ford Algorithm (Pages 38)

Introduction, finding shortest path from a given source to all other vertices of the graph, negative weight cycle, complexity is (V.E), example where Dijkstra's algorithm fails, algorithm description, how does it work, example1, example2, used in RIP routing protocol, Yen's improvements for the algorithm.

Maximum Subarray Problem (Pages 19)

Finding the contiguous subarray within a one dimensional array of numbers which has the largest sum, Kadane's algorithm (1984), example.

Lowest Common Ancestor Problem (Pages 59)

Problem statement, trees with parent pointers -- solution based on hashing table, finding LCA for BST, recursive and non-recursive versions, trees with pointers -- solution based on finding the difference between the depths of nodes, LCA for generic binary trees, Method 1 -- O(n) complexity and three tree traversal, Method 2 -- O(n) with single tree traversal, Tarjan's offline LCA algorithm using disjoint set forest, makeset(), union() and find() operations, example, LCA using RMQ (Range Minimum Query), Euler tour on tree, first occurrence array, program, complexity.

Longest Increasing Subsequence (Pages 59)

Introduction, example, shortest path in DAGs, dynamic programming, LIC problem using longest path in DAGs, why not recursion?, LIC with complexity O(N log N), active lists, algorithm, example, complexity, variants of LIC problem, building bridges problem, maximum sum increasing subsequence problem, the longest chain problem, box stacking problem, Erdos-Szekeres theorem: 'any sequence of n^2+1 distinct integers has an increasing or decreasing subsequence of length n+1'. (CPP code can be found here).

Pancake Sorting Problem (Pages 31)

Problem statement, examples, 'the problem of determining the minimum number of moves for a given stack has been shown to be NP-hard', algorithm, mathematical paper written by Bill Gates and Papadimitriou, animation, examples, runtime.
  • C++ code can be found here.
  • The original 1978 paper on the topic by Bill Gates and Padimitriou can be found here.

Topological Sorting (Pages 56)

Overview, linear ordering of nodes, DAG, example, Kahn's algorithm, 'A DAG has at least one vertex with in-degree 0 and one vertex with out-degree 0', reverse graph, example1, example 2, example 3, computing the indegrees instead of reversing the graph, how to find the indrees of nodes - two techniques, topological sorting vs. DFS, hamiltonian paths and toplogical sorting -- how they are related, every DAG has either zero hamiltonian paths or one hamiltonian path, tsort linux command. C++ code can be found here.

Horner's Rule for Polynomial Evaluation (Pages 9)

Naive tehcnique for Polynomial evaluation with complexity O(n^2). The Horner's technique with complexity O(n).

Strongly Connected components and Kosaraju's Algorithm (Pages 31)

Introduction, strongly connected components, 'every directed graph is a dag of its strongly connected components', 'the node with the highest finish time belongs to the source SCC', DFS algorithm, discovery and finish times in DFS traversal, Kosaraju's algorithm for findindg SCC, transpose of graph G, algorithm, example, complexity: O(V+E). The C++ implementation can be found here.

Stable Marriage Problem (Pages 43)

Introduction, problem description, Nobel prize in Economics -2012 (theory of stable allocation and the practice of market design), applications, solution, Gale-Shapley algorithm, guarantees of the algorithm, optimality of the solution, stable marriage with indifference, similar problems, national resident matching program, matching algorithm.