DOC

# MASTER IN COMPUTER APPLICATIONS

By Beatrice Wagner,2014-08-29 05:42
10 views 0
MASTER IN COMPUTER APPLICATIONS

MASTER OF COMPUTER

APPLICATIONS

(MCA)

rd(3 SEMESTER)

ASSIGNMENTS

2009

(MCS-031, MCS-032, MCS-033, MCS-034, MCS-035, MCSL-036)

SCHOOL OF COMPUTER AND INFORMATION SCIENCES INDIRA GANDHI NATIONAL OPEN UNIVERSITY

MAIDAN GARHI, NEW DELHI 110068

CONTENTS

Course Code Assignment No. Maximum Page No.

Marks

MCS-031 MCA(3)/031/Assign/09 100 3 MCS-032 MCA(3)/032/Assign/09 100 5 MCS-033 MCA(3)/033/Assign/09 100 6 MCS-034 MCA(3)/034/Assign/09 100 10 MCS-035 MCA(3)/035/Assign/09 100 11 MCSL-036 MCA(3)/036/Assign/09 100 15

Important Notes Important Notes

1. Viva-voce worth 20 Marks is compulsory for each course.

1. Viva-voce worth 20 Marks is compulsory for each course. 2. Please follow the guidelines given in the MCA Programme Guide for solving, presentation

2. Please follow the guidelines given in the MCA Programme Guide for solving, presentation format and submission of the assignment.

format and submission of the assignments.

2

Course Code : MCS-031

Course Title : Design and Analysis of Algorithms

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

Maximum Marks : 100

Weightage : 25% th Last Dates for Submission : 15 April,2009 (For January Session) th 15 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. Further, if (u, v) is an edge in E, then, for i with 1 i < k, the edge u belongs to V 12kiand the vertex v belongs to V. The number of vertices in each of the first and last sets viz., V and V is i+11kone. Let the node in the first set V be called s and the node in the last set V be called t. Further, let c(i, j) 1kbe the cost of traversing from vertex i to vertex j.

The Multistage Graph Problem is to find a minimum cost path from the start node s to the terminal node t.

Using Dynamic Programming, suggest a solution to Multi-stage Graph Problem.

(20 marks)

3

Question 4:

(a) Job Sequencing with Deadlines using Greedy Method, find an optimal solution to the problem of

, p, p, p) = (10, 1, 15, 7) and (d, job sequencing with Deadlines, where n = 4, (p12341

d d, d) = (1, 2, 1, 2). (10 marks) 234

(b) Let G = (V, E) be a given graph and S be a subset of V. Then, S is said to be a node cover of the

graph G if each of the edges in E is incident to at least one vertex in S. The size of the cover is the

number of vertices in the set S. The Node Cover Problem is to determine whether a given graph G

has a Node cover of size k, where k is a pre-assigned natural number.

(10 marks)

4

Course Code : MCS-032

Course Title : Object Oriented Analysis and Design

Assignment Number : MCA(3)/032/Assign/09

Maximum Marks : 100

Weightage : 25% th Last Dates for Submission : 15 April,2009 (For January Session) th 15 October, 2009 (For July Session)

There are eight questions in this assignment which carries 80 marks. Rest 20 marks are for viva-voce. Answer all the questions. Please go through the guidelines regarding assignments given in the Program Guide for the format of presentation.

Question 1:

Question 2:

Explain characteristics of an Object Oriented Systems. (10 Marks)

Question 3:

What is Inheritances? Explain with an example, how Inheritance is shown in class diagram. (10 Marks)

Question 4:

What is an object? Critically explain “Object Identification is one of the major challenges in OOAD”.

(10 Marks)

Question 5:

What is a state diagram? Explain the characteristics of the system that can be identified by

examination of the state diagram of that System. (10 Marks)

Question 6 :

Explain different UML Diagrams used in OOAD. (10 Marks)

Question 7:

Explain object model and dynamic model with example. (10 Marks)

Question 8:

What is Unidirectional Implementation? Explain how it is different than Bi-directional Implementation with an example. (10 Marks)

5

Course Code : MCS-033

Course Title : Advanced Discrete Mathematics

Assignment Number : MCA(3)/033/Assign/09

Maximum Marks : 100

Weightage : 25% th Last Dates for Submission : 15 April,2009 (For January Session) th 15 October, 2009 (For July Session)

There are eight questions in this assignment. Answer all questions. 20 Marks are for viva-voce. You may use illustrations and diagrams to enhance explanations. Please go through the guidelines regarding assignments given in the Programme Guide for the format of presentation.

Question 1:

Which of the following statements are true and which are false? Give reasons for your answer.

i) Neither order nor degree is defined for the recurrence relation a = . aa...an12n1

ii) The generating function of the recurrence relation a = 3a 2a, where a = 1, a1 = 1, n+2n+1n0xeis . (x1)(x2)？？

-2iii) The generating function of the sequence {1, 2, 3, 4, …, n …} is (1–z).

