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, BigTheta.

3.

Asymptotic
Analysis

Asymptotic Notation, BigTheta, BigO, Bigomega,
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.

DivideandConquer

divideandconquer: design paradigm, binary
search, powering a number.

8.

DivideandConquer
(Cont.....)

Fibonacci numbers, matrix multiplication Strassen's Algorithm.

9.

Straseen's Algorithms

Matrix multiplication using divideandconquer
technique, Straseen's idea, VLSI layout, Embedding.

10.

Quick
Sort

Quicksort
as a divideandconquer 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 Maxheap, heap operations, MaxHepify.

14.

Heap
Sort

BuildMaxHeap, worst case time complexity of
BuildMaxHeap, 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, digitbydigit sort, Analysis of Radix
Sort, bucket sort, analysis of bucket sort.

18.

Order
Statistics

Finding the ith 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, inodertreewalk, 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, recoloring, rotations, red
black tree insertion.

29.

Augmentation
of data structure

Augmenting data structure, Dynamic Order
Statistics, OSSelect

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

Fixeduniverse success problem, bit vector,
onedimensional array, two dimensional array, augmenting the data structure,
nonempty 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, breathfirstsearch (BFS).

41.

BFS & DFS

breathfirstsearch (BFS), level by level search,
BFS, O(V+E), shortest path, depthfirstsearch (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

BellmanFord, Greedy, general algorithm which can
handle negative cycle, time complexity of BellmanFord, example of
BellmanFord.

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.

FloydWarshall

Dynamic programming, matrix multiplication, O(n^3
log n), Floyd Warshall, O(n^3).

50.

Johnson
Algorithm

FloydWarshall,
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.

UnionFind

Disjoint set data structure, linkedlist
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 flowmin cut theorem.

57.

Dynamic
Programming II

Memoization
and subproblems, Exponential to Polynomial,
Fibonacci numbers, Memoized DP Algorithm, Bottomup
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, NPhard, NPcomplete,
EXPhard, EXPcomplete, Reductions, NPhardness, example of NPcomplete
problems.
