IGNOU MCA -mcs-031 solved assignments 2012 -2013

Course Code : MCS-031

Course Code : MCS-031
Course Title : Design and Analysis of Algorithms
Assignment Number : MCA (3)/031/Assign/2012
Maximum Marks : 100
Weightage : 25%
Last Dates for Submission : 15
th
October, 2012 (For July 2012 Session)
15
th
April, 2013 (For January 2013 Session)
There are ten questions in this assignment, which carries 80 marks. Rest 20 marks
are for viva-voce. Answer all the questions. You may use illustration and diagrams
to enhance the explanations. Please go through the guidelines regarding assignments
given in the MCA Programme Guide for the format of presentation. The examples,
whenever asked to be given, should be different from those that are discussed in the
course material.

Question1: Using Insertion Sort, sort the following sequence in increasing  (10 marks)
order and do the analysis of the algorithm:  35, 37, 18, 15, 40, 12

Question 2: Write a pseudocode for divide and conquer algorithm for
finding the position of an array of n numbers and estimate the
number of key comparisons made by your algorithm.      (10 marks)

Question 3: Apply quicksort to sort the following list: Q U I C K S O R T (10 marks)
         in alphabetical order. Find the element whose position is
unchanged in the sorted list.

Question 4: Write Strassen’s matrix multiplications algorithm for obtaining
the product of two matrices.   (10 marks)

Question 5: (i) Define DFS. Explain briefly how it differs from BFS.  (10 marks)
        (ii) Write pseudocode for DFS and calculate its time complexity

Question 6: Apply Kruskal’s algorithm to find minimal spanning tree with
an example.  (10 marks)

Question7: Arrange the following growth rates in increasing order:
O (3
n
), O (n
2
), O (1), O (n log n)    (4 marks)

Question 8: Using Principle of Mathematical Induction, prove that the
sum 2
0
+ 2
1
+…+ 2
n
  is 2
n +1
– 1 for all n  1.    (6 marks)

Question 9: Define Knapsack Problem and cite one instance of the problem. (5 marks)

Question 10: Explain the essential idea of Dynamic Programming. How
does Dynamic Programming differ from Divide and conquer
approach for solving problems? (5 marks)

 IGNOU Coaching for BCA, MCA, MBA in Jaipur  

BCA Coaching in Jaipur | MCA Coaching in Jaipur

IGNOU JAIPUR

Regional Director,
IGNOU Regional Centre,
70/79,
Sector - 7,
Patel Marg,
Mansarovar
Rajasthan - 302020
India
Ph :+91-0141-2785763 / 2785750
Fax :+91-0141-2784043