B.E. Computers, IT Notes/Solved Question papers Maharashtra, Mumbai - Free call 022-66752917: Analysis of algorithms

Showing posts with label Analysis of algorithms. Show all posts

Tuesday, May 27, 2014

ANALYSIS OF ALGORITHMS (AOA) DECEMBER 2011 COMPUTER AND SCIENCE SEMESTER 4

Con. 6785-11. MP-4342
(3 Hours) [ Total Marks : 100 ]

N.B : (1) Question No.1 is compulsory.
(2) Out of remaining 6 questions attempt any 4 questions.
(3) In all 5 questions to be attempted.

Q.1. (a)	Compare the time complexities of the following algorithm giving their	05
	complexities in terms of big -0,Ώ,Ө.
	(i) Quick sort (iii) Heap sort
	(ii) Shell sort (iv) Insertion sort.
(b)	State the applications of the Graph theory.	05
(c)	State advantages and disadvantages of recursion.	05
(d)	Write a routine to delete a word from a tries.	05
Q.2. (a)	What is Hamiltonian Cycle? Write an algorithm to find all Hamiltonian Cycles.	10
(b)	Calculate variable length Huffman code for following frequencies	10
	A=2, B=6, C=4, D=15, E=7, F=22, G=9, H=17.
Q.3. (a)	Explain 8-queen problem. Write an algorithm using backtracking to solve this	10
	problem.
(b)	Explain graphing coloring algorithm with an example.	10
Q.4. (a)	Write an algorithm for 0/1 knapsack problem using dynamic programming	10
	approach.
(b)	Find the minimum cost spanning tree for the following graph using prim's	10
	algorithm.
Q.5. (a)	What is travelling Salesman Problem? How to solve the same problem using	10
	Branch and bound?Explain with example.
(b)	Sort the following list of elements in ascending order using merge sort	10
	technique. Give the output of each pass.
	90 20 80 89 70 65 85 74.
Q.6. (a)	Write functions to implement DFS and BFS graph searching methods.	10
(b)	To implement the binary search, prove that the complexity of binary search is	10
	0(log2n).
Q.7.	Write short note on:	20
	(a) Randomized Algorithms
	(b) Divide and Conquer Strategy
	(c) Optimal Storage on Tape
	(d) Strassen's Matrix Multiplication.

ANALYSIS OF ALGORITHMS (AOA) DECEMBER 2010 COMPUTER AND SCIENCE SEMESTER 4

Con.6221-10. GT-6462

(3 Hours) [Total Marks : -100]

N.B.: (1) Question No.1 is compulsory.
(2) Attempt any four out of remaining six questions.
(3) Assume suitable data.
(4) Figures to right indicate full marks.

1. (a) Explain Big-oh, Omega and Theta Notations with the help of diagram. How do we analyze
and measure time complexity of algorithm? [10 Marks]
(b) Calculate variable length Huffman code for the following frequencies: [10 Marks]
A=1, B=2, C=1, D=4, E=8, F=5, G=14, H=22

2. (a) Prove that for the quick sort, [10 Marks]
(i) Worst case efficiency is T(N) = O(N2)
(ii) Best case efficiency is T(N) = O(NlogN)
(b) Explain the strassen's Matrix Multiplication. [10 Marks]

3. (a) Find MST of following graph using prim's and kruskal's Algorithm. [10 Marks]

(b) Explain optimal storage on tape with example. [10 Marks]

4. (a) Explain Hamiltonian Cycle and give an algorithm to find all Hamiltonian cycle. [10 Marks]
(b) Consider the following instance of the Knapsack problem: [10 Marks]
No. of objects n=3, knapsack capacity m=20, profits (p1,p2,p3) = (25,24,15) and
weights (w1,w2,w3) = (18,15,10)
Find out the optimal solution using greedy method.

5. (a) Describe 8 Queen problem. Write an algorithm using backtracking to solve this
problem. [10 Marks]
(b) What is Travelling Salesman problem. How to solve the same problem using Branch
Bound. Explain with example. [10 Marks]