iv) Any graph is isomorphic to its complement.

v) If (G) = 3, G has a subgraph isomorphic to K. (10 Marks) 3

Question 2:

i) Draw the complement of the graph in Figure 2.

A a

F BE

D C

Figure 2

ii) Show that each of the graphs in Figure.3 is isomorphic to one of the subgraph of the graph in

Figure 2.

6

BEE

CDCD CB

Figure 3

For example, you can show that the graph in Figure 4. Is isomorphic to a subgraph of the graph in Figure 2. by producing the subgraph H with V (H) =

{f, b, d, c}, E (H) = {(f,b), (b, c), (c, d), (d, f)}

AB

CD

Figure 4

and the isomorphism g (f) = a, g (b) = B, g(c) = D, g (d) = C.

b) Is it possible to draw a 6 regular graph on 11 vertices? If yes, draw such a graph. If no, give

Question 3:

(a) Raghu goes to a grocery shop and purchases grocery for Rs. 23. He has 3 five rupee coins, 4 two

rupee coins and 6 one rupee coins. In how many ways can he pay the shop keeper? Find a

solution using generating functions. (6 Marks)

(b) Find the general form of the solution to the linear homogeneous recurrence relation with constant

coefficients for which the characteristic roots are 1 with multiplicity 1, 2 with multiplicity 2 and

2 with multiplicity 3. The relation also has a non-homogenous part which is a linear combination nnof n2 and (2). (4 Marks)

Question 4:

(a) How can a power series be associated with the problem in which we have to find the number of

selections of fruits if we have Rs.50 with us and it is given that an Apple costs Rs. 5, a Banana

Rs.2 and a Coconut Rs.3. (4 marks)

(b) (i) Use Lemma 1 to find the generating function A(z) (say) for the

sequence in arithmetic progression {a, a +d, a+ 2d,…}.

(ii) How many integer solutions are there to a1+a2+a3+a4+a5 = 28 with ak > k for each k, 1?

(6 marks)

7

Question 5:

a) Solve the recurrence relation

n(n1)2 = b + n + (4 Marks) bnn 12

b) Consider the number of subsets of {1, 2, 3, …, n} which do not contain two consecutive integers.

Denote this number by a. n

i) What are the values of a, a, a and a? 1234

ii) Derive a recurrence relation of a and solve it. (6 Marks) n

Question 6:

Prove that

(a) Let G be a simple graph on p vertices, p ? 3, satisfying the condition that d(u)+ d(v) ? p for any

two non-adjacent vertices u and v in G. Then G is Hamiltonian.

(b) A connected graph G with two or more vertices is edge traceable if and only if it has exactly two

vertices of odd degree. (10 marks)

Question 7:

a) Check whether the graph in Figure 5 is Eulerian. b) Check whether the graph in Figure 6 is Hamiltonian

aa

bfg eb

gfhce

Cdd

Figure 5 Figure 6 c) Consider the following weighted complete graph.

8

V1

51 23

36 5 vV25

30 15

19 78 30

v3v442

Figure 7

Start with the Hamiltonian cycle {v, v, v, v, v, v}. Apply the 1-exchange algorithm get a Hamiltonian 123451cycle of lesser weight. (10 Marks)

Question 8:

a) A palindrome is a word that reads the same whether read from right to left or from the left to right,

athe word ROTOR, for example. Let be the number of words of length n, not necessarily n

meaningful, which are palindromes. We consider a single letter as a palindrome.

i) What are a anda? 12

aii) Set up a recurrence for . n

iii) Check that

)??n126126??n??26(1) ;； a~?n??22??((?

is the solution to the recurrence. (6 Marks)

b) Show that a tree has at least 2 vertices of degree 1. (4 Marks)

9

Course Code : MCS-034

Course Title : Software Engineering

Assignment Number : MCA(3)/034/Assign/09

Maximum Marks : 100

Weightage : 25% th Last Dates for Submission : 30 April,2009 (For January Session) st 31 October, 2009 (For July Session)

This assignment has only one question for 80 marks. 20 marks are for viva voce. You may use illustrations and diagrams to enhance the explanations. Please go through the guidelines regarding assignments given in the Programme Guide for the format of presentation.

Question 1:

Suppose that you need to develop a Pay Roll Processing System for an organization whose employee strength is 1000. Every employee gets pay which is computed based on their designation, experience and qualifications.

Now, perform the following activities for the Pay Roll Processing System. Make assumptions, wherever necessary.

(a) Which SDLC model will you choose? Justify your answer. (10 marks) (b) List the functional and non-functional requirements. (6 marks)

(c) Propose a schedule for the project completion. Draw Gantt and Pert charts. (16 marks) (d) Estimate cost of the project. (16 marks)

(e) Develop complete SRS. (16 marks)

(f) Develop test plan document. (16 marks)

10

Report this document

For any questions or suggestions please email
cust-service@docsford.com