Introduction of Algorithms and Analysis

Prof. Sourav Mukhopadhyay (IIT Kharagpur)

Lecture Note (full)

LECTURE	TOPIC	DESCRIPTION
1.	Insertion Sort	Problem of Sorting, Pseudo code, Insertion sort, Loop Invariant, time complexity, Runtime, parameterise the runtime by size of the input.
2.	Analysis of Insertion Sort	Types of Analysis: Worst case, Best case and Average case. Machine dependency, Asymptotic Notation, Big-Theta.
3.	Asymptotic Analysis	Asymptotic Notation, Big-Theta, Big-O, Big-omega, Time complexity of Insertion sort: Worst case, best case, average case. Merge Sort.
4.	Recurrence of Merge Sort	Merge sort, run time of merge sort, recurrence, Recursive tree.
5.	Substitution Method	Solving the recurrence: Substitution method, method of induction.
6.	The Master Method	Solving the recurrence of the form T(n) = aT(n/b) + f(n). Master method, Proof idea of mater method.
7.	Divide-and-Conquer	divide-and-conquer: design paradigm, binary search, powering a number.
8.	Divide-and-Conquer (Cont.....)	Fibonacci numbers, matrix multiplication Strassen's Algorithm.
9.	Straseen's Algorithms	Matrix multiplication using divide-and-conquer technique, Straseen's idea, VLSI layout, Embedding.
10.	Quick Sort	Quicksort as a divide-and-conquer technique, Liner time Partition subroutine, pivot element
11.	Analysis of Quicksort.	Pseudo code for Quicksort, worst case, best cast, almost best case, good pivot, bad pivot.
12.	Randomized Quicksort	More analysis on Quicksort, problem with fixing the position of the pivot element, choosing the pivot element randomly, Randomised Quicksort, Average case analysis, Expected runtime of Randomized Quicksort.
13.	Heap	Priority Queue, heap data structure, array, nearly complete binary tree Max-heap, heap operations, Max-Hepify.
14.	Heap Sort	Build-Max-Heap, worst case time complexity of Build-Max-Heap, Heap Sort
15.	Decision Tree	How fast we can sort? worst case runtime of Comparison based sorting algorithms, Decision Tree model.
16.	Linear time Sorting	No comparison between the elements, Counting Sort, Stable sorting, linear time complexity of counting sort.
17.	Radix Sort & Bucket Sort	Radix sort, digit-by-digit sort, Analysis of Radix Sort, bucket sort, analysis of bucket sort.
18.	Order Statistics	Finding the i-th smallest element from a given n numbers, minimum, maximum, median, Naive approach, partition, select algorithm, analysis of select algorithm, worst case runtime of select.
19.	Randomised Order Statistics	Randomized select algorithm, average case runtime is linear, worst case runtime is O(n^2).
20.	Worst case linear time order statistics	Good pivot, generate the good pivot recursively, SELECT algorithm, worst case runtime.
21.	Hash Function	Symbol table problem, Direct access table, Hash function, collision, resolving collision by chaining, analysis of chaining.
22.	Open Addressing	Good hash functions, choosing of hash function, division method, multiplication method, resolving collision by open addressing, example of open addressing, linear probing, double probing.
23.	Universal Hashing	Analysis of open addressing, fundamental weakness of hashing, Random choice of hash function, Universal hashing, Universality is good.
24.	Perfect Hashing	Construction a set of universal hash functions, perfect hashing, static hash table, Analysis of perfect hashing.
25.	Binary Search Tree (BST) Sort	Binary search tree (BST), build BST, inoder-tree-walk, BST sort, runtime of BST sort, relationship between BST sort and Quick Sort
26.	Randomly build BST	Randomised BST sort, randomly build BST, expected height of a randomly build BST
27.	Red Black Tree	Balanced binary search tree, Red Black Tree, Black height, red black tree is balanced.
28.	Red Black Tree (Cont...)	Modifying operation, re-coloring, rotations, red black tree insertion.
29.	Augmentation of data structure	Augmenting data structure, Dynamic Order Statistics, OS-Select
30.	Interval trees	Methodology of data structure augmentation, interval search, interval tree.
31.	Fixed universe successor	Dynamic set S of n elements, Fixed universe with size u, Insert, Delete, Successor, array, bit vector, O(log log u).
32.	Van Emde Boas data structure	Fixed-universe success problem, bit vector, one-dimensional array, two dimensional array, augmenting the data structure, non-empty bits, more augmentations, maximum bits and minimum bits.
33.	Amortized analysis	How large should a hash table be? Dynamic table, overflow, worst case analysis, tighter analysis, amortized analysis.
34.	Computational Geometry	Algorithm for geometric problems, basis geometric objects, basic structures, orthogonal range search, 1D range tree.
35.	Computational Geometry (cont....)	1D range query, split node, 2D range tree, 2D range query, line segment intersections, sweep lines.
36.	Dynamic Programming	Design technique, longest common subsequence, simplification, length of the longest common subsequence, hallmarks of dynamic programming, optimal substructure, overlapping sub problems.
37.	Longest common subsequence	Recursive algorithms for length of the longest common subsequence, memoization algorithm, dynamic programming algorithm.
38.	Graphs	Graphs, directed graphs, undirected graphs, adjacency matrix, adjacency list, minimum spanning tree, optimal substructure.
39.	Prim's Algorithms	Minimum spanning tree, Greedy algorithm, Prim's algorithms, example of prim's algorithms.
40.	Graph Search	Analysis of prim's algorithm, exploring a graph, application of graph search, rubix cube, god number, breath-first-search (BFS).
41.	BFS & DFS	breath-first-search (BFS), level by level search, BFS, O(V+E), shortest path, depth-first-search (DFS), exploring until stuck, back tracking, recursively explore, DFS, classification of edges: tree edge, forward edge, back edge and cross edge. Cycle detection.
42.	Shortest path problem	Path in a graph, shortest path, weight of shortest path, existence of shortest path, negative weight cycle, optimal substructure, triangular inequality.
43.	Dijktra's	Single source shortest path, Greedy algorithms, idea of Dijktra's, No negative cycle, pseudo code of Dijktra's, time complexity of Dijktra's.
44.	Example of Dijktra	Dijktra's algorithm, example Dijktra's algorithms, correctness of Dijktra's algorithm.
45.	Bellman Ford	Bellman-Ford, Greedy, general algorithm which can handle negative cycle, time complexity of Bellman-Ford, example of Bellman-Ford.
46.	Correctness of Bellman Ford	Correctness of Bellman Ford, If there are no negative weight cycle then Bellman Ford gives the shortest path weights.
47.	Application of Bellman Ford	Linear programming problems, difference constraints, constraints graph, unstatisfiable constraints, negative weight cycle, statisfiable constraints.
48.	All pairs shortest paths	All pairs shortest paths, adjacency matrix, Bellman Ford, O(n^4), dynamic programming.
49.	Floyd-Warshall	Dynamic programming, matrix multiplication, O(n^3 log n), Floyd Warshall, O(n^3).
50.	Johnson Algorithm	Floyd-Warshall, transitive closure, graph reweighting, dijktra's, johnson's Algorithm
51.	Disjoint set data structure	Dynamic collection of multiple sets, representative element, MAKE_SET, UNION, FIND_SET, Doubly linked list.
52.	Union-Find	Disjoint set data structure, linked-list solutions, balanced tree solution.
53.	Augmented disjoint set data structure	Augmentation of disjoint set data structures, Amortized Analysis.
54.	Network flow I	Flow Network, Capacity, Positive flow, maximum flow, flow cancellation.
55.	Network Flow II	Net flow, equivalence between net flow and positive flow, value of flow.
56.	Network Flow III	Cuts, flow across the cut, net flow and flow across the cut, capacity of a cut, residential capacity, residential network, augmenting path, max flow-min cut theorem.
57.	Dynamic Programming II	Memoization and subproblems, Exponential to Polynomial, Fibonacci numbers, Memoized DP Algorithm, Bottom-up DP Algorithm
58.	Dynamic Programming III	Shortest path problem, naive recursive algorithm, guessing, memoization, cycle, DAG, DAG view of any graph, 5 easy steps in DP
59.	Computational Complexity I	Complexity classes: P, EXP, R. Most problems are uncomputable, Tetris.
60.	Computational Complexity II	NP, nondeterministic algorithms, NP-hard, NP-complete, EXP-hard, EXP-complete, Reductions, NP-hardness, example of NP-complete problems.

Home