# Analysis and Design of Algorithms (2150703)

## Teaching Scheme (in Hours)

Theory Tutorial Practical Total
4 0 2 6

Subject Credit :  6

Theory
ESE (E)
Theory
PA (M)
Practical
ESE Viva (V)
Practical
PA (I)
Total
70 30 30 20 150

## Syllabus Content

###### Unit-1:  Basics of Algorithms and Mathematics

What is an algorithm?, Mathematics for Algorithmic Sets, Functions and Relations, Vectors and Matrices, Linear Inequalities and Linear Equations.

###### Unit-2:  Analysis of Algorithm

The efficient algorithm, Average, Best and worst case analysis, Amortized analysis , Asymptotic Notations, Analyzing control statement, Loop invariant and the correctness of the algorithm, Sorting Algorithms and analysis: Bubble sort, Selection sort, Insertion sort, Shell sort Heap sort, Sorting in linear time : Bucket sort, Radix sort and Counting sort

###### Unit-3:  Divide and Conquer Algorithm

Introduction, Recurrence and different methods to solve recurrence, Multiplying large Integers Problem, Problem Solving using divide and conquer algorithm - Binary Search, Max-Min problem, Sorting (Merge Sort, Quick Sort), Matrix Multiplication, Exponential.

###### Unit-4:  Dynamic Programming

Introduction, The Principle of Optimality, Problem Solving using Dynamic Programming – Calculating the Binomial Coefficient, Making Change Problem, Assembly Line-Scheduling, Knapsack problem, All Points Shortest path, Matrix chain multiplication, Longest Common Subsequence.

###### Unit-5:  Greedy Algorithm

General Characteristics of greedy algorithms, Problem solving using Greedy Algorithm - Activity selection problem, Elements of Greedy Strategy, Minimum Spanning trees (Kruskal’s algorithm, Prim’s algorithm), Graphs: Shortest paths, The Knapsack Problem, Job Scheduling Problem, Huffman code.

###### Unit-6:  Exploring Graphs

An introduction using graphs and games, Undirected Graph, Directed Graph, Traversing Graphs, Depth First Search, Breath First Search, Topological sort, Connected components.

###### Unit-7:  Backtracking and Branch and Bound

Introduction, The Eight queens problem , Knapsack problem, Travelling Salesman problem, Minimax principle

###### Unit-8:  String Matching

Introduction, The naive string matching algorithm, The Rabin-Karp algorithm, String Matching with finite automata, The Knuth-Morris-Pratt algorithm.

###### Unit-9:  Introduction to NP-Completeness

The class P and NP, Polynomial reduction, NP- Completeness Problem, NP-Hard Problems. Travelling Salesman problem, Hamiltonian problem, Approximation algorithms

## Reference Books

Sr. Title Author Publication Amazon Link
1 Introduction to Algorithms Thomas H. Cormen, Charles E. Leiserson, Ronald L. PHI
2 Fundamental of Algorithms Gills Brassard, Paul Bratley PHI
3 Introduction to Design and Analysis of Algorithms Anany Levitin Pearson
4 Foundations of Algorithms Shailesh R Sathe Penram
5 Design and Analysis of Algorithms Dave and Dave Pearson

### BE (CE) ⇒ Semester: 5

Darshan Institute of Engineering & Technology is a leading institute offering undergraduate (B.E.), postgraduate (M.E.) and Diploma programs in engineering.

## Our Contacts

At Hadala, Rajkot - Morbi Highway,
Gujarat-363650, INDIA

(+91) 97277 47310
(+91) 97277 47311