MCS-031
1. Discuss some
real world problems, to which the techniques given below are applicable. (12 Marks)
(i) Divide & Conquer
(ii) Dynamic Programming
(iii) Greedy Approach
2. Two
algorithms A1 and A2 run on the same machine. The running
time of A1 is 100 n and running time of A2 is 2n.
For what value of n2, A1 runs faster than A2 ?
If running time of A1 is changed to 100 n30, then what
could be the possible value of n. You can use any spreadsheet software to plot
the graph nVS A1 & A2 running time, to analyse the
results. (5 Marks)
3. Use
Principle of Mathematical induction to show that the polynomial P(X) = X3
– X, is divisible by 6, where X is a non-negative integer. (5 Marks)
4. Verify
the expression n! = 0(nn). (5 Marks)
5. Determine the
complexity of following sorting algorithms
(i) Quick sort
(ii) Merge sort
(iii) Bubble sort
(iv) Heap sort
Show all steps, performed to determine the complexity, with
suitable example for each.(16 Marks)
6. Find the
product of two numbers X1 = 732912 and X2 = 1026732 by
using Karatsuba’s Method.
7. Write Strassen’s Algorithm ? What are the limitation
of Strassen’s Algorithim. Apply Strassen’s Algorithm to multiply two matrices
A1 & A2 given below A1 = and A2 = (10 Marks)
8. Perform
following tasks
(a) Write Kleene closure of {aa, b}
(b) Find regular expression for language {Ù, a, abb, abbbb, ….} (5 Marks)
9. Write short
note on NP complete and NP Hard problems, give suitable example for each. (5 Marks)
10. Discuss the following with
suitable example
(i)
Halting problem,
(ii)
Turing machine,
(iii)
Push down automata.
*****************************************************************
Note: Answer with Dotcom Books
www.dotcombooks4u.com
(Last 5 year solved question
paper with Assignment solutions)
****************************************************************
No comments:
Post a Comment