Design and Analysis of Algorithm Lab

List of Experiments / Activities

1. 1Program for Recursive Binary & Linear Search.
2. 2Program for Heap Sort.
3. 3Program for Merge Sort.
4. 4Program for Selection Sort.
5. 5Program for Insertion Sort.
6. 6Program for Quick Sort.
7. 7Knapsack Problem using Greedy Solution
8. 8Perform Travelling Salesman Problem
9. 9Find Minimum Spanning Tree using Kruskal’s Algorithm
10. 10Implement N Queen Problem using Backtracking
11. 11Sort 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. 12Sort 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. 136. Implement , the 0/1 Knapsack problem using (a) Dynamic Programming method (b) Greedy method.
14. 14From a given vertex in a weighted connected graph, find shortest paths to other vertices using Dijkstra's algorithm.
15. 15Find Minimum Cost Spanning Tree of a given connected undirected graph using Kruskal's algorithm. Use Union-Find algorithms in your program.
16. 16Find Minimum Cost Spanning Tree of a given undirected graph using Prim’s algorithm.
17. 17Write programs to (a) Implement All-Pairs Shortest Paths problem using Floyd's algorithm. (b) Implement Travelling Sales Person problem using Dynamic programming.
18. 18Design 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. 19Design and implement to find all Hamiltonian Cycles in a connected undirected Graph G of n vertices using backtracking principle.
20. Note: The Instructor may add/delete/modify/tune experiments, wherever he/she feels in a justified manner It is also suggested that open source tools should be preferred to conduct the lab ( C, C++ etc)