Scribd
Upload
8 views

Daa Lab Syllabus

Daa lab btech syllabus

Uploaded by

Gsgsgdh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
8 views

Daa Lab Syllabus

Daa lab btech syllabus

Uploaded by

Gsgsgdh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

GL BAJAJ Institute of Technology Greater Noida

Department of Information Technology


Design and Analysis of Algorithm Lab (KCS-553)

Course Outcome ( CO) Bloom’s Knowledge Level (KL)


At the end of course , the student will be able to:

Understand and implement algorithm to solve problems by iterative approach. K2, K4


CO 1
Understand and implement algorithm to solve problems by divide and conquer K3, K5
CO 2 approach.

Understand and implement algorithm to solve problems by Greedy algorithm approach. K4, K5
CO 3
Understand and analyze algorithm to solve problems by Dynamic programming, K4, K5
CO 4 backtracking.

Understand and analyze the algorithm to solve problems by branch and bound K3, K4
CO 5
approach.

List of Experiments:
1. Program for Recursive Binary & Linear Search.
2. Program for Heap Sort.
3. Program for Merge Sort.
4. Program for Selection Sort.
5. Program for Insertion Sort.
6. Program for Quick Sort.
7. Knapsack Problem using Greedy Solution
8. Perform Travelling Salesman Problem
9. Find Minimum Spanning Tree using Kruskal’s Algorithm
10. Implement N Queen Problem using Backtracking
11. 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 non graph sheet. The elements
can be read from a file or can be generated using the random number generator. Demonstrate using Java how the divide and-
conquer method works along with its time complexity analysis: worst case, average case and best case.
12. 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 non graph sheet. The elements
can be read from a file or can be generated using the random number generator. Demonstrate how the divide and- conquer
method works along with its time complexity analysis: worst case, average case and best case.
13. Implement, the 0/1 Knapsack problem using
(a) Dynamic Programming method
(b) Greedy method.
14. From a given vertex in a weighted connected graph, find shortest paths to other vertices using Dijkstra's algorithm.
15.Find Minimum Cost Spanning Tree of a given connected undirected graph using Kruskal's algorithm. Use Union-Find
algorithms in your program.
16. Find Minimum Cost Spanning Tree of a given undirected graph using Prim’s algorithm.
17. Write programs to (a) Implement All-Pairs Shortest Paths problem using Floyd's algorithm.
(b) Implement Travelling Sales Person problem using Dynamic programming.
18. Design and implement 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.
19. Design and implement to find all Hamiltonian Cycles in a connected undirected Graph G of n vertices using
backtracking principle.

You might also like