Subject Name : Computer Algorithms
Unit 1: Divide and Conquer
1. What is time & space complexity? Explain with example.
2. Explain with example Big-oh, Big-omega and Theta, Also plot a
graph for few functions.
3. What is algorithm, Explain different criteria’s needed for the
algorithm to satisfy.
4. Difference between priori and posteriori analysis.
5. Write a short note on Amortized complexity.
6. Explain Miller-Rabin primality testing algorithm.
7. Explain Divide and conquer Maxmin algorithm prove that its
complexity is 3n/2-2
.
8. Prove that complexity of binary search is O(log(n))
.
9. Explain merge sort algorithm and show that its complexity O(n log
n).
10.Prove that algorithm using divide and conquer approach to find
minimum and maximum number in list save 25% efforts compare to
straight forward approach to find minimum and maximum number
in list?
11.Write algorithm to select nth smallest element in list. compute its
complexity.
12.Explain general method of divide and conquer using example.
13.Difference between Las-Vegas and Monte Carlo Algorithm
14.Solve following recurrence relation by master method
i)T(n) = 9T(n/3) + n2.5
ii)T(n) = T(n/3) + n
15.Show that following equalities are correct.
i) 5n2
– 6n = O (n2
)
Unit 2: The Greedy Method
16.Solve job sequencing problem with deadlines using greedy
approach for following instance n=7.
(p1,p2,…,p7) = (50,15,18,16.8,25,60)
(d1,d2,…,d7) = (1,3,4,3,2,1,2)
17.Find the optimal placement for programs on tapes T0,T1,T2 where
programs are of length 12,5,8,32,7,15,18,26,4,3,11,10,6 also find
MRT.
18.Explain greedy method in general with example.
19.Prove If l1 <= l2 <= … <= ln, then ordering ij
= j , 1<= j<= n,
minimizes . Over all possible permutations of ij
20.Prove that if p1/w1>=p2/W2>=....>pn/Wn then greedy method
generates an optimal solution to given instance of knapscak
problem.
21.Compare Prim's and Kruskal's algorithm to find minimum cost
spanning tree(MST)
22.Find an optimal merge pattern for 10 files whose lengths are
26,32,12,6,85,55,90,35,3,11 ?
23.Solve following problems.
ii) Find out max profit of knapsack when (p1,p2,p3)= (1,4,5)
and (w1,w2,w3) = (3,5,6) , m=10.
Unit 3: Dynamic Programming
24.Find minimum cost path from s to t in multistage graph given below
25.Explain dynamic programming solution to 0/1 knapsack problem.
26.Solve the instance of "Travelling sales person problem " to find tour of min-cost
27.Explain reliability design problem with suitable example.
28.Find all pair shortest path for fallowing graph.
Unit 4: Basic Traversal and Search Techniques and Backtracking
30.Define articulation point and biconnected component with suitable example.
Identify articulation points using DFS Spanning Tree in following graph.
31.Find DFS and BFS spanning tree for following graph.
32.For the below graph identify articulation points and biconnected components
and Write a Pseudocode to determine biconnected components
33.How can be a non biconnected graph converted into a biconnected graph
.
34.Write an explain algorithm for Breadth first search & traversal.
35.Write a note on :
a. AND / OR graph
b. Game tree
c. techniques for binary tree traversal
d. Rearrangement
36. Draw and explain permutation tree generated for 4-Queens
problems using backtracking.
37.Discuss Algorithm and conditions of 8 Queens problem.
38.What is backtracking? Explain sum of subset problem and algorithm with
suitable example
.
39.Explain solution to 0/1 knapsack problem using Backtracking method.
40.Explain solution to Hamiltonian cycle problem using Backtracking method.
41.Find out chromatic number of following graph
42.Explain with suitable example the terms- live node, E-node, dead node and
bounding function with respect to backtracking.
43.Define following terms :
a. Criteria function
b. Bounding function
c. Explicit constraint
d. Implicit constraint
e. Solution state
f. Answer state
Unit 5: NP Hard and NP Complete Problems
44.Explain the relationship between P, NP, NP-Complete, NP-Hard problems
with neat diagram.
45.List and explain NP-Hard graph problems.
46.Write a short note on chromatic number decision problems.
47.Write a note on flow shop scheduling.
48.Define and Explain Non-Deterministic algorithms.
49.Define and explain the following terms.
a. Deterministic and NonDeterministic algorithm.
b. Decision and optimization problem.
c. DHC problem.
d. Relationship between NCDP and CDP
Unit 6: Introduction to Parallel Algorithm
50.Write a note on Amdahl's law.
51.List and explain Variants of PRAM.
52.Write an algorithm & Explain Prefix computation problem with suitable
example.
53.Write a note on Deterministic list ranking.
54.Write the difference between sequential computational models & shared
memory models.
55.Explain how MESH computational model works.
56.Write a note on Broadcasting in MESH.
57.Write an algorithm for prefix computation on linear array.
58.Write an algorithm for prefix computation on mesh.
59.Compute the prefix sums on the mesh for the following indexing schemes
row major, snakelike row major, column major and snakelike column
major.
3 4 1 2
5 6 3 4
1 5 8 6
7 9 2 3
60. Explain Hypercube.
61. How three dimensional Butterfly network works?
62. Explain with example embedding of binary tree into hypercube.
63. Write algorithm for prefix computation on binary tree & explain with
suitable example the working of it?
please share mcq
ReplyDeleteare you in shivaji university
ReplyDelete