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 |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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, 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 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|