BSc CS Sem 3 BSc CS Semester 3 (2014 2015) 2015 Comp I Question Paper - Mumbai University | munotes

Questions asked in this paper

1. Q1 Solve the following (any4) {20]
   • a) Prove that any two equivalence classes are either equal or disjoint
   • b) Solve the recurrence relation , with generating function f “Arrange the numbers 6,7,4,5,3 in ascending order using Bubble sorting algorithm
   • d) Solve the recurrence relation with ao=5,
   • e) Write a note on Tower of Hanoi
   • f) LetarelationR defined on as aRb iff a/b then prove that /) is also poset
   • g) Define trasitive closure Let A={1,2,3,4}.Find the transitive closure of R whose matrix is given by
   • h) Define the Composite relation Let A={1,2,3}, B={a,b,c}, C={x,y,z}. Let from A to B and from B to C. Find SoR,M sor verify M
2. Q2 Solve the following (any 4) a tree on 5 vertices with a suitable example Perform a preorder ,postorder and Inorder on the following tree
   • b) Define i) ordered rooted tree
   • ii) linked list representation using vertex and edge file
   • c) Write the Breadth First Search algorithm. Apply it on the following graph starting
   • d) Write an algorithm on deleting the value in binary seach tree. Use it to delete V=72
   • i)Build a binary tree for a list : connected graph and regular graph with an example Find the Path matrix for the following graph using Warshall’s algorithm
   • g) Define the term i) Binary tree 11) Complete binary tree ii) Extended binary tree
   • h) i)Construct a tree of the algebraic expression (X+(Y-(X+Y))) x ((3+(2x7))x4)
   • ii)Give the adjacency list and adjacency matrix of complete graph of 5 vertices
3. Q3 Solve the following (any 4) 20 marks
   • a) State the Inclusion — exclusion principle How many positive integers not exceeding 100 are divisible by 2,3 or 5?
   • b) Pigeonhole principle if seven colours are used to paint 60 cles , atleast 9 bicycles will be of the
   • c) State the sum and product rule How many bit string are g there of length 8? Also find how many of them ends with two A family of 4 brothers i ‘
   • d) 3 Sisters are to be seated for photograph in one row. In how Selected all sisters are seat together
   • 1) if no two sisters sit together
   • e) State the Binomial théorem Use it to prove for non-negative integer
   • ii) for Positive integer n,
   • f) State and prove Vandermonde’s identity,
   • g) State and prove Pascal’s identity,
   • h) Consider tollowing FSA. Find States, input letters, initial State, accepting state, f(s;,b), write it’s state table
4. Q4 Solve the following (any 3)
   • a) Solve the non-homogenous recurrence relaticn a,=
   • b) Define the term i)Lattice Lattice 111) Bounded Lattice
   • c) Write a note on Binary-operations on the graph Use Shortest-Path algorithm to find shortest path between the vertices of the followin:
   • e) Define the term Grammer. Write a note on the types of Grammer,
   • f) Define a) Turning Machine b) finite state automata c)types of languages

Read from the scan above, so a character or two may differ. The scan is the original.