|
PROGRAMME:COMPUTER SCIENCE AND ENGINEERING |
DEGREE: BTECH |
|
COURSE: DESIGN AND ANALYSIS OF ALGORITHMS |
SEMESTER: VI CREDITS: 4 |
|
COURSE CODE: CS302 REGULATION: 2016 |
COURSE TYPE: CORE |
|
COURSE AREA/DOMAIN: DESIGN AND ANALYSIS |
CONTACT HOURS: 4+1(Tutorial) hours/Week. |
|
CORRESPONDING LAB COURSE CODE (IF ANY): |
LAB COURSE NAME: |
SYLLABUS:
|
UNIT |
DETAILS |
HOURS |
|
I |
Introduction to Algorithm AnalysisTime and Space Complexity- Elementary operations and Computation of Time Complexity- Best, worst and Average Case Complexities- Complexity Calculation of simple algorithms Recurrence Equations:Solution of Recurrence Equations – Iteration Method and Recursion Tree Methods, |
8 |
|
II |
Master’s Theorem(Proof not required) – examples, Asymptotic Notations and their propertiesApplication of Asymptotic Notations in Algorithm Analysis- Common Complexity Functions AVL Trees – rotations, Red-Black Trees insertion and deletion (Techniques only; algorithms not expected). B-Trees – insertion and deletion operations. SetsUnion and find operations on disjoint sets. |
9 |
|
III |
Graphs – DFS and BFS traversals, complexity, Spanning trees – Minimum Cost Spanning Trees, single source shortest path algorithms, Topological sorting, strongly connected components. |
7 |
|
IV |
Divide and Conquer:The Control Abstraction, 2 way Merge sort, Strassen’s Matrix Multiplication, Analysis Dynamic Programming : The control Abstraction- The Optimality Principle- Optimal matrix multiplication, Bellman-Ford Algorithm
|
8 |
|
V |
Analysis, Comparison of Divide and Conquer and Dynamic Programming strategies Greedy Strategy: - The Control Abstraction- the Fractional Knapsack Problem, Minimal Cost Spanning Tree Computation- Prim’s Algorithm – Kruskal’s Algorithm |
9 |
|
VI |
Back Tracking: -The Control Abstraction – The N Queen’s Problem, 0/1 Knapsack Problem Branch and Bound:Travelling Salesman Problem. Introduction to Complexity Theory :-Tractable and Intractable Problems- The P and NP ClassesPolynomial Time Reductions - The NP- Hard and NPComplete Classes |
9 |
|
TOTAL HOURS |
50 |
|
TEXT/REFERENCE BOOKS:
1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, MIT Press [Modules 1,2,6]
2. Ellis Horowitz, SartajSahni, SanguthevarRajasekaran, Computer Algorithms, Universities Press, 2007 [Modules 3,4,5]
REFERENCES
1. AnanyLevitin, Introduction to the Design and Analysis of Algorithms, Pearson, 3rd Edition.
2. Richard E. Neapolitan,KumarssNaimipour, Foundations of Algorithms using C++ Psuedocode, Second Edition.
3. Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman, The Design and Analysis of Computer Algorithms, Pearson Education, 1999.
4. Gilles Brassard, Paul Bratley, Fundamentals of Algorithmics, Pearson Education.
COURSE PRE-REQUISITES:
|
C.CODE |
COURSE NAME |
DESCRIPTION |
SEM |
|
CS205 |
Data Structures and Algorithms |
Detailed study of different data structures and algorithms |
S3 |
COURSE OBJECTIVES:
|
1 |
To develop an understanding about basic algorithms and different problem solving strategies.
|
|
2 |
To improve creativeness and the confidence to solve non-conventional problems and expertise for analyzing existing solutions.
|
COURSE OUTCOMES:
|
CS302.1 |
Students will be able to Analyze a given algorithm and express its time and space complexities in asymptotic notations. (Level 1- Knowledge) |
|
CS302.2 |
Students will be able to Solve recurrence equations using Iteration Method, Recurrence Tree Method and Master’s Theorem (Level 3-4-5 –Apply-Analyze –Evaluate) |
|
CS302.3 |
Students will be able to design algorithms using Divide and Conquer Strategy. (Level 3-5- Apply- Evaluate) |
|
CS302.4 |
Students will be able to compare Dynamic Programming and Divide and Conquer Strategies.(Level 3- 4 – Apply-Analyze) |
|
CS302.5 |
Students will be able to solve Optimization problems using Greedy strategy. (Level 2 & 4 –Understand and Analyze) |
|
CS302.6 |
Students will be able to design efficient algorithms using Back Tracking and Branch Bound Techniques for solving problems. |
|
CS302.7 |
Students will be able to classify computational problems into P, NP, NP-Hard and NP-Complete.
|