BCA-IVth Semester Syllabus by KSWU

 DAA Study Notes

BCA-IVth Semester Syllabus by KSWU

SUBJECT - Design and Analysis of Algorithm 

UNIT I - Design Of Efficient Algorithms And Elementary Data Structures: Algorithms, Analysis of Algorithms, Time and Space Complexity, Running Time of A Program. Review of Stack, Queues, Trees.Operations on Stack, Queue and Trees.Recursion, Heaps and Heap Sort.-For STUDY NOTES CLICK HERE  👉- UNIT I

UNIT II -Divide and Conquer: General Method, Binary Search, Max and Min, Merge Sort, Quick Sort, Matrix Multiplication And Related Operations; Strassen’s Matrix Multiplication, Inversion Matrices, LUP Decomposition And Its Application, Boolean Matrix Multiplication

UNIT III - The Greedy Method: The General Method, Knapsack Problem, Job Sequencing with Deadlines, Minimum Cost Spanning Trees: Prim’s Algorithm, Kruskal’s Algorithm. Optimal Storage on Tapes, Optimal Merge Patterns, Single Source Shortest Paths

UNIT IV - Dynamic Programming:The General Method, Multistage Graphs, All Pair’s Shortest Paths,0/1 knapsack, Travelling Salesman Problem.

UNIT V -Backtracking: General Methods, 8 – Queens Problem, Sum of Subsets, Knapsack Problem, NP – Hard and NP – Complete Problems.

Design and Analysis of Algorithm LAB

Program List: 

1. Program to construct a stack of integers and to perform the following operations on it: a. PUSH b. POP c. DISPLAY

 

2. Program to construct a queue of integers and to perform following operations on it: a. INSERT b. DELETE c. DISPLAY

 3. Program to find factorial of a given number using recursion 

4. Program to sort N numbers using Heap Sort 

5. Program to search an element from a list using Binary Search Technique 

6. Program to sort N numbers using Merge Sort 

7. Program to implement Strassen’s matrix multiplication 

8. Program to find Maximum and Minimum elements in a matrix 

9. Program to compute minimum spanning tree using Prim’s Algorithm 

10. Program to find shortest distance and shortest path from given source to all other nodes using Dijkstra’s Algorithm 

11. Program to implement all pair shortest problem using dynamic programming technique 

12. Program to find GCD of two integers using Euclid’s Algorithm