DOC/LP/01/28.02.02

/ LESSON PLAN / LP- CS6402
LP Rev. No: 00
Date: 31/12/2014
Page 1 of 6
Sub Code : CS6402
Sub Name : DESIGN AND ANALYSIS OF ALGORITHMS
Unit: I Branch: IT&CS Semester: IV

Unit syllabus:

UNIT I INTRODUCTION

Notion of an Algorithm – Fundamentals of Algorithmic Problem Solving – Important Problem Types – Fundamentals of the Analysis of Algorithm Efficiency – Analysis Framework – Asymptotic Notations and its properties – Mathematical analysis for Recursive and Non-recursive algorithms.

Objective: To understand the basics about algorithms and learn how to analyze and design algorithms.

Session No / Topics to be covered / Time / Ref, Page No / Teaching Method
1 / Introduction, Algorithm, Notion of algorithm / 50m / 1 (1-7)
2(5-11) / LCD
2 / Fundamentals of Algorithmic Problem Solving-steps in designing and analyzing an algorithm / 50m / 1 (9-16)
2(30-39) / LCD
3 / Important Problem Types-Sorting.searching, string processing, graph, geometric, numeric and combinatorial problems / 50m / 1(18-23) / LCD
4 / Fundamentals of the Analysis of Algorithm Efficiency, Analysis Framework, measuring input size, units for measuring running time, / 50m / 1(41-45) / LCD
5 / Analysis Framework, Orders of growth, worst, best and average case analysis, recapitulation of Analysis Framework. / 50m / 1(45-50)
2(23-29) / LCD
6 / Asymptotic Notations and its properties- Informal, Big-oh, Big-omega, Big-theta notation / 50m / 1(52-58)
2(43-53)
4(31-57) / LCD
7 / Mathematical analysis for Non-recursive algorithms –General plan for analyzing time efficiency / 50m / 1(61-67) / LCD
8 / Mathematical analysis for Recursive algorithms –General plan for analyzing time efficiency / 50m / 1(70-76)
2(65-75) / LCD
9 / Sample problems / 50m / 1(8,16-18,) / LCD
/ LESSON PLAN / LP- CS6402
LP Rev. No: 00
Date: 31/12/2014
Page 2 of 6
Sub Code : CS6402
Sub Name : DESIGN AND ANALYSIS OF ALGORITHMS
Unit: I I Branch: IT&CS Semester: IV

Unit syllabus:

UNIT II BRUTE FORCE AND DIVIDE-AND-CONQUER 9

Brute Force - Closest-Pair and Convex-Hull Problems-Exhaustive Search - Traveling Salesman Problem - Knapsack Problem - Assignment problem. Divide and conquer methodology – Merge sort – Quick sort – Binary search – Multiplication of Large Integers – Strassen’s Matrix Multiplication-Closest-Pair and Convex-Hull Problems.

Objective: To make the students solve computing problems using brute force and divide and conquer methods.

Session
No / Topics to be covered / Time / Ref, Page No / Teaching Method
10 / Brute Force-selection.bubble sort, / 50m / 1(97-101) / LCD
11 / Brute Force -sequential search,brute force string manipulation / 50m / 1(104-106) / LCD
12 / Closest-Pair and Convex-Hull Problems / 50m / 1(108-113) / LCD
13 / Traveling Salesman Problem - Knapsack Problem / 50m / 1(115-119)
3(401-405) / LCD
14 / Assignment problem / 50m / 1(119-121)
4(498-501) / LCD
15 / Divide and conquer methodology master theorem / 50m / 1(169-172)
2(93-97),5 / LCD
16 / Merge sort,Quick sort / 50m / 1(172-181)
2(170-182)
4(120-129) / LCD
17 / Binary search-Binary tree traversal and properties. / 50m / 1(181-185)
4(132-139) / LCD
18 / Multiplication of Large Integers – Strassen’s Matrix Multiplication / 50m / 1(186-191),
2(75-82)
4(135-137) / LCD
19 / Closest-Pair and Convex-Hull Problems.
By divide and conquer rule / 50m / 1(192-197) / LCD
Continuous Assessment Test - I
/ LESSON PLAN / LP- CS6402
LP Rev. No: 00
Date: 31/12/2014
Page 3 of 6
Sub Code : CS6402
Sub Name : DESIGN AND ANALYSIS OF ALGORITHMS
Unit: III Branch: IT&CS Semester: IV

Unit syllabus:

UNIT III DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE 9

Computing a Binomial Coefficient – Warshall’s and Floyd’ algorithm – Optimal Binary Search Trees – Knapsack Problem and Memory functions. Greedy Technique– Prim’s algorithm- Kruskal's Algorithm- Dijkstra's Algorithm-Huffman Trees.

Objective: To given students the exposure about solving problems using dynamic programming and greedy techniques.

