Lessons

1. Module 01 : Introduction, Analysis of Algorithms
   1. What is the course all about?

      9 mins
2. Module 02 : Example: Air Travel
   1. What is Air travel problem?

      10 mins
3. Module 03 : Example: Xerox shop
   1. What is the Xerox shop problem?

      6 mins
4. Module 04 : Example: Document similarity
   1. What is the document similarity problem?

      9 mins
5. Module 05 : Introduction and motivation
   1. How analysis of algorithm is done and what is efficiency and time measurement?

      5 mins
   2. What is a sorting and video game example?

      8 mins
   3. What is the order of Magnitude and typical functions?

      6 mins
6. Module 06 : Input size, worst case, average case
   1. What is the input size and orders of magnitude?

      4 mins
   2. How basic operations are chosen and what is worst case and average case complexity?

      6 mins
7. Module 07 : Quantifying efficiency: O( ), Omega( ), Theta( )
   1. What are Upper bounds and Big O?

      11 mins
   2. What are Lower bounds, omega, tight bound and theta?

      7 mins
8. Module 08 : Examples: Analysis of iterative and recursive algorithms
   1. What are the different examples of iterative algorithms?

      9 mins
   2. What are the different examples of recursive algorithms?

      8 mins
9. Module 09 : Arrays and lists
   1. How values are stored and Arrays and Lists?

      6 mins
10. Module 10 : Searching in an array
    1. How a value is searched in an array and what is Binary Search?

       9 mins
11. Module 11 : Selection Sort
    1. What is Selection Sort algorithm and how it works?

       7 mins
    2. How is Selection Sort algorithm analyzed?

       5 mins
12. Module 12 : Insertion sort
    1. What is Insertion Sort algorithm and how it works?

       7 mins
    2. How is Insertion Sort algorithm analyzed?

       7 mins
13. Module 13 : Merge sort
    1. What is Merge Sort Algorithm and How it works?

       8 mins
    2. How Merge Sort Algorithm is implemented in a program?

       6 mins
14. Module 14 : Merge sort - analysis
    1. How Merge Sort Algorithm is analyzed?

       9 mins
    2. What are the variations on Merge and shortcomings of Merge Sort?

       6 mins
15. Module 15 : Quicksort
    1. What is Quick Sort Argorithm and how it works?

       10 mins
    2. How Quick Sort Algorithm is implemented in program?

       8 mins
16. Module 16 : Quicksort - analysis
    1. How Quick Sort Algorithm is analyzed?

       9 mins
    2. What is Iterative QuickSort?

       3 mins
17. Module 17 : Sorting - Concluding remarks
    1. Which sorting algorithm is the best?

       8 mins
18. Module 18 : Introduction to graphs
    1. How Map and Graph coloring is done?

       8 mins
    2. How airline routing is represented using Graph?

       4 mins
19. Module 19 : Representing graphs
    1. What is a Graph and what is a adjacency matrix?

       5 mins
    2. How to find the path in adjacency matrix?

       5 mins
    3. What is Adjacency list?

       4 mins
20. Module 20 : Breadth first search (BFS)
    1. What is Breadth First Search (BFS) algorithm and how it works?

       10 mins
    2. How to analyze the complexity of BFS and what more can be done in BFS?

       11 mins
21. Module 21 : Depth first search (DFS)
    1. What is Depth First Search (DFS) algorithm and how it works?

       7 mins
    2. What is the complexity of DFS and what is DFS numbering?

       6 mins
22. Module 22 : Applications of BFS and DFS
    1. What are BFS and DFS trees?

       10 mins
    2. What are directed cycles?

       8 mins
    3. What are directed Acyclic Graphs and how directed graphs are connected?

       4 mins
23. Module 23 : Directed acyclic graphs: topological sort
    1. How a problem is modeled using graphs and what is Directed Acyclic Graph (DAG)?

       5 mins
    2. How Topological sorting algorithm works?

       9 mins
    3. What is the pseudo code for topological sorting algorithm?

       7 mins
24. Module 24 : Directed acyclic graphs: longest paths
    1. What is the longest path in DAG?

       9 mins
    2. What is the psuedo code for Longest Path?

       5 mins
25. Module 25 : Single source shortest paths: Dijkstras algorithm
    1. How to find the shortest path?

       4 mins
    2. What is the single source shortest path problem?

       9 mins
    3. How this problem is represented algorithmically and what is Dijkstra's algorithm?

       3 mins
26. Module 26 : Dijkstras algorithm: analysis
    1. Why Dijkstra's algorithm is a greedy algorithm and how much correctness is there in this algorithm?

       5 mins
    2. What is the complexity of Dijkstra's algorithm?

       5 mins
    3. What are the limitations of Dijkstra's algorithm?

       4 mins
27. Module 27 : Negative edge weights: Bellman-Ford algorithm
    1. What are the shortest paths in graphs where negative weights are allowed?

       9 mins
    2. What is Bellman-Ford algorithm, its examples and complexity?

       8 mins
28. Module 28 : All pairs shortest paths
    1. How shortest paths are explored inductively?

       6 mins
    2. What is Floyd-Warshall algorithm, its examples and complexity?

       8 mins
    3. What are the historical perspectives of Floyd-Warshall algorithm and how paths are computed?

       5 mins
29. Module 29 : Minimum Cost Spanning Trees
    1. What is a Spanning tree and what are the various facts about trees?

       8 mins
    2. How to build a minimum cost spanning tree?

       4 mins
