(c) Implement the activity-selection problem ( You are given n activities with their start and
finish times. Select the maximum number of activities that can be performed by a single
person, assuming that a person can only work on a single activity at a time.
Example: Consider the following 6 activities.
start[] = {1, 3, 0, 5, 8, 5}; finish[] = {2, 4, 6, 7, 9, 9};
The maximum set of activities that can be executed by a single person is {0, 1, 3, 4} ).
II. (a)
(b) Consider the following scheduling problem. You are given n jobs. Job i is specified by
an earliest start time si, and a processing time pi. We consider a preemptive version of
the problem where a job's execution can be suspended at any time and then completed
later. For example if n = 2 and the input is s1 = 2, p1 = 5 and s2 = 0, p2 = 3, then a legal
preemptive schedule is one in which job 2 runs from time 0 to 2 and is then suspended.
Then job 1 runs from time 2 to 7 and secondly, job 2 is completed from time 7 to 8. The
j = 1, where Cj is the time when job j is
completed and j runs from 1 to n. In the example schedule given above, C1 =7 and C2
=8.
(c) Implement the activity-selection problem ( You are given n activities with their start and
finish times. Select the maximum number of activities that can be performed by a single
person, assuming that a person can only work on a single activity at a time.
Example: Consider the following 6 activities.
start[] = {1, 3, 0, 5, 8, 5}; finish[] = {2, 4, 6, 7, 9, 9};
The maximum set of activities that can be executed by a single person is {0, 1, 3, 4} ).
Experiment 4 (Binary Search Tree)
I. (a) Finding the maximum and minimum element in BST.
(b) Finding Kth smallest/largest element in BST.
II. Write a program for converting the array to BST (Input: Unsorted/Sorted array).
III. Write a program for printing all the elements of BST in the range K1 and K2 (Input:
BST and two numbers K1 and K2).
IV. Write a program for removing the duplicates in array using BST.
Experiment 5 (Binary Tree)
I. Write a program to build a binary tree for the given elements (i.e., integers) and give
traversal functions: inorder, preorder, postorder.
II. Write a program to transform given a tree into a binary tree.
III. Write a program to represent an arithmetic expression in binary tree format.
Experiment 6 (Graph Algorithms)
I. (a)
algorithm.
(b) Implement the algorithm for Hash Tables to check both arrays have same set of
numbers/characters (Input: given two arrays of unordered numbers/characters).
II. (a)
(b) Implement the algorithm for Hash Tables to removing the duplicate characters/ numbers
(Input as an array of characters/numbers).
III. (a)
algorithm.
(b) Give an algorithm for finding non repeated character in a string/number using Hash
Tables. Examp
Experiment 7 (Shortest Path Finding in Graph)
I. (a) From a given vertex in a weighted connected graph, find shortest paths to other vertices
using Dijkstra's algorithm.
(b) Draw simple, connected weighted graph with 10 vertices and 18 edges, such that graph
contains minimum weight cycle with at least 4 edges. Show that the Bellman-Ford
algorithm find this cycle.
II. (a) Draw simple, connected weighted graph with 8 vertices and 16 edges, each with unique
edge weight. Identify one vertex as a start vertex and obtain shortest path using
Dijkstra's algorithm.
(b) From a given vertex in a weighted connected graph, find shortest paths to other vertices
using Bellman-Ford algorithm.
III. (a) Find the kth shortest path between two given nodes of a graph.
(b) Give an algorithm to determine whether a directed graph with positive and negative
cost edges has negative cost cycle.
Experiment 8 )
I. (a) -Warshall algorithm.
(b)
Experiment 9 (BFS and DFS problems)
I. (a) Write an algorithm to print all the nodes reachable from a given starting node in a
digraph using BFS method.
(b) Obtain the Topological ordering of vertices in a given digraph.
II. (a) Check whether a given graph is connected or not using DFS method.
(b) Find the strongly connected components in a digraph.
Experiment 10 (Flow and Sorting Networks)
I. (a) Implement the Ford-Fulkerson method for maximum flow network.
(b) Implement the Maximum bipartite matching problem in the graph.
(c) Implement the Bitonic sorting algorithm.
Note: Additional Programs are for those students who wish to do advance problems
Additional Problem 1 (Data Structures)
I. Write an algorithm for finding counting inversions in an array. Inversion is a pair such
that for an array A = {a1, a2, a3,...., an}, and ai > aj and i < j
II. Given an array. Let us assume that there can be duplicates in the list. Write an algorithm
to search for an element in the list in such a way that we get the highest index if there
are duplicates.
III. Write an algorithm for finding i and j in an array A for any key such that
A[j]2 + A[i]2 == key
IV. Given key in a sorted array A with distinct values. Find i, j, k such that
A[i] + A[j] + A[k] == key
V. Suppose an array A has n distinct integers. Increasing sequence is given as
A[1].........A[k] and decreasing sequence is given as A[k+1]........A[n]. Write an
algorithm for finding k.
VI. You have 1 to N-1 array and 1 to N numbers and one number is missing. Write an
algorithm for finding that missing number.
Additional Problem 2 (Dynamic Programming & Greedy Algorithms)
I. Implement the job sequencing with deadlines problem using the fixed tuple size
formulation.
II. (a) Implement the algorithm to compute roots of optimal sub-trees.
(b) Implement the optimal binary search tree problem.
III. (a) Write an algorithm for partitioning problem. Partition problem is to determine whether a
given set can be partitioned into two subsets such that the sum of elements in both
subsets is same.
(b) Find a subset of a given set S = {S1, S2 m} 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.
(c) Given a value N, if we want to make change for N cents, and we have infinite supply of
each of S = {S1, S2 m} valued coins, how many ways can we make the change?
, 3}, there are
four solutions: {1, 1, 1, 1}, {1, 1, 2}, {2, 2}, {1, 3}. So output should be 4. For N = 10
and S = {2, 5, 3, 6}, there are five solutions: {2, 2, 2, 2, 2}, {2, 2, 3, 3}, {2, 2, 6}, {2, 3,
5} and {5, 5}. So the output should be 5.
Additional Problem 3 (Advanced Data Structures)
I. Perform the following operations on B-Tree:
a) Creation
b) Insertion.
c) Deletion.
d) Searching.
II. Implement the conversion of the BST to B-tree.
III. Perform the following operations on Binomial heaps:
a) Creation
b) Insertion.
c) Deletion.
d) Searching.
e) Uniting two Heaps
f) Extracting the minimum node
IV. Perform the following operations on Fibonacci heaps:
a) Creation
b) Insertion.
c) Deletion.
d) Searching.
e) Uniting two Heaps
f) Extracting the minimum node
Additional Problem 4 (Graph Algorithms)
I. Perform the following operations on Disjoint set:
a) MAKE-SET
b) UNION
c) FIND-SET
d) INSERT
e) DELETE
f) SPLIT
g) Returns the minimum object in SET
II. Perform the following Union-by-Weight operations on a universe of 10 elements (0-9,
each initially in their own set). Draw the forest of trees that result. U(1,5); U(3,7);
U(1,4);U(5,7); U(0,8); U(6,9); U(3,9). If the sets have equal weight, use the root with
the smaller value as the root of the new set.
III. Let G be a connected graph of order n. Write an algorithm for finding maximum number
of Cut-vertices that G can contain. Cut-vertex is a vertex which when removed from the
graph splits it into two disconnected components.
IV. An Euler circuit for an undirected graph is a path that starts and ends at the same vertex
and uses each edge exactly once. A connected undirected graph G has an Euler circuit.
If and only If energy vertex is of even degree. Give an algorithm and implement to find
the Euler Circuit in a graph with e edges provided one exists.
Additional Problem 5 (Other Techniques)
I. Implement N Queen's problem.
II. Implement Sudoku problem.
III. Design an efficient solution for tower of Hanoi problem.
IV. Implement 0/1 Knapsack problem.
V Implement the travelling salesman problem (TSP).
VI. Given a rod of length n inches and an array of prices that contains prices of all pieces of
size smaller than n. Determine the maximum value obtainable by cutting up the rod and
selling the pieces. For example, if length of the rod is 8 and the values of different
pieces are given as following, then the maximum obtainable value is 22 (by cutting in
two pieces of lengths 2 and 6)
Length | 1 2 3 4 5 6 7 8
-----------------------------------------------------
Price | 1 5 8 9 10 17 17 20
VII Implement the Coin change problem.
VIII. Design the Graph coloring problem
