NOC:Design and Analysis of Algorithms


Lecture 1 - Course Outline


Lecture 2 - Example: Air Travel


Lecture 3 - Example: Xerox shop


Lecture 4 - Example: Document similarity


Lecture 5 - Introduction and motivation


Lecture 6 - Input size, worst case, average case


Lecture 7 - Quantifying efficiency: O( ), Omega( ), Theta( )


Lecture 8 - Examples: Analysis of iterative and recursive algorithms


Lecture 9 - Arrays and lists


Lecture 10 - Searching in an array


Lecture 11 - Selection Sort


Lecture 12 - Insertion sort


Lecture 13 - Merge sort


Lecture 14 - Merge sort - analysis


Lecture 15 - Quicksort


Lecture 16 - Quicksort - analysis


Lecture 17 - Sorting - Concluding remarks


Lecture 18 - Introduction to graphs


Lecture 19 - Representing graphs


Lecture 20 - Breadth first search (BFS)


Lecture 21 - Depth first search (DFS)


Lecture 22 - Applications of BFS and DFS


Lecture 23 - Directed acylic graphs: topological sort


Lecture 24 - Directed acylic graphs: longest paths


Lecture 25 - Single source shortest paths: Dijkstras algorithm


Lecture 26 - Dijkstras algorithm: analysis


Lecture 27 - Negative edge weights: Bellman-Ford algorithm


Lecture 28 - All pairs shortest paths


Lecture 29 - Minimum Cost Spanning Trees


Lecture 30 - Prims Algorithm


Lecture 31 - Kruskals algorithm


Lecture 32 - Union-Find using arrays


Lecture 33 - Union-Find using pointers


Lecture 34 - Priority queues


Lecture 35 - Heaps


Lecture 36 - Heaps: Updating values, sorting


Lecture 37 - Counting inversions


Lecture 38 - Closest pair of points


Lecture 39 - Binary Search Trees


Lecture 40 - Balanced search trees


Lecture 41 - Interval scheduling


Lecture 42 - Scheduling with deadlines: minimizing lateness


Lecture 43 - Huffman codes


Lecture 44 - Introduction to dynamic programming


Lecture 45 - Memoization


Lecture 46 - Grid Paths


Lecture 47 - Common subwords and subsequences


Lecture 48 - Edit distance


Lecture 49 - Matrix multiplication


Lecture 50 - Linear Programming


Lecture 51 - LP modelling: Production Planning


Lecture 52 - LP modelling: Bandwidth allocation


Lecture 53 - Network Flows


Lecture 54 - Reductions


Lecture 55 - Checking Algorithms


Lecture 56 - P and NP