VTU Previous Exam Papers BE CS 4th Semester Analysis and Design of Algorithms July 2009

VTU Previous Exam Papers BE CS 4th Semester

Analysis and Design of Algorithms July 2009

 

Note: Answer any FIVE full questions.

1 a. Compare adjacency matrix and adjacency list methods of representing graphs. Give examples.

b. Write two separate algorithms to compute the indegree and outdegree of a directed, connected graph, which is represented as adjacency list.

 

2 a. Define the following asymptotic notations: 0,(H), Q.

b. Prove the following, using limit theory: i) log (n!)=fi(nlog nj   ii) Vl0n2+7n+3 =@(x)

c.   Write an iterative/recursive algorithm to find an and determine the time taken by your algorithm (apply brute-force method).

 

3 a. Show the steps in sorting the list using quicksort: 60, 50, 20, 80, 10, 90, 30, 70, 40.

b.  Using divide-and-conquer approach, write an algorithm for Quicksort and derive the best, worst, and average complexity of the same.

 

4 a. Write DFS and BFS trees for the following graph:

1

b.  Write an algorithm or C/C++ program to find the path between any two given vertices u and v of an undirected graph G – {V, E} based on DFS. You must print all the vertices appearing between u and v. Note that the path need not be the shortest.

 

5 a. What do you understand by Topological sort? Give its applications. Apply source removal method to find the topological order of the following graph:

2

b.  An efficient algorithm to generate all permutations of a positive integer n is by using Johnson-Trotter algorithm. Show the algorithm and all the intermediate steps for n = 3. Suggest the best data structure to implement this algorithm.

 

6 a. Show how would you sort the following list using Heapsort algorithm:

34, 12, 89, 34, 21, 12, 64, 10

b.  Explain the Horspool algorithm by taking an appropriate example.

c.   Devise a dynamic programming based algorithm for finding the all-pairs shortest path of a given connected, directed graph G. Trace your algorithm for the below given cost matrix.

  1 2 3 4
1 0 00 3 6
2 2 0 00 4
3 co 7 0 1
4 00 00 00 0

 

7 a. Let G – {V, E} be an undirected, connected graph. Write the Prim’s algorithm that finds the minimum spanning tree based on greedy technique. Give an example of a 5 vertex graph to illustrate its working.

b.  Apply backtracking to solve the following instance of sum-of-subset problem:

S – {1, 5,2, 7} with d = 8

 

8 a. Solve the following problem using Branch and Bound technique:

Job Persons

  Jobl Job2 Job3 Job4
A 9 2 7 8
B 6 4 3 7
C 5 8 1 8
D 7 6 9 4

B  Discuss the approximation algorithms for NP-hard problems.

Leave a Comment