II Year – II Semester L T P C
Design and Analysis of Algorithms
Course Code: 1005222203 3 0 0 3
COURSE OBJECTIVES:
This course introduces different techniques to design algorithms using Divide and Conquer,
Greedy Approach, Dynamic Programming, Randomized techniques, Multi-Threading,
Backtracking and Branch and Bound. It also focuses on how to measure the time and space
complexities of algorithms.
COURSE OUTCOMES:
CO’
At the end of the course, the student will have the ability to:
s
CO1 Analyze the asymptotic performance of algorithms.
CO2 Apply the divide-and-conquer and dynamic programming paradigms
CO3 Compare the shared memory allocations between serial and parallel algorithms
Extend the backtracking and branch-and-bound techniques for state space tree
CO4
algorithms
UNIT- I
Foundations of Algorithm: Algorithm, Algorithm Specification, Recursive Algorithm,
Analysis: Space Complexity and Time Complexity, Asymptotic Notations, Amortized Analysis,
Sorting in linear time: Counting sort. [8
Hours]
UNIT-II
Divide and Conquer: General method, Masters Theorem with proof, Applications: Binary
search, Defective Chessboard, Finding the Maximum and Minimum, Quick sort, Merge sort,
Matrix multiplication: Block and Strassen’s matrix multiplication, Randomized Quicksort.
[10 Hours]
UNIT-III
Greedy method: General method, Applications: Job sequencing with deadlines, knapsack
problem, Single source shortest path problem, Optimal Merge Patterns.
Multithreaded Algorithms: Basics of dynamic multithreading, multithreaded matrix
multiplication, multithreaded merge sort.
[8 Hours]
UNIT-IV
Dynamic Programming: General method, Applications: Matrix chain multiplication, 0/1
knapsack problem, All pairs shortest path problem, Travelling salesperson problem, String
Editing, Reliability design.
[12 Hours]
UNIT-V
Backtracking: General method, Applications: n-queen problem, sum of subsets problem.
Branch and Bound: Control Abstraction for LC-Search, FIFO & LIFO Branch-and-Bound
techniques, 15-Puzzle Problem.
Introduction to NP-Hard and NP- Completeness. [10 Hours]
Text Books:
1. Fundamentals of Computer Algorithms, Ellis Horowitz, SatrajSahni and
Rajasekharam, Universities Press.
2. Introduction to Algorithms, second edition, [Link], [Link], [Link] and
[Link], PHI Pvt. Ltd.
3. The Algorithm Design Manual, 2nd edition, Steven S. Skiena, Springer.
4. Design and Analysis of Algorithms, S. Sridhar, OXFORD UNIVERSITY PRESS.
5. Introduction to the Design and Analysis of Algorithms, Anany Levi, PEA
Reference Books:
1. Design and Analysis of Computer Algorithms, First Edition, V. AHO, Pearson
2. Design and Analysis of Algorithms, ParagHimanshu Dave, HimansuBalachandra Dave,
Pearson Education.
3. Introduction to Design and Analysis of Algorithms A strategic approach, R.C.T. Lee,
[Link], [Link] and [Link], McGrawHill.
4. Design and Analysis of algorithms, Aho, Ullman and Hopcroft, Pearson education.
5. Algorithms: Fourth Edition, Robert Sedgewick, Addison-Wesley, 2008