5. (a) Describe the advantages of dynamic programming. How it differ from Divide and
Conquer. [10 Marks]
(b) Sort the following list of elements in ascending order using merge sort technique. Give output
of each pass. [10 Marks]
90, 20, 80, 89, 70, 65, 85, 74

7. (a) Define the Knuth-Morris-Fratt Algorithm for string matching. [10 Marks]
Write a function to implement the concept of the same algorithm.
(b) Write short note on : (any two) [10 Marks]
i) Tries
ii) Job sequencing with Deadlines
iii) Randomized Algorithms.

ANALYSIS OF ALGORITHMS (AOA) MAY 2010 COMPUTER AND SCIENCE SEMESTER 4

Con.3705-10 (REVISED COURSE) AN-3454

(3 Hours) [Total Marks :-100]

N.B. (1) Question No.1 is compulsory.
(2) Attempt any four questions from the remaining six questions.
(3) Assumption made should be clearly stated.
(4) Assume suitable data whenever required.

1. (a) Write a routine to delete a word from tries. [5 Marks]
(b) Write an algorithm to find the sum of series and also find its time complexity
where, [5 Marks]
n
s= ∑ i2
i=1
(c) Compare Greedy method & backtracking method. [5 Marks]
(d) What is recursion? Write a routine to calculate Fibonacci series using it. [5 Marks]

2. (a) Implement the binary search, prove that the complexity of binary search is
O(log2N). [10 Marks]
(b) Explain randomized version of Quick sort and evaluate its complexity with
example. [10 Marks]

3. (a) Explain with example job sequencing with deadlines. [10 Marks]
(b) Explain optimal storage on tapes with example. [10 Marks]

4. (a) Explain longest common subsequence with example. [10 Marks]
(b) Write a note on all pairs shortest path algorithm. [10 Marks]

5. (a) Write and explain sum of subset algorithm, [10 Marks]
with n=4, w= {2,7,8,15}, m=17
(b) Explain backtracking method to solve 0/1 knapsack problem. [10 Marks]
Find solution for n=3, m=20
(p1, p2, p3) = (25,24,15) and (w1,w2,w3) = (18,15,10).

6. (a) Find minimum cost spanning tree for the given graph figure,using prim's & kruskal's
Algorithm :- [10 Marks]

(b) Explain how branch and bound method can be applied to solve 15 puzzle using least
cost search. [10 Marks]

7. (a) Implement merge sort using divide & conquer strategy. [10 Marks]
sort the following numbers showing output of each pass.
100,20, 38, 14, 48, 07, 17, 57, 93, 35
(b) Find the Huffman code for the following set of frequencies based on the first 8
Fibonacci numbers. [10 Marks]
a=1, b=1, c=2, d=3, e=5, f=8, g=13, h=21.

Monday, May 26, 2014

ANALYSIS OF ALGORITHMS (AOA) MAY 2012 COMPUTER AND SCIENCE SEMESTER 4

Con. 4608-12. GN-8795
(3 Hours) [Total Marks : 100]

N.B. (1) Question No.1 is compulsory.
(2) Attempt any four questions from remaining six questions.
(3) Assumption made should be clearly stated.
(4) Assume suitable data whenever required.

1. (a)	Explain Big-oh, Omega and Theta Notations with help of example. How do we	10
	Analyse and measure time and space complexity of algorithms ?
(b)	Construct the Optimal Binary Search Tree for the identifier set	10
	(a1, a2, a3, a4) = (cout, float, if, while).
2. (a)	Explain Flow Shop Scheduling with help of suitable examples.	10
(b)	Write down Prim's Algorithm and solve following problem :-	10

3. (a)	Write Randomized Quick Sort Algorithm and explain with help of example.	10
(b)	Explain 0/1 Knapsack problem using Branch and Bound Method.	10
4. (a)	Describe Traveling Salesperson problem. Explain how to solve using Branch	10
	and Bound Method.
