Design and Analysis of Algorithms

Course Outline.
Example: Air Travel.
Example: Xerox shop.
Example: Document similarity.
Introduction and motivation.
Input size, worst case, average case.
Quantifying efficiency: O( ), Omega( ), Theta( ).
Examples: Analysis of iterative and recursive algorithms.
Arrays and lists.
Searching in an array.
Selection Sort.
Insertion sort.
Merge sort.
Merge sort - analysis.
Quicksort.
Quicksort - analysis.
Sorting - Concluding remarks.
Introduction to graphs.
Representing graphs.
Breadth first search (BFS).
Depth first search (DFS).
Applications of BFS and DFS.
Directed acylic graphs: topological sort.
Directed acylic graphs: longest paths.
Dijkstras algorithm: analysis.
Negative edge weights: Bellman-Ford algorithm.
All pairs shortest paths.
Minimum Cost Spanning Trees.
Prims Algorithm.
Kruskals algorithm.
Union-Find using arrays.
Union-Find using pointers.
Priority queues.
Heaps.
Heaps: Updating values, sorting.
Counting inversions.
Closest pair of points.
Binary Search Trees.
Balanced search trees.
Interval scheduling.
Scheduling with deadlines: minimizing lateness.
Huffman codes.
Introduction to dynamic programming.
Memoization.
Grid paths.
Common subwords and subsequences.
Edit distance.
Matrix multiplication.
Linear Programming.
LP modelling: Production Planning.
LP modelling: Bandwidth allocation.
Network Flows.
Reductions.
Checking Algorithms.
P and NP.
Single source shortest paths: Dijkstras algorithm.