[VTU Model Paper Solved] 4th Sem Design and Analysis of Algorithms - DAA (21CS42)

[VTU Model Paper Solved] 4th Sem Design and Analysis of Algorithms - DAA (21CS42)

Download the Model Papers from Here:- 

• DAA Question Paper 1 Solved - https://teraboxapp.com/s/1pLV15anb6fiI-THAfjOMSg
• DAA Question Paper 2 Solved - https://teraboxapp.com/s/1EokUT822mtsRRSYjNP53RA

DESIGN AND ANALYSIS OF ALGORITHMS

Course Code 21CS42 

CIE Marks 50

Teaching Hours/Week (L:T:P: S) 3:0:2:0 

SEE Marks 50

Total Hours of Pedagogy 40 T + 20 P 

Total Marks 100

Credits 04 

Exam Hours 03

Module-1

Introduction: What is an Algorithm? It’s Properties. Algorithm Specification-using natural language, using Pseudo code convention, Fundamentals of Algorithmic Problem solving, Analysis Framework- Time efficiency and space efficiency, Worst-case, Best-case and Average case efficiency. Performance Analysis: Estimating Space complexity and Time complexity of algorithms. Asymptotic Notations: Big-Oh notation (O), Omega notation (Ω), Theta notation ( ) with examples, Basic efficiency classes, Mathematical analysis of Non-Recursive and Recursive Algorithms with Examples. Brute force design technique: Selection sort, sequential search, string matching algorithm with complexity Analysis. Textbook 1: Chapter 1 (Sections 1.1,1.2), Chapter 2(Sections 2.1,2.2,2.3,2.4), Chapter 3(Section3.1,3.2)Textbook 2: Chapter 1(section 1.1,1.2,1.3)

Laboratory Component: 

1. Sort a given set of n integer elements using Selection Sort method and compute its time complexity.  Run the program for varied values of n> 5000 and record the time taken to sort. Plot a graph of the time taken versus n.  The elements can be read from a file or can be generated using the random number generator. Demonstrate using C++/Java how the brute force method works along with its time complexity analysis: worst case, average case and best case.

Module-2

Divide and Conquer: General method, Recurrence equation for divide and conquer, solving it using Master’s theorem. , Divide and Conquer algorithms and complexity Analysis of Finding the maximum & minimum, Binary search, Merge sort, Quick sort. Decrease and Conquer Approach: Introduction, Insertion sort, Graph searching algorithms, Topological Sorting. It’s efficiency analysis. Textbook 2: Chapter 3(Sections 3.1,3.3,3.4,3.5,3.6) Textbook 1: Chapter 4 (Sections 4.1,4.2,4.3), Chapter 5(Section 5.1,5.2,5.3)

Laboratory Component:

1. Sort a given set of n integer elements using Quick Sort method and compute its time complexity. Run the program for varied values of n> 5000 and record the time taken to sort. Plot a graph of the time taken versus n. The elements can be read from a file or can be generated using the random number generator. Demonstrate using C++/Java how the divide-and-conquer method works along with its time complexity analysis: worst case, average case and best case.

2. Sort a given set of n integer elements using Merge Sort method and compute its time complexity. Run the program for varied values of n> 5000, and record the time taken to sort. Plot a graph of the time taken versus n. The elements can be read from a file or can be generated using the random number generator. Demonstrate using C++/Java how the divide-and-conquer method works along with its time complexity analysis: worst case, average case and best case.

Module-3

Greedy Method: General method, Coin Change Problem, Knapsack Problem, solving Job sequencing with deadlines Problems. Minimum cost spanning trees: Prim’s Algorithm, Kruskal’s Algorithm with performance analysis. Single source shortest paths: Dijkstra's Algorithm. Optimal Tree problem: Huffman Trees and Codes. Transform and Conquer Approach: Introduction, Heaps and Heap Sort. Textbook 2: Chapter 4(Sections 4.1,4.3,4.5) Textbook 1: Chapter 9(Section 9.1,9.2,9.3,9.4), Chapter 6( section 6.4)

