Chennai Mathematical Institute · Computer Science
Design and Analysis of Algorithms
Prof. Madhavan Mukund · 2023 · 56 free video lectures
This course will cover basic concepts in the design and analysis of algorithms. Asymptotic complexity, O() notation Sorting and search Algorithms on graphs: exploration, connectivity, shortest paths, directed acyclic graphs, spanning trees Design techniques: divide and conquer, greedy, dynamic…
▶ Play on Open Lecture HallCourse page ↗
Lectures
- 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
- Single source shortest paths: Dijkstra's algorithm
- Dijkstra's algorithm: analysis
- Negative edge weights: Bellman-Ford algorithm
- All pairs shortest paths
- Minimum Cost Spanning Trees
- Prim's Algorithm
- Kruskal's 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
From NPTEL (IITs and IISc) · CC BY-NC-SA. More from Chennai Mathematical Institute.
Open Lecture Hall is free, with no ads and no sign-up. It is not run by or connected to any university; the lectures are the universities' own free recordings, played from where they host them. About & rights