Session
No / Topics to be covered / Time / Ref,Page No / Teaching Method
20 / Dynamic programming-three basic examples –coin row problem / 50m / 1(283-287) / LCD
21 / Change-making problem, Coin-collecting problem / 1(287-290) / LCD
22 / Warshall’s algorithm / 50m / 1(217-225) / LCD
23 / Floyd’ algorithm / 50m / 1(226-237)
4(210-212) / LCD
24 / Optimal Binary Search Trees / 50m / 1(241-255)
2(397-403) / LCD
25 / Knapsack Problem and Memory functions. / 50m / 1(249-257)
2(425-427)
4(427-431) / LCD
26 / Greedy Technique– Prim’s algorithm / 50m / 1(315-322)
2(634-636) / LCD
27 / Kruskal's Algorithm / 50m / 1(325-331)
2(631-633) / LCD
28 / Dijkstra's Algorithm / 50m / 1(333-337)
2(658-662) / LCD
29 / Huffman Trees. / 50m / 1(338-343) / LCD
/ LESSON PLAN / LP- CS6402
LP Rev. No: 00
Date: 31/12/2014
Page 4 of 6
Sub Code : CS6402
Sub Name : DESIGN AND ANALYSIS OF ALGORITHMS
Unit: I V Branch: IT&CS Semester: IV

Unit syllabus:

UNIT IV ITERATIVE IMPROVEMENT 9

The Simplex Method-The Maximum-Flow Problem – Maximm Matching in Bipartite Graphs- The Stable marriage Problem.

Objective: To make the students understand solve problems using iterative method. Problems solved using iterative methods are discussed for better understanding.

Session
No / Topics to be covered / Time / Ref, Page No / Teaching Method
30 / The Simplex Method, geometric interpretation of
linear programming / 50m / 1(345-351)
2(846-850) / LCD
31 / Outline of simplex method / 50m / 1(351-359)
2(864-878) / LCD
32 / The Maximum-Flow Problem / 50m / 1(361-369)
2(708-714) / LCD
33 / Max flow-min cut Theorem / 50m / 1(369-371)
4(258-262) / LCD
34 / Maximum Matching in Bipartite Graphs / 50m / 1(372-375)
2(732-735) / LCD
35 / Maximum Matching in Bipartite Graphs- theorem and proof / 50m / 1(375-378)
2(732-735)
4(217-222) / LCD
36 / The Stable marriage Problem. / 50m / 1(380-381), / LCD
37 / Stable marriage algorithm- theorem and proof / 50m / 1(381-383) / LCD
Continuous Assessment Test - II
/ LESSON PLAN / LP- CS6402
LP Rev. No: 00
Date: 31/12/2014
Page 5 of 6
Sub Code : CS6402
Sub Name : DESIGN AND ANALYSIS OF ALGORITHMS
Unit: I Branch: IT&CS Semester: IV

Unit syllabus:

UNIT V COPING WITH THE LIMITATIONS OF ALGORITHM POWER 9

Limitations of Algorithm Power-Lower-Bound Arguments-Decision Trees-P, NP and NP-Complete Problems--Coping with the Limitations - Backtracking – n-Queens problem – Hamiltonian Circuit Problem – Subset Sum Problem-Branch and Bound – Assignment problem – Knapsack Problem – Traveling Salesman Problem- Approximation Algorithms for NP – Hard Problems – Traveling Salesman problem – Knapsack problem.

Objective: To make students understand and solve complex problems using backtracking .branch and bound techniques.

Session
No / Topics to be covered / Time / Ref, Page No / Teaching Method
38 / Limitations of Algorithm Power- Lower-Bound Arguments-Methods for establishing lower bounds / 50m / 1(387-392) / LCD
39 / Decision Trees- Decision Trees for sorting and
searching in sorted arrays. / 50m / 1(394-397) / LCD
40 / P, NP and NP-Complete Problems / 50m / 1(401-409) / LCD
41 / Coping with the Limitations of algorithm power-backtracking / 50m / 1(423-425)
4(231-238) / LCD
42 / n-Queens problem – Hamiltonian Circuit Problem-
Subset sum problem / 50m / 1(426-430) / LCD
43 / Branch and Bound – Assignment problem / 50m / 1(432-436) / LCD
44 / Knapsack Problem – Traveling Salesman Problem / 50m / 1(436-440)
4(427-430)
4(533-537) / LCD
45 / Approximation Algorithms for NP – Hard Problems – Traveling Salesman problem – Knapsack problem. / 50m / 1(778-788)
2(1048-1053) / LCD
Continuous Assessment Test - III
/ LESSON PLAN / LP- CS6402
LP Rev. No: 00
Date: 31/12/2014
Page 6 of 6
Sub Code : CS6402
Sub Name : DESIGN AND ANALYSIS OF ALGORITHMS
Unit: I Branch: IT&CS Semester: IV

Course Delivery Plan:

Week / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10 / 11 / 12 / 13 / 14 / 15
I II / I II / I II / I II / I II / I II / I II / I II / I II / I II / I II / I II / I II / I II / I II
Units / / 1 / / 2 / / / 3 / / 4 / / 5 /

CAT-I CAT-II CAT-III

TEXT BOOK:

1. Anany Levitin, “Introduction to the Design and Analysis of Algorithms”, Third Edition, Pearson Education, 2012.

REFERENCES:

2. Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest and Clifford Stein, “Introduction to

Algorithms”, Third Edition, PHI Learning Private Limited, 2012.

3. Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman, “Data Structures and Algorithms”, Pearson Education, Reprint 2006.

4. Donald E. Knuth, “The Art of Computer Programming”, Volumes 1& 3 Pearson Education, 2009. Steven S. Skiena, “The Algorithm Design Manual”, Second Edition, Springer, 2008.

5. http://nptel.ac.in/

Prepared by / Approved by
Signature
Name / Ms.B.T.Shobana
Ms.R. Saktheeswari / Dr. D. Balasubramanian
Designation / Assistant Professor / HOD/IT
Date / 31/12/2014 / 31/12/2014