(b)	Write algorithm of Sum of Subsets. Solve following problem and draw portion	10
	of state space tree.
	w={5, 7, 10, 12, 15, 18, 20} and m=35. Find all possible subsets of w that sum to m.
5. (a)	Explain Strassen's Matrix multiplication and derived its time complexity.	10
(b)	Write down Knuth-Morris-Pratt Algorithm.	10
6. (a)	Write algorithm of job Sequencing with Deadlines. Solve the following problem	10
	n = 5.
	(P1, P2, P3, P4, P5) = (20, 15, 10, 5, 1) and
	(d1, d2, d3, d4, d5) = (2, 2, 1, 3, 3).
(b)	Explain Hamiltonian Cycles Algorithm, and draw static space tree.	10
7.	Write short notes on (Any four) :-	20
	(a) Tries
	(b) Randomized Algorithm
	(c) N-Queens Problem
	(d) Bellman and Ford Algorithm
	(e) Optimal Storage on Tapes.

ANALYSIS OF ALGORITHMS (AOA) DECEMBER 2009 COMPUTER AND SCIENCE SEMESTER 4

Con.5681-09. (REVISED COURSE) SP-7808

(3 Hours) [Total Marks: -100]

N.B.: (1) Question No.1 is compulsory.
(2) Attempt any four questions out of the remaining six questions.
(3) Assumption made should be clearly stated.
(4) Assume suitable data whenever required.

1. (a) Consider the iterative program to find fibonacci numbers. [5 Marks]
unsigned int fibonacci (Unsigned int n)
{
int previous = -1
int result = 1
for (Unsigned int i20; i< = n; ++i)
{
int Const Sum = result + previous,
previous = result;
result = sum;
}
return = sum;
}
Determine the running time of the above algorithm.
(b) Discuss the best case and worst case efficiency for a quick sort algorithm. [5 Marks]
(c) Write and explain with illustration the recursive algorithm for a merge sort. [5 Marks]
(d) Explain the Strassen's Matrix Multiplication. [5 Marks]

2. (a) Explain the following algorithm with an example and give its complexity: [10 Marks]
(i) Selection Sort ii) Heap Sort
(b) Write the algorithm for for pattern matching using Boyer-Moore Algorithm. Suppose we
have a string - abacaabaccabacabaabb. Illustrate the Boyer Moore algorithm to search
a string -> abacab. [10 Marks]

3. (a) What are trics? What are its applications? Briefly, describe the types of tries. [10 Marks]
(b) Illustrate the heap sort algorithm for the array. [10 Marks]
A= <27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9>

4. (a) Find the minimum cost spanning tree for the graph using Prim's and Kruskal's
algorithm. [10 Marks]

(b) Write an algorithm for 0/1 Knapsack problem using dynamic programming. When do we
use the greedy algorithm for the Knapsack problem? Explain. [10 Marks]

5. (a) Find the Huffman code for the following set of frequencies, based on the fist 8 fibonacci
numbers. [10 Marks]
a= 1, b = 1, c = 2, d = 3, e = 5, f = 8, g = 13, h = 21.
(b) Explain the graph coloring algorithm with an example. [10 Marks]

6. (a) Explain the 8-queen problem. Write an algorithm using back -tracking to solve this
problem. [10 Marks]
(b) Compare the Radix sort and Bucket sort algorithm and state its complexity. [10 Marks]
(Write both the algorithms). [10 Marks]

7. (a) Explain the quick sort algorithm using the Divide and Conquer method. [10 Marks]
Determine the complexity for the worst case/best case and average case.
(b) Write short notes on the following :- [10 Marks]
(i) Warshall's Algorithm (ii) Djkstra's Algorithm

ANALYSIS OF ALGORITHMS (AOA) MAY 2009 COMPUTER AND SCIENCE SEMESTER 4

Con.3546-09 (REVISED COURSE) VR-3783

(3 Hours) [Total Marks :- 100]

