DAA LAB (Design and Analysis of Algorithms LAB)

List of Programs:

1. WAP to find sum of first n natural numbers, using functions, and calculate its complexity.
2. WAP to find sum of squares of first n natural numbers, using functions, and calculate its complexity.
3. WAP to find sum of cubes of first n natural numbers, using functions, and calculate its complexity.
4. WAP to find factorial of a natural number, using functions, and calculate its complexity.
5. WAP to check whether a no is prime or not, using functions, and calculate its complexity.
6. WAP to print Fibonacci Series, using functions, and calculate its complexity.
7. WAP to add two matrices, using functions, and calculate its complexity.
8. WAP to subtract two matrices, using functions, and calculate its complexity.
9. WAP to multiply two matrices, using functions, and calculate its complexity.
10. WAP to transpose a matrix, using functions, and calculate its complexity.
11. WAP in C++ to search an item in an array using Linear Search, using functions, and calculate its complexity.
12. WAP in C++ to search an item in an array using Binary Search, using functions, and calculate its complexity.
13. WAP in C++ to find the divisors of a number, using functions, and calculate its complexity.
14. WAP in C++ to sort the array using Bubble Sort, using functions, and calculate its complexity.
15. WAP in C++ to sort the array using Selection Sort, using functions, and calculate its complexity.
16. WAP in C++ to sort the array using Insertion Sort, using functions, and calculate its complexity.
17. Sort a given set of elements using the Quick sort method and determine the time required to sort the elements. Repeat the experiment for different values of n, the number of elements in the lIst to be sorted and 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.
18. Implement a parallelized Merge Sort algorithm to sort a given set of elements and determine the time required to sort the elements. Repeat the experiment for different values of n, the number of elements in the list to be sorted and 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.
19. Obtain the Topological ordering of vertices in a given digraph.
20. Compute the transitive closure of a given directed graph using Warshall’s algorithm.
21. Implement 0/1 Knapsack problem using Dynamic Programming.
22. From a given vertex in a weighted connected graph, find shortest paths to other vertices using Dijikstra’s algorithm.
23. Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal’s algorithm.
24. Print all the nodes reachable from a given starting node in a digraph using BFS method.
25. Check whether a given graph is connected or not using DFS method.
26. 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}.A suitable message is to be displayed if the given problem instance doesn’t have a solution.
27. Implement any scheme to find the optimal solution for the Traveling Salesperson problem and then solve the same problem instance using any approximation algorithm and determine the error in the approximation.
28. Find Minimum Cost Spanning Tree of a given undirected graph using Prim‟s algorithm.
29. Implement All-Pairs Shortest Paths Problem using Floyd’s algorithm. Parallelize this algorithm, implement it using Open and determine the speed-up achieved.
30. Implement N Queen’s problem using Back Tracking.

DCRUST SYLLABUS

CSE 286 C (Design and Analysis of Algorithms Lab)

CATEGORY : ENGINEERING SCIENCE COURSE

Course Objectives:

1. To develop and code program for the algorithms and analyze it to determine its computational complexity.
2. To identify and analyze worst-case running times of algorithms.
3. To model given engineering problem using graph and trees and write the corresponding algorithm to solve the problems.
4. To strengthen the ability to identify and apply the suitable algorithm for the given real world problem.

List of Programs:

1. Sort a given set of elements using the Quick sort method and determine the time required to sort the elements. Repeat the experiment for different values of n, the number of elements in the lIst to be sorted and 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.
2. Implement a parallelized Merge Sort algorithm to sort a given set of elements and determine the time required to sort the elements. Repeat the experiment for different values of n, the number of elements in the list to be sorted and 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.
3. a.  Obtain the Topological ordering of vertices in a given digraph.
   • b. Compute the transitive closure of a given directed graph using Warshall’s algorithm.
4. Implement 0/1 Knapsack problem using Dynamic Programming.
5. From a given vertex in a weighted connected graph, find shortest paths to other vertices using Dijikstra’s algorithm.
6. Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal’s algorithm.
7. a. Print all the nodes reachable from a given starting node in a digraph using BFS method.
   • b. Check whether a given graph is connected or not using DFS method.
8. 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}.A suitable message is to be displayed if the given problem instance doesn’t have a solution.
9. Implement any scheme to find the optimal solution for the Traveling Salesperson problem and then solve the same problem instance using any approximation algorithm and determine the error in the approximation.
10. Find Minimum Cost Spanning Tree of a given undirected graph using Prim‟s algorithm.
11. Implement All-Pairs Shortest Paths Problem using Floyd’s algorithm. Parallelize this algorithm, implement it using Open and determine the speed-up achieved.
12. Implement N Queen’s problem using Back Tracking.

Course Outcomes: Upon successful completion of the course, students will be able to:

1. Develop and code program for the algorithms and analyze it to determine its computational complexity.
2. Identify and analyze worst-case running times of algorithms.
3. Model given engineering problem using graph and trees and write the corresponding algorithm to solve the problems.
4. Identify and apply the suitable algorithm for the given real world problem.