Instructor: Partha Sarathi Mandal
Indian Institute of Technology Guwahati

 

Title

Design and Analysis of Algorithms [MA353] & Introduction to Algorithms [MA515] [3-0-0-6]

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 union-find problems.

Introduction to NP-completeness, geometric algorithms, approximation algorithms for some NP-complete problems.

Exams and Marking

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

Reference

  1. Cormen, Leiserson and Rivest, Introduction to Algorithms, Prentice Hall-India.
  2. A.V. Aho, J.E. Hopcroft, J.D. Ullman, Design and Analysis of Algorithms, Addition and Wesley.
  3. E. Horowitz and S. Sahni, Fundamentals of Computer Algorithms, Galgotia Publishers.
  4. K. Melhorn, Data Structures and Algorithms, Vol. 1 and 2, Springer Verlag.

Time Table for

MA 515 & MA 353

 

Class Room: 2101

Day

8 - 8:55

9 - 9:55

10 - 10:55

11 - 11:55

12 - 12:55

1 - 1:55

2 - 4:55

5 - 5:55

Monday

 

Class

 

 

 

 

 

Tuesday

 

 

Class

 

 

 

Wednesday

 

 

 

 

 

 

 

Thursday

Class

 

 

 

 

 

 

Friday

 

Class

 

 

 

 

 

 

Announcement

  1. Quiz I is on August 29, 2009(Saturday), from 9:00AM to 9:55AM.
  2. Midsem is on September 15, 2009(Tuesday) from 2:00PM to 4:00PM.
  3. Quiz II is on October 30, 2009(Friday), from 9:00AM to 9:55AM.
  4. Eedsem is on November 17, 2009(Tuesday) from 1:00PM to 4:00PM.

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, Bachmann-Landau notations, Comparison of Functions]

Aug 4

Lecture Notes 4 [The problem of sorting, Insertion sort, Analysis of insertion sorting, divide-and-conquer 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, Decision-tree 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, Max-heap & Min-heap 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, Breadth-First Search]

Aug 24

Lecture Notes 13 [BFS Tree, Depth-First 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

Quiz I

Aug 31

Lecture Notes 16 [Worst-case linear-time 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

Midsem

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: Bellman-Ford algorithm]

Oct 5

Lecture Notes 26 [Dynamic Programming (DP) Paradigm; DP Solution for Fibonacci Numbers, All-Pairs 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 [All-Pairs Shortest Paths Problem; based on matrix multiplication]

Oct 16

Lecture Notes 31 [Floyd-Warshall 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

Quiz II

Nov 3

Lecture Notes 37 [Decision Problems, Polynomial Reduction, NP-Completeness, 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

Endsem