N.B.: (1) Question No.1 is compulsory.
(2) Attempt any four questions out of remaining six questions.
(3) Assumptions made should be clearly stated.
(4) Figures to the right indicate full marks.
(5) Assume suitable data wherever required but justify the same.

1. (a) An algorithm takes 0.5 ms for input size 100. How long it will take for input size 500 if the
running time is - [5 Marks]
(i) Quadratic (ii) NlogN
(b) Explain strassen's matrix multiplication. [5 Marks]
(c) State advantages and disadvantages of recursion. [5 Marks]
(d) prove that worst case efficiency of quick sort is O(n2). [5 Marks]

2. (a) Explain Radix sort algorithm with example. Give its complexity. [10 Marks]
(b) Explain Boyer-Moore method. Give its advantages over Brute-Force method. [10 Marks]

3. (a) Explain how branch and bound method can be applied to 15 puzzle problem using LC search.
Write it's algorithm. [10 Marks]
(b) Explain graph coloring algorithm with backtracking. [10 Marks]

4. (a) Explain Merge sort algorithm. Sort following numbers with merge sort. Give output of
each pass. [10 Marks]
84, 25, 36, 15, 48, 09, 17, 55, 92, 36
(b) Explain 8-queen problem. Write a algorithm using backtracking to solve this
problem. [10 Marks]

5. (a) Find minimum cost spanning tree for the graph shown below using prime algorithm. [10 Marks]

(b) Write an algorithm for 0/1 Knapsack problem using dynamic programming
approach. [10 Marks]

6. (a) What is branch and bound method? Discuss the solution to Travelling salesman problem using
branch and bound method. [10 Marks]
(b) What is multistage graph problem? Discuss its solution based on dynamic programming
approach. [10 Marks]

7. (a) Write note on "Tries" [10 Marks]
(b) (i) Compare Greedy method and Dynamic programming. [5 Marks]
(ii) Write in brief about 'Divide and Conquer' strategy. [5 Marks]

Saturday, May 24, 2014

ANALYSIS OF ALGORITHMS (AOA) DECEMBER 2012 COMPUTER AND SCIENCE SEMESTER 4

Con.7847-12 KR-7472

(3 Hours) [Total Marks :- 100]

N.B.: (1) Question No.1 is compulsory.
(2) Solve any four questions out of remaining six questions.
(3) Figures to the right indicate full marks.
(4) Assume suitable data if necessary but justify the same.

1. (a) Arrange the following function in increasing order. [5 Marks]

(b) Explain general method of Dynamic programming. List different examples of it. [5 Marks]
(c) Justify greedy approach for solving Knapsack problem. [5 Marks]
(d) State graph coloring problem. State the strategy used to solve above problem. [5 Marks]

2. (a) Sort the following numbers using Merge sort. Give the output of each pass. Write an algorithm
for Merge sort. [10 Marks]
27, 6, 18, 25, 48, 59, 98, 34
(b) Write an algorithm for minimum spanning tree using Prim's method. [10 Marks]

3. (a) Explain N-Queen's problem using Backtracking with algorithm. [10 Marks]
(b) Consider the following set of frequencies. [10 Marks]
A=2, B=6, C=4, D=15, E=7, F=22, G=9, H=17
Find Huffman codes for the same.

4. (a) Describe O/I Knapsack problem. How to solve it using Branch and Bound? [10 Marks]
(b) Write an algorithm for binary search. Derive its best case and worst case
complexities. [10 Marks]

5. (a) For the following graph find all pair shortest path using Dynamic programming. [10 Marks]

(b) Explain optimal storage on tapes with example. [10 Marks]

6. (a) Find longest common subsequence of given two strings. [10 Marks]
X = {B A T A}
Y = {T A T A}
(b) Explain single source shortest path using Dynamic programming. Write an algorithm
for same. [10 Marks]

7. Write short notes on the following:- [20 Marks]
(a) Radix Sort
(b) Job sequencing with Dead lines
(c) Strassen's Matrix Multiplication
(d) Branch and Bound strategy

