Title 
Design
and Analysis of Algorithms [MA353] &
Introduction to Algorithms [MA515] [3006] 

Level 
B. Tech. (M&C)
and M.Sc.(M&C) (core) 

Prerequisites 
CS
203/MA501 Discrete Mathematics, MA513 Data Structures 

Semester 
July  Nov
2009. 

Contents 
Models
of computation. Algorithm analysis, order arithmetic, time and space
complexities, average and wrost case analysis,
lower bounds. Algorithm
design techniques: devide and conquer, search and
traversals, dynamic programming, backtracking, branch and bound. Sorting and
searching algorithms (insertion sort, quicksort, heapsort, mergsort). Graph
Algorithms: Connectivity, shorter path, spanning trees, topological sorting. Algorithms
for set unionfind problems. Introduction
to NPcompleteness, geometric algorithms, approximation algorithms for some
NPcomplete problems. 

Exams and Marking 
10 (Quiz 1) + 30 (Midsem) + 10 (Quiz
2) + 50 (Endsem). 

Reference 


Time Table for MA 515 & MA 353 Class Room: 2101 


Announcement



Lecture Notes

________________________________________________________________________________


July 31 
Lecture Notes 1 [Introduction, Time Table, Tests and Marks distribution, Warning, Reference Books, Outline of the course]  
Aug 1 
Lecture Notes 2 [Experimental Studies and Limitations, Theoretical Analysis, Pseudocode, RAM Model, Primitive Operations, Estimating Running Time, Growth Rate] 

Aug 3 
Lecture Notes 3 [Asymptotic Algorithm Analysis, Computing Prefix Averages, Exercise, Asymptotic Notations, BachmannLandau notations, Comparison of Functions] 

Aug 4 
Lecture Notes 4 [The problem of sorting, Insertion sort, Analysis of insertion sorting, divideandconquer paradigm, Merge sort, Analyzing merge sort, Recurrence equation] 

Aug 7 
Lecture Notes 5 [Solving recurrence equation, Recursion tree, The master method, Exercises] 

Aug 8 
Lecture Notes 6 [Binary search, Powering a number, Fibonacci numbers, Golden Ratio, Computing Fibonacci numbers, Matrix multiplication, Strassen's algorithm, Reference: fastest known algorithm for matrix multiplication] 

Aug 10 
Lecture Notes 7 [Quicksort, Complexity analysis of the quicksort] 

Aug 11 
Lecture Notes 8 [Randomized quicksort, Complexity analysis of the Randomized quicksort, Decisiontree model, Lower bound for comparison sorting] 

Aug 14 
Lecture Notes 9 [Sorting in linear time, Counting sort, Running time, Stable sorting, Radix sort, Correctness of radix sort, Analysis of radix sort] 

Aug 17 
Lecture Notes 10 [Binary Heap, Maxheap & Minheap property, Heap Sort] 

Aug 18 
Lecture Notes 11 [Complexity analysis of the Heap Sort, Priority Queues] 

Aug 21 
Lecture Notes 12 [Graph Algorithms: Graph Representation, Graph Search Methods, BreadthFirst Search] 

Aug 24 
Lecture Notes 13 [BFS Tree, DepthFirst Search, DFS Properties, Linear Ordering, Topological Sort] 

Aug 25 
Lecture Notes 14 [Strongly Connected Components, Kosaraju's Algorithm, Biconnected Components] 

Aug 28 
Lecture Notes 15 [Order Statistics, Randomized selection algorithm, Analysis of expected time] 

Aug 29 

Aug 31 
Lecture Notes 16 [Worstcase lineartime order statistics] 

Sep 1 
Lecture Notes 17 [Disjoint Sets, Linked List Representation] 

Sep 11 
Lecture Notes 18 [Disjoint Sets, Tree Representation] 

Sep 11 
Lecture Notes 19 [Minimum Spanning Tree(MST), Kruskal's Algorithm] 

Sep 15 

Sep 22&23 
Lecture Notes 20 & 21 [Complexity analysis of the Kruskal Algorithm, Prim's Algorithm: Correctness proof and Complexity analysis] 

Sep 25 
Lecture Notes 24 [Single Source Shortest Path Algorithms: Dijkstra's algorithm; Correctness proof and Complexity analysis] 

Sep 29 
Lecture Notes 25 [Single Source Shortest Path Algorithms: BellmanFord algorithm] 

Oct 5 
Lecture Notes 26 [Dynamic Programming (DP) Paradigm; DP Solution for Fibonacci Numbers, AllPairs Shortest Paths Problem] 

Oct 6 
Lecture Notes 27 [DP Solution for Longest common subsequence (LCS) problem] 

Oct 9 
Lecture Notes 28 [The 0/1 Knapsack Problem] 

Oct 12 
Lecture Notes 29 [Matrix Chain Order Problem] 

Oct 13 
Lecture Notes 30 [AllPairs Shortest Paths Problem; based on matrix multiplication] 

Oct 16 
Lecture Notes 31 [FloydWarshall Algorithm, Transitive closure of a directed graph] 

Oct 19 
Lecture Notes 32 [Greedy Strategy: Fractional Knapsack Problem, MST: Kruskal & Prim's Algorithms] 

Oct 20 
Lecture Notes 33 [Interval scheduling Problem; A greedy approach] 

Oct 23 
Lecture Notes 34 [Scheduling all intervals, Huffman Codes] 

Oct 26 
Lecture Notes 35 [Huffman Codes: Finding Optimal Code] 

Oct 27 
Lecture Notes 36 [N & NP Problems] 

Oct 30 

Nov 3 
Lecture Notes 37 [Decision Problems, Polynomial Reduction, NPCompleteness, TSP reduction from HC] 

Nov 10 
Lecture Notes 38 [Vertex Cover (VC) of a Graph, VC reduction from 3SAT] 

Nov 13 
Lecture Notes 39 [Approximation Algorithms] 

Nov 17 


