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 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 programming
Data structures: heaps, union of disjoint sets, search trees
Intractability

Week

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 : Huffman 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.


nil


nil


nil



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