IMPLEMENT THE FOLLOWING USING C/C++ LANGUAGE:
1. Implement Recursive Binary search and Linear search and determine
the time required to search an element. Repeat the experiment for
different values of n, the number of elements in the list to be searched
and plot a graph of the time taken versus n.
2. Sort a given set of elements using the Heapsort 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.
3. Sort a given set of elements using Merge 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.
4. Sort a given set of elements using Selection sort and determine the time
required to sort 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.
5. Implement 0/1 Knapsack problem using dynamic programming.
6. From a given vertex in a weighted connected graph, find shortest paths
to other vertices using Dijkstra's algorithm.
7. Sort a given set of elements using Quick sort method and determine the
time required 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.
8. Find Minimum Cost Spanning Tree of a given undirected graph using
Kruskal's algorithm.
9. 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.
10. 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.
11. a. Implement Horspool algorithm for String Matching.
b. Find the Binomial Co-efficient using Dynamic Programming.
12. Find Minimum Cost Spanning Tree of a given undirected graph using
Prim’s algorithm.
13. a. Implement Floyd’s algorithm for the All-Pairs- Shortest-Paths problem.
b. Compute the transitive closure of a given directed graph using
Warshall's algorithm.
14. Implement N Queen's problem using Back Tracking.