NPTEL : NOC:Design and Analysis of Algorithms (Computer Science and Engineering)

Co-ordinators : Prof. Madhavan Mukund


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