Syllabus  |   Lectures  |   Downloads  |   FAQ  |   Ask a question  |  
Course Co-ordinated by IIT Madras
Coordinators
 
Prof. Madhavan Mukund
Chennai Mathematical Institute

 

Download Syllabus in PDF format



Untitled Document
 

This course covers topics on motivation,Asymptotic complexity,binary search,Sorting,Graphs,Dijkstra algorithm,Priority queues, heaps,Search Trees,Dynamic Programming & Intractability.

 

Week. No

Topics

1.

  • Module 1 Introduction
  • Module 2 Examples and motivation
  • Module 3 Examples and motivation
  • Module 4 Asymptotic complexity: informal concepts
  • Module 5 Asymptotic complexity: formal notation
  • Module 6 Asymptotic complexity: examples

2.

  • Module 1 Searching in list: binary search
  • Module 2 Sorting: insertion sort
  • Module 3 Sorting: selection sort
  • Module 4 Sorting: merge sort
  • Module 5 Sorting: quicksort
  • Module 6 Sorting: stability and other issues

3.

  • Module 1 Graphs: Motivation
  • Module 2 Graph exploration: BFS
  • Module 3 Graph exploration: DFS
  • Module 4 DFS numbering and applications
  • Module 5 Directed acyclic graphs
  • Module 6 Directed acyclic graphs

4.

  • Module 1 Shortest paths: unweighted and weighted
  • Module 2 Single source shortest paths: Dijkstra
  • Module 3 Single source shortest paths: Dijkstra
  • Module 4 Minimum cost spanning trees: Prim's algorithm
  • Module 5 Minimum cost spanning trees: Kruskal's Algorithm
  • Module 6 Union-Find data structure

5.

  • Module 1 Divide and conquer: counting inversions
  • Module 2 Divide and conquer: nearest pair of points
  • Module 3 Priority queues, heaps
  • Module 4 Priority queues, heaps
  • Module 5 Dijstra/Prims revisited using heaps
  • Module 6 Search Trees: Introduction

6.

  • Module 1 Search Trees: Traversals, insertions, deletions
  • Module 2 Search Trees: Balancing
  • Module 3 Greedy : Interval scheduling
  • Module 4 Greedy : Proof strategies
  • Module 5 Greedy : Hu man coding
  • Module 6 Dynamic Programming: weighted interval scheduling

7.

  • Module 1 Dynamic Programming: memoization
  • Module 2 Dynamic Programming: edit distance
  • Module 3 Dynamic Programming: longest ascending subsequence
  • Module 4 Dynamic Programming: matrix multiplication
  • Module 5 Dynamic Programming: shortest paths: Bellman Ford
  • Module 6 Dynamic Programming: shortest paths: Floyd Warshall

8.

  • Module 1 Intractability: NP completeness
  • Module 2 Intractability: reductions
  • Module 3 Intractability: examples
  • Module 4 Intractability: more examples
  • Module 5 Misc topics
  • Module 6 Misc topics

Exposure to introductory courses on programming and data structures



Important: Please enable javascript in your browser and download Adobe Flash player to view this site
Site Maintained by Web Studio, IIT Madras. Contact Webmaster: nptel@iitm.ac.in