Ktunotes.in-CS302 Design and analysis and algorithms.pdf

Page 1 of 3

Course

code Course Name L-T-P -

Credits

Year of

Introduction

CS302 Design and Analysis of Algorithms 3-1-0-4 2016

Prerequisite: Nil

Course Objectives

 To introduce the concepts of Algorithm Analysis, Time Complexity, Space Complexity.

 To discuss various Algorithm Design Strategies with proper illustrative examples.

 To introduce Complexity Theory.

Syllabus

Introduction to Algorithm Analysis, Notions of Time and Space Complexity, Asymptotic

Notations, Recurrence Equations and their solutions, Master’s Theorem, Divide and Conquer and

illustrative examples, AVL trees, Red-Black Trees, Union-find algorithms, Graph algorithms,

Divide and Conquer, Dynamic Programming, Greedy Strategy, Back Tracking and Branch and

Bound, Complexity classes

Expected outcome

The students will be able to

i. Analyze a given algorithm and express its time and space complexities in asymptotic

notations.

ii. Solve recurrence equations using Iteration Method, Recurrence Tree Method and

Master’s Theorem.

iii. Design algorithms using Divide and Conquer Strategy.

iv. Compare Dynamic Programming and Divide and Conquer Strategies.

v. Solve Optimization problems using Greedy strategy.

vi. Design efficient algorithms using Back Tracking and Branch Bound Techniques for

solving problems.

vii. Classify computational problems into P, NP, NP-Hard and NP-Complete.

Text Books

1. Ellis Horowitz, SartajSahni, SanguthevarRajasekaran, Computer Algorithms, Universities

Press, 2007 [Modules 3,4,5]

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

Algorithms, MIT Press, 2009 [Modules 1,2,6]

References

1. Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman, The Design and Analysis of

Computer Algorithms, Pearson Education, 1999.

2. Anany Levitin, Introduction to the Design and Analysis of Algorithms, Pearson, 3rd

Edition, 2011.

3. Gilles Brassard, Paul Bratley, Fundamentals of Algorithmics, Pearson Education, 1995.

4. Richard E. Neapolitan, Kumarss Naimipour, Foundations of Algorithms using C++

Psuedocode, Second Edition, 1997.

Course Plan

Module Contents Hours

End

Sem.

Exam

Marks

KTUNOTES.IN

To get more study materails visit www.ktunotes.in

Page 2 of 3

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

15 %

Master’s Theorem(Proof not required) – examples, Asymptotic

Notations and their properties- Application 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. Sets- Union and find operations on

disjoint sets.

15%

FIRST INTERNAL EXAM

III

Graphs – DFS and BFS traversals, complexity, Spanning trees –

Minimum Cost Spanning Trees, single source shortest path

algorithms, Topological sorting, strongly connected components. 07 15%

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

05 15%

SECOND INTERNAL EXAM

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.

20%

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 Classes- Polynomial Time Reductions -

The NP- Hard and NP-Complete Classes

20%

END SEMESTER EXAM

Question Paper Pattern

1. There will be five parts in the question paper – A, B, C, D, E

2. Part A

a. Total marks : 12

b. Four questions each having 3 marks, uniformly covering modules I and II;

Allfour questions have to be answered.

3. Part B

a. Total marks : 18

b. Three questions each having 9 marks, uniformly covering modules I and

II; Two questions have to be answered. Each question can have a

maximum of three subparts.

4. Part C

KTUNOTES.IN

To get more study materails visit www.ktunotes.in