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

Questions asked in this paper

1. Q1 Solve the following (any4)
   • a) the numbers 6, 7,4,5,3 in ascending order using Bubble sorting algorithm,
   • b) Define the terms
   • i) Relation ii) Cycle iii)Boolean product of two matrices
   • c) the recurrence relation with using generating function
   • d) Write a note on Tower of Hanoi
   • e) Let Using Warshall’s algorithm find the transitive closure of R whose matrix is given by
   • f) R as aRbiff a/b then prove that is also poset
   • g) Define the Composite relation Let A={1,2,3}, B={a,b,c}, C={x,y,z}. Let R={(1,b),(2,a),(2,c)} from A to B and from B to Find verify M
   • h) Solve the recurrence relation With a=5,
2. Q2 Solve the following (any 4) a postorder search on the following tree using postorder search algorithm Define i) ordered rooted linked list representation using vertex and graph starting with vertex 20 marks
   • c) Write the Breadth First Search algorithm. Apply it on ee, Use it to delete
   • d) . Write an algorithm on deleting the value in binary search tree
   • e) Build a binary tree for a begin, break, else, end, goto, If, then
   • ii) Give adjacency structure and linked representation for the graph,
   • f) Find the Path matrix for the following graph using Warshall’s algorithm ; Define the term i) Binary tree ii) Complete binary tree iii) Extended binary
   • h) i) Construct a tree of the algebraic expression ((7*3)+(4-(5*3)))+(3-(3 *6))
   • 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 52 State the pigeonhole principle Show that if seven colours are used to paint 60 bicycles, atleast 9 bicycles will be of the same
   • c) the sum and product rule, How many bit string are there of length 8? 00? Also find how many of them ends with two bits
   • d) A family of 4 brothers and 3 sisters are to be seated for ways can they selected i) ifall sisters are seat together,
   • ii) if no two sisters sit together
   • 2) the Binomia
   • m. Use j =0 for Positive in: State and prove it’s state table letters, initial state. accepting state, write
4. Q4 following (any 3) 125}
   • 2) Solv e the non-homogenous recurrence relation
   • 5) Write a note on Binary Operations on the graph Use Shortest-Path algorithm to find shortest path between the vertices of the following graph Define the term Grammar. Write a note on the types of Grammar
   • f) Determine whether the relation R whose diagraph is given is reflexive, symmetic,

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