Laboratory Component:

Write & Execute C++/Java Program

1. To solve Knapsack problem using Greedy method.

2. To find shortest paths to other vertices from a given vertex in a weighted connected graph, using Dijkstra's algorithm.

3. To find Minimum Cost Spanning Tree of a given connected undirected graph using Kruskal's algorithm. Use Union-Find algorithms in your program.

4. To find Minimum Cost Spanning Tree of a given connected undirected graph using Prim's algorithm.

Module-4

Dynamic Programming: General method with Examples, Multistage Graphs. Transitive Closure: Warshall’s Algorithm. All Pairs Shortest Paths: Floyd's Algorithm, Knapsack problem, Bellman-Ford Algorithm, Travelling Sales Person problem. Space-Time Tradeoffs: Introduction, Sorting by Counting, Input Enhancement in String Matching- Harspool’s algorithm. 

Textbook 2: Chapter 5 (Sections 5.1,5.2,5.4,5.9) Textbook 1: Chapter 8(Sections 8.2,8.4), Chapter 7 (Sections 7.1,7.2)

Laboratory Component:

Write C++/ Java programs to

1. Solve All-Pairs Shortest Paths problem using Floyd's algorithm.

2. Solve Travelling Sales Person problem using Dynamic programming.

3. Solve 0/1 Knapsack problem using Dynamic Programming method.

Module-5

Backtracking: General method, solution using back tracking to N-Queens problem, Sum of subsets problem, Graph coloring, Hamiltonian cycles Problems. 

Branch and Bound: Assignment Problem, Travelling Sales Person problem, 0/1 Knapsack problem 

NP-Complete and NP-Hard problems: Basic concepts, non- deterministic algorithms, P, NP, NP- Complete, and NP-Hard classes. 

Textbook 1: Chapter 12 (Sections 12.1,12.2) Chapter 11(11.3) Textbook 2: Chapter 7 (Sections 7.1,7.2,7.3,7.4,7.5) Chapter 11 (Section 11.1)

Laboratory Component:

1. Design and implement C++/Java Program to find a subset of a given set S = {Sl, S2,..., Sn} of n positive integers whose SUM is equal to a given positive integer d. For example, if S = {1, 2, 5, 6, 8} and d= 9, there are two solutions {1, 2, 6} and {1, 8}. Display a suitable message, if the given problem instance doesn't have a solution.

2. Design and implement C++/Java Program to find all Hamiltonian Cycles in a connected undirected Graph G of n vertices using backtracking principle.

Suggested Learning Resources:

Textbooks

1. Introduction to the Design and Analysis of Algorithms, Anany Levitin: 2nd Edition, 2009. Pearson.

2. Computer Algorithms/C++, Ellis Horowitz, SatrajSahni and Rajasekaran, 2nd Edition, 2014, Universities Press. 

Reference Books

1. Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronal L. Rivest, Clifford Stein, 3rd Edition, PHI.

2. Design and Analysis of Algorithms, S. Sridhar, Oxford (Higher Education)

Weblinks and Video Lectures (e-Resources):

1. http://elearning.vtu.ac.in/econtent/courses/video/CSE/06CS43.html

2. https://nptel.ac.in/courses/106/101/106101060/

3. http://elearning.vtu.ac.in/econtent/courses/video/FEP/ADA.html

4. http://cse01-iiith.vlabs.ac.in/

5. http://openclassroom.stanford.edu/MainFolder/CoursePage.php?course=IntroToAlgorithms

Activity Based Learning (Suggested Activities in Class)/ Practical Based learning

1. Real world problem solving and puzzles using group discussion. E.g., Fake coin identification, Peasant, wolf, goat, cabbage puzzle, Konigsberg bridge puzzle etc.,

2. Demonstration of solution to a problem through programming.

Related searches

vtu solved question papers pdf

vtu 1st sem question papers with answers 2023

vtu model question paper 2023 with answers

21cs32 model question paper with answers

vtu question papers with answers

www.vturesource.com question papers with answers

vtu 3rd sem question papers with answers

vtu question papers 1st sem