Design & Analysis of Algorithm(DAA)

GUJARAT TECHNOLOGICAL UNIVERSITY

B.E. SEMESTER : VIII

INFORMATION TECHNOLOGY

Subject Name: DESIGN AND ANALYSIS OF ALGORITHM

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.

2. Analysis of Algorithm: The efficient algorithm, Average and worst case analysis, Elementary operation, Asymptotic Notation, Analyzing control statement, Amortized analysis, Sorting Algorithm, Binary Tree Search.

3. Divide and Conquer Algorithm: Introduction, Multiplying large Integers Problem, Problem Solving using divide and conquer algorithm - Binary Search, Sorting (Merge Sort, Quick Sort), Matrix Multiplication, Exponential.

4. 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

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

6. Exploring Graphs: An introduction using graphs and games, Traversing Trees – Preconditioning, Depth First Search - Undirected Graph, Directed Graph, Breath First Search, Backtracking – The Knapsack Problem, The Eight queens problem, General Template.

7. String Matching: Introduction, The naive string matching algorithm, The Rabin- Karp algorithm, String Matching with finite automata.

8. Introduction to NP-Completeness: The class P and NP, Polynomial reduction, NP- Completeness Problem, NP-Hard Problems.

Text Books:
1. Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, PHI.
2. Fundamental of Algorithms by Gills Brassard, Paul Bratley, PHI.
Reference Books:
1. Design and Analysis of Algorithms, Dave and Dave, Pearson.
2. Algorithm Design: Foundation, Analysis and Internet Examples, GoodRich, Tamassia, Wiley
India
3. Introduction to Design and Analysis of Algorithms, Anany Levitin, Pearson.

Practical List

Sr. No.	Aim Of Practical	Link to Syllabus	Link to Question Bank
1.	Write a C/C++ program to implement Bubble , Selection sort and measure time complexity	Unit 2	Module 2 Q. No-6
2.	Write a C/C++ program to implement the Quick Sort and measure time complexity.	Unit 2	Module 2 Q. No-7
3.	Write a C/C++ program to implement the Merge Sort using Divide and conquer strategy.	Unit 3	Module 3 Q. No-1
4.	Write a program to implement Binary Search using C or C++ programming.	Unit 2	Module 3 Q. No-2
5.	Write a C/C++ program to implement Kruskal’s algorithm using Greedy strategy.	Unit 4	Module 4 Q. No-3
6.	Write a C/C++ program to implement Prim’s algorithm using Greedy strategy.	Unit 4	Module 4 Q. No-4
7.	Write a C/C++ program to implement knapsack problem using Dynamic Programming.	Unit 5	Module 5 Q. No-5
8.	Write a C/C++ program to implement Matrix Chain Multiplication using Dynamic Programming.	Unit 5	Module 5 Q. No-6
9.	Write a C/C++ program to implement Depth First Search and Breath First Search Algorithm.	Unit 6	Module 6 Q. No-2,3
10.	Write a C/C++ program to implement Naive/ Rabin-Karp String Matching Algorithm.	Unit 7	Module 7 Q. No-2