ANALYSIS OF ALGORITHMS (AOA) MAY 2013 COMPUTER AND SCIENCE SEMESTER 4

Con. 6646-13. GS-7323
(3 Hours) [Total Marks : 100]

N.B. (1) Question No. 1 is compulsory.
(2) Attempt any four questions out of remaining six questions.
(3) Assume suitable data wherever necessary.

1. (a)	Explain Divide and Conquer strategy. Write control abstraction (General method)	10
	for it. List any four examples that can be solved by divide and conquer.
(b)	Explain Asymptotic notations. Explain time complexity and space complexity in detail.	10
2. (a)	Explain Graph coloring problem using backtracking. Write algorithm for same.	10
(b)	Find out single source shortest path for following graph using Dijkstra's algorithm.	10

3. (a)	Find the longest common subsequence from the given two sequences :-	10
	P= (100101101101)
	Q= (0110)
(b)	Explain 15-puzzle problem using branch and bound.	10
4. (a)	Sort following numbers using Quicksort algorithm. Show all passes of execution.	10
	Also state the time complexity.
	65, 70, 75, 80, 85, 60, 55, 50, 45
(b)	Explain and write Knunth-Morris pratt algorithm. Explain with an example.	10
5. (a)	Explain job-sequencing with deadlines. Solve the following instance :	10
	n = 5.
	(P1, P2, P3, P4, P5) = (20, 15, 10, 5, 1)
	(d1, d2, d3, d4, d5) = (2, 2, 1, 3, 3)
(b)	Solve following sum of subset problem using backtracking :	10
	w = { 1, 3, 4, 5 }
	m = 8
	Find all possible subsets of 'w' that sum to 'm'.
6. (a)	Solve shortest path from source 1 for following graph using dynamic	10
	programming.
(b)	Explain travelling salesperson problem using branch and bound method.	10
7.	Write short notes :-	20
	(a) Differentiate between greedy approach and dynamic programming.
	(b) Optimal storage on tapes.
	(c) Radix sort
	(d) Minimum spanning Tree using Kruskal's Algorithm.

ANALYSIS OF ALGORITHMS (AOA) DECEMBER 2013 COMPUTER AND SCIENCE SEMESTER 4

Con.5779-13. LJ-10604

(3 Hours) [Total Marks : -100]

N.B.: (1) Question No.1 is compulsory.
(2) Attempt any four out of remaining six questions.
(3) Assume suitable data wherever required.

1. (a) Explain divide and conquer strategy. Write control abstraction (General Method) for it.
List any four problems that can be solved using divide and conquer. [10 Marks]
(b) Explain asymptotic . Explain time complexity and space complexity in detail. [10 Marks]

2. (a) Construct the optimal binary search tree for identifier set [10 Marks]
(a1,a2,a3,a4,) = (count, float, if, while)

(b) Explain 0/1 knapsack problem using Branch and Bound method. [10 Marks]

3. (a) Explain flow shop scheduling with the help of example. [10 Marks]
(b) Solve following problem using krushkal's algorithm which is used to find minimum
spanning tree. [10 Marks]

4. (a) State graph coloring algorithm. Explain strategy used for solving it along with
example. [10 Marks]
(b) Consider following set of frequencies. [10 Marks]
A=2 B=5 C=7 D=8 E=7 F=22 G=4 H=17
Find Huffman code for same.

5. (a) Explain Binary search. Derive its best case and worst case complexity. [10 Marks]
(b) Find shortest path using Djkstra's algorithm for the following graph assume source
node is A. [10 Marks]

6. (a) Explain 8 Queen problem and strategy used to solve it. [10 Marks]
(b) Explain job sequencing with dead lines along with example. [10 Marks]

7. Write short notes on the following :- [20 Marks]
(i) Radix sort
(ii) Tries
(iii) Randomised algorithm
(iv) Strassen's matrix multiplication.