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

  1. Course Outline
  2. Example: Air Travel
  3. Example: Xerox shop
  4. Example: Document similarity
  5. Introduction and motivation
  6. Input size, worst case, average case
  7. Quantifying efficiency: O( ), Omega( ), Theta( )
  8. Examples: Analysis of iterative and recursive algorithms
  9. Arrays and lists
  10. Searching in an array
  11. Selection Sort
  12. Insertion sort
  13. Merge sort
  14. Merge sort - analysis
  15. Quicksort
  16. Quicksort - analysis
  17. Sorting - Concluding remarks
  18. Introduction to graphs
  19. Representing graphs
  20. Breadth first search (BFS)
  21. Depth first search (DFS)
  22. Applications of BFS and DFS
  23. Directed acylic graphs: topological sort
  24. Directed acylic graphs: longest paths
  25. Single source shortest paths: Dijkstra's algorithm
  26. Dijkstra's algorithm: analysis
  27. Negative edge weights: Bellman-Ford algorithm
  28. All pairs shortest paths
  29. Minimum Cost Spanning Trees
  30. Prim's Algorithm
  31. Kruskal's algorithm
  32. Union-Find using arrays
  33. Union-Find using pointers
  34. Priority queues
  35. Heaps
  36. Heaps: Updating values, sorting
  37. Counting inversions
  38. Closest pair of points
  39. Binary Search Trees
  40. Balanced search trees
  41. Interval scheduling
  42. Scheduling with deadlines: minimizing lateness
  43. Huffman codes
  44. Introduction to dynamic programming
  45. Memoization
  46. Grid Paths
  47. Common subwords and subsequences
  48. Edit distance
  49. Matrix multiplication
  50. Linear Programming
  51. LP modelling: Production Planning
  52. LP modelling: Bandwidth allocation
  53. Network Flows
  54. Reductions
  55. Checking Algorithms
  56. 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