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.
     
Q1:                        

• Explain in what respect, the process of ‘analysing a problem’ and ‘analysing an algorithm’ are essential for developing computer-based solutions of problems.                        (5 marks)

• Show that an = O (bn), where a and b are some constant natural numbers.     (5 marks)

• Solve the following inhomogeneous recurrence.

G (m) – 7 G(m – 1) + 12 G (m – 2) = 9.                     (5 marks)

• Suggest some method of computing x1218792, where x is a natural number, and the method does not use more than 2 log2(1218792) number of product operations.                 (5 marks)

Q2:                        

• Sort the following list in increasing order of numbers

9, 94, 45, 47, 28,     98, 65, 42, 78, 4, 11, 88, 6
using each of the following methods,                          (12 marks)

• Merge Sort
• Quick Sort
• Insertion Sort
• Selection Sort
• Heap Sort

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

• For the graph given below, use DFS to visit various vertices taking C as starting vertex.                                                                                   (8 marks)

Q3:                        

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 V1, V2, ………, Vk. Further, if (u, v) is an edge in E, then, for i with 1 £ i < k, the edge u belongs to Vi and the vertex v belongs to Vi+1. The number of vertices in each of the first and last sets viz., V1 and Vk is one. Let the node in the first set V1 be called s and the node in the last set Vk be called t. Further, let c(i, j) be 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)

Q4:
(a)       Job Sequencing with Deadlines using Greedy Method, find an optimal solution to the problem of job
Sequencing with Deadlines, where n = 4, (p1, p2, p3, p4) = (100, 10, 5, 27) and 
(d1, d2, d3, d4) = (2, 1, 2, 1).                                   (10 marks)

(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)

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.

Q1:
Explain the concept of generalization and inheritance with example.                              (10 Marks)        

Q2:
Discuss the advantages of object-oriented approach over structured approach of problem solving.                      
                     (10 Marks)

Q3:
What is concurrency? Explain the process of concurrency identification in respect to OOM.
                                                                                                                                                        (10 Marks)

Q4:  
What is object modeling? Explain different UML notations used in object modeling.    (10 Marks)

 Q5:
What is state diagram? Draw a state diagram for ATM system.                                     (10 Marks)

 Q6:
What is one-way association? Explain how it is different than two-way association.    (10 Marks)

Q7:
Explain how generalizations are mapped into a database table with example.                (10 Marks)

Q8:
Explain with example how integrity constraints are applied in object-oriented model.   (10 Marks)

There are ten 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.

Q1:
a)             Consider the following graph:

1. Is the graph Eulerian?
2. Is the graph Hamiltonian?

Give reasons for your answer.                                            (4 Marks)                                            
b)            A post office has stamps only in denominations of   Rs. 1, Rs. 2. and Rs.5.
i)              Find the generating function for the number of ways in which you can pay n rupees.
ii)             If the post office has only 18 stamps of Rs.1, 12 stamps of Rs. 5 and 15 stamps of Rs. 2, find the number of ways in which you can pay a postage of Rs. n.                                   (4 Marks)
Q2:
a)         Using an appropriate substitution, solve the  recurrence
                                                                                                (4 Marks)
b)        Give an example of a non-Hamiltonian graph G on 13 vertices with  for all
                                                                                                                                                         (4 Marks)

Q3:
a)         Define the edge chromatic number of a graph. Give examples of graphs Gand G2 for
which and where   denotes the edge chromatic number of a graph. G.                             (4 Marks)
b)        Find the general solution to the homogeneous part and a particular solution to the recurrence.
                                                              (4 Marks)
Q4:
a)         Prove that a vertex V in a graph is a cut vertex if and only if there exists distinct vertices x, y in G such that V lies on every path joining x and y.                                                              (4 Marks)

b)        Let be a sequence satisfying the recurrence
       
                        Find the generating function of an.                                                                                               (4 Marks)

Q5:
a)         Solve the recurrence
        ,                                           (7 Marks)

b)        In the graph given in the next page, let
         and Y=
Check whether there is a complete matching of X into Y using the necessary and sufficient condition for a complete matching.              (3 Marks)
 

Q6:
a)         A palindrome is a word that reads the same whether read from right to left or from the left to right, the word ROTOR, for example.
Let be the number of words of length n, not necessarily meaningful, which are palindromes. We consider a single letter as a palindrome.

1. What are  and?
2. Set up a recurrence for .
3. Check that

               
                is the solution to the recurrence.                                                                                                  (4 Marks)

            b)        Show that a tree has at least 2 vertices of degree 1.                                                                 (4 Marks)
7)         Use generating function to solve the recurrence relation
                                      (7 Marks)
            where

Q8:
a)         Find a minimal colouring for the following graph.                                                                                (5 Marks)

b)        Use an appropriate substitution to solve the recurrence
                                      (5 Marks)

Q9:
a)         Give an example of a graph, which has a unique spanning tree up to isomorphism. Is it true that any graph has a unique spanning tree up to isomorphism?                                                                           (3 Marks)

1. Check whether is a solution to the recurrence                      

            Is the recurrence homogeneous? Give reasons for your answer.                                                        (3 Marks)
Q10:
a)         Consider the following weighted complete Hamiltonian graph. Start with the Hamiltonian cycle             {a,b,c,d,e} and carry out zthe reduction step twice to get a cycle of lesser weight.    (3 Marks)

1. It is true that  always. Give reasons for your answer.                    (2 Marks)

Is there tree with degree sequence {1,1,2,4}? Give reasons for your answer.        

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.

                                                      
Q1: Consider developing a system for Inventory Management for a super market that has a number of branches all over a city. Perform the following activities:

1. Suggest the most appropriate Software Engineering model for developing this project   

       with appropriate justification.                                                                   (4 Marks)

(b)   Derive the requirement specifications.                                                                         (6 Marks)

(c)  List all the functional and non-functional requirements.                                           (6 Marks)

1. Produce a project-scheduling chart using Gantt chart technique.                            (4 marks)

1. Give the scope of the solution.                                                                            (4 marks)  

1. Suggest the tools/platform, hardware and software requirements.                         (4 Marks)

1. Suggest the networking architecture.                                                                           (4 Marks)  

1. Suggest the security mechanisms to be implemented.                                          (4 Marks)

1. Develop a test plan for the system. You can make necessary assumptions and specify  

       them.                                                                                 (6 Marks)

(d) Write the risk management plan for the system.                                                     (6 Marks)

(e)   Estimate the efforts of software project. Make necessary assumptions.                (6 Marks)

(f)   Suppose it was revealed that the poor knowledge of the tool is responsible for the problems that are being encountered for timely completion of the project. What type of remedies do you suggest for such type of problem? Justify your answer.             (6 Marks)

1. Suppose there exists some old systems and wants to replace it, suggest the changes with respect to the software and hardware requirements.                                              (6 Marks)
2. Describe the user-training plan, which can be followed.                                       (8 Marks)

(i)    Develop a design review plan for the system. Also, list the deficiencies, if any, in the SRS for the same.                                                                                                                 (6 Marks)