MCS-031 : Design and Analysis of Algorithms

Assignment Code : MCA(3)/031/Assign/09

Maximum Marks : 100

Weightage : 25%

Last Dates for Submission : 15^th April, 2009 (For January Session)

15^th October, 2009 (For July Session)

There are four questions in this assignment, which carries 80 marks. Rest 20 marks are for viva-voce. Answer all the questions. You may use illustrations 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.

Question 1:

Sort the following list of numbers in the descending order,

187, 62, 155, 343, 184, 958, 365, 427, 78, 94, 121, 388

using each of the following methods:

(i) Insertion Sort

(ii) Selection Sort

(iii) Heap Sort

(iv) Merge Sort

(v) Quick Sort

Further, count the number of operations, by each sorting method.

(20 marks)

Question 2:

A directed Hamiltonian cycle DHC in a directed graph G = (V, E) is a directed cycle of length n =÷V÷, where ÷V÷ is the number of vertices in G. So, the cycle goes through every vertex exactly once and then returns to the starting vertex. The DHC problem is to determine if a given directed graph G has a directed Hamiltonian cycle. Show that DHC is NP-Hard.

(20 marks)

Question 3:

Multistage Graphs Problem:

A multistage graph G = (V, E) is a directed graph in which the vertices are partitioned in k ³ 2 disjoint sets say V₁, V₂, ………, V_k. Further, if (u, v) is an edge in E, then, for i with 1 £ i <

Read Full Post HERE

Download Attached PDF

• Element of Animal Husbandry And Poultry (1)
  (46 downloads)