Madhavan Mukund

NPTEL Design and Analysis of Algorithms

Lecture Slides

• Week 1: Introduction

  • Course Outline
  • Example: Air Travel
  • Example: Xerox Shop
  • Example: Document Similarity

• Week 1: Analysis of Algorithms

  • Analysis of Algorithms: Introduction
  • Asymptotic Complexity: Input Size, Worst Case, Average Case
  • Comparing Efficiency: O(), Ω(), Θ()
  • Examples: Analysis of Iterative and Recursive Algorithms

• Week 2: Searching and Sorting

  • Arrays and Lists
  • Searching in an array
  • Selection Sort
  • Insertion Sort
  • Merge Sort
  • Merge Sort – Analysis
  • Quicksort
  • Quicksort – Anaysis
  • Concluding Remarks: Stable Sorting etc

• Week 3: Graphs

  • Introduction to graphs
  • Graph representation
  • Breadth first search (BFS)
  • Depth first search (DFS)
  • Applications of BFS and DFS
  • Directed acyclic graphs: topological sort
  • Directed acyclic graphs: longest path

• Week 4: Weighted Graphs

  • 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

• Week 5: Data Structures – Union-Find and Heaps

  • Union-Find using arrays
  • Union-Find using pointers
  • Priority queues
  • Heaps
  • Heaps: Updating values, sorting

• Week 5: Divide and conquer

  • Counting inversions
  • Closest pair of points

• Week 6: Data Structures: Search trees

  • Binary search trees
  • Balanced search trees

• Week 6: Data Structures: Greedy algorihms

  • Interval Scheduling
  • Scheduling with deadlines: Minimizing lateness
  • Huffman codes

• Week 7: Dynamic Programming

  • Introduction to dynamic programming
  • Memoization
  • Grid paths
  • Longest common subsequence
  • Edit distance
  • Matrix multiplication

• Week 8: Linear programming and network flows

  • Linear programming
  • LP modelling: Production planning
  • LP modelling: Bandwidth allocation
  • Network flows
  • Reductions

• Week 8: Intractability

  • Checking algorithms
  • P and NP