Sikkim-Manipal University of Health Medical and Technological Sciences (SMUHMTS) 2008 M.C.A Computer S.M.UAssignment s . - Question Paper

MC0056–01
Marks: 60
ALGORITHM AND ALGORITHMIC GRAPH THEORY

ans the following:
1. Describe in brief the algorithm for Planarity Testing. [10]
2. Sort the subsequent array using Quick Sort method: [10]
10, 30, 20, 50, 40, 70, 60, 90, 80
Show all the possible passes.
3. Given a sorted array [10]
11, 22, 33, 44, 55, 66, 77, 88, 99
Locate the elements: 22, 88 and 100
Show the values of high, mid and low at every step.
4. Find the feasible solution for the subsequent knapsack Problem:
N=3, m=20, (p1,p2,p3)=(25,24,15) and (w1,w2,w3)=(18,15,10) [10]
5. What is Dynamic Programming? [10]
6. Write a short note on Graph Coloring issue. [10]
















MC0056 –02
Marks: 60
ALGORITHM and ALGORITHMIC GRAPH THEORY

ans THE FOLLOWING:
1. Explain 8-Queens issue algorithm using backtracking method. [10]
2. Define the subsequent along with an example: [10]
a. Digraph
b. Cycle
c. Bipartite Graph
d. Tree
e. Hamiltonian Path
f. Hamiltonian Circuit
g. Subgraph
h. Bridge
3. Explain the greedy method of Job sequencing with deadlines algorithm. [10]
4. Explain the Max-Min algorithm using Divide and Conquer approach. [10]
5. Explain the basic operations on stack with the help of an example. [10]
6. What are NP Hard and NP Complete issues. [10]

Earning:   Approval pending.