30. Module 30 : Prims Algorithm
    1. What is a Prim's algorithm and its correctness?

       11 mins
    2. What is the Prim's algorithm for minimum cost spanning tree and its complexity?

       11 mins
31. Module 31 : Kruskals algorithm
    1. What is Kruskal's algorithm and its correctness?

       9 mins
    2. What is the Kruskal's algorithm for minimum cost spanning tree and its complexity?

       6 mins
32. Module 32 : Union-Find using arrays
    1. What is Union-find data structure, its naive implementation and complexity?

       8 mins
    2. What is the improved implementation of Union-find data structure and why does this help?

       11 mins
    3. How to use Union-find data structure in Kruskal's algorithm?

       3 mins
33. Module 33 : Union-Find using pointers
    1. How Union-find data structure is implemented using pointers?

       11 mins
    2. How path compression can be done?

       5 mins
34. Module 34 : Priority queues
    1. What is a Priority Queue and what are its various operations?

       10 mins
35. Module 35 : Heaps
    1. What is a heap and its examples?

       6 mins
    2. What is insert() operation in heap and its complexity?

       6 mins
    3. What is delete_max() operation in heap?

       4 mins
    4. How heap is implemented using arrays and what is heapify()?

       7 mins
36. Module 36 : Heaps: Updating values, sorting
    1. How to update values in Heap?

       8 mins
    2. What is the complexity of Dijkstra's algorithm?

       4 mins
37. Module 37 : Counting inversions
    1. What is divide and conquer principle, what are recommendation systems and how rankings are compared?

       4 mins
    2. How inversions are counted?

       5 mins
    3. How to implement inversions using divide and conquer principle?

       9 mins
38. Module 38 : Closest pair of points
    1. How to find the closest pair of points in a video game example?

       17 mins
39. Module 39 : Binary Search Trees
    1. How heaps are implemented in air traffic control problem?

       7 mins
    2. What is a Binary Search Tree (BST) and its operations?

       9 mins
    3. How a successor and a predecessor work?

       5 mins
    4. How to insert and delete a value in BST?

       11 mins
40. Module 40 : Balanced search trees
    1. What are the different notions and situations of balance?

       16 mins
    2. What are the various functions in balancing a tree and how slope is computed?

       6 mins
41. Module 41 : Interval scheduling
    1. What are Greedy Algorithms and what is the problem of interval scheduling and what are the different greedy strategies?

       8 mins
    2. How the algorithm is implemented for Greedy strategies?

       10 mins
42. Module 42 : Scheduling with deadlines: minimizing lateness
    1. what are the greedy strategies for minimizing maximum lateness?

       7 mins
    2. What are the different aspects of optimal scheduling?

       10 mins
43. Module 43 : Huffman codes
    1. What is the concept of variable length coding and what are optimal prefix codes?

       11 mins
    2. How to view the codes as Binary tree?

       5 mins
    3. What is Huffman's Algorithm and its optimality?

       9 mins
    4. What is the implementation, complexity and historical perpective of Huffman's algorithm?

       4 mins
44. Module 44 : Introduction to dynamic programming
    1. What is inductive definition, optimal substructure property?

       9 mins
    2. What is the problem weighted interval scheduling and computational challenge?

       11 mins
45. Module 45 : Memoization
    1. What is a subproblem and how to evaluate it?

       6 mins
    2. What is memoization and how memoized fibonacci is implemented?

       7 mins
    3. What is dynamic programming?

       7 mins
46. Module 46 : Grid Paths
    1. What is the problem of computing grid paths and its combinational solution?

       9 mins
    2. What is the inductive formulation of a grid problem?

       5 mins
    3. How to use dynamic programming on Grid and how is memoization different from dynamic programming?

       8 mins
47. Module 47 : Common subwords and subsequences
    1. What is the Longest Common Subword (LCW) problem and how it is addressed?

       13 mins
    2. What is the Longest Common Subsequence (LCS) problem and how it is addressed?

       14 mins
48. Module 48 : Edit distance
    1. What is the problem of edit diatance and how it is related to LCS?

       6 mins
    2. How the problem of edit distance is addressed?

       9 mins
49. Module 49 : Matrix multiplication
    1. What is the problem of matrix multiplication?

       6 mins
    2. How the problem of martix multiplication is addressed?

       10 mins
50. Module 50 : Linear Programming
    1. What is Linear Programming and its example?

       8 mins
    2. What is Simplex algorithm and what it does?

       3 mins
    3. How to solve a problem using Simplex algorithm?

       7 mins
51. Module 51 : LP modelling: Production Planning
    1. What is the problem of production planning?

       5 mins
    2. How the problem is modelled using linear programming?

       8 mins
52. Module 52 : LP modelling: Bandwidth allocation
    1. What is the problem of Network Bandwidth and how it is modelled using linear programming?

       10 mins
53. Module 53 : Network Flows
    1. What is the oil network problem and how oil flow is formulated using Linear programming?

       5 mins
    2. What is Ford-Fulkerson Algorithm and how it is implemented?

       13 mins
54. Module 54 : Reductions
    1. What is the problem of course allocation in a school?

       11 mins
55. Module 55 : Checking Algorithms
    1. What are efficient algorithms and checking algorithm?

       4 mins
    2. What is Boolean Satisfiability problem?

       7 mins
    3. What is Travelling Salesman problem?

       5 mins
    4. What is the Independent Set problem?

       8 mins
56. Module 56 : P and NP
    1. What is P and NP?

       7 mins
    2. How SAT and 3-SAT are reduced within NP?

       8 mins
    3. What is Cook-Levin Theorem and how completeness of NP is achieved?

       5 mins