10CSL47 DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY syllabus for CS


Unit-1 0 hours

Sort a given set of elements using the Quicksort 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.

Unit-2 0 hours

Using OpenMP, 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.

Unit-3 0 hours

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.

Unit-4 0 hours

Implement 0/1 Knapsack problem using Dynamic Programming.

Unit-5 0 hours

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

Unit-6 0 hours

Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal's algorithm.

Unit-7 0 hours

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.

Unit-8 0 hours

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.

Unit-9 0 hours

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.

Unit-10 0 hours

Find Minimum Cost Spanning Tree of a given undirected graph using Prim’s algorithm.

Unit-11 0 hours

Implement All-Pairs Shortest Paths Problem using Floyd's algorithm. Parallelize this algorithm, implement it using OpenMP and determine the speed-up achieved.

Unit-12 0 hours

Implement N Queen's problem using Back Tracking.

Last Updated: Tuesday, January 24, 2023