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

Questions asked in this paper

1. Q1 Solve the following (any 4)
   • a) Define transitive closure.Let Find transitive closure by algorithm for R whose matrix is given by
   • b) Write a note on Tower of Hanoi
   • c) Define Hasse diagram. Draw Hasse diagram of poset relation Solve the recurrence relation dn= with
   • e) Determine whether the relation an equivalence on Where Solve the non-homogenous recurrence relation a,= Let (A, R) be a Poset then show
   • h) Define the terms i) Relation ii) Least upper iti) eyele 7
2. Q2 Solve the following (any 4) 20 marks
   • a) Explain Binary operations on graph with an example
   • b) Define the term i) Binary tree ii) Complete binary. tree iii) Extended binary tree
   • c) Construct a tree of the algebraic expression ((2*X) + (3-(4*X))) + (X-(3*11)). Also find it’s value
   • ii)In an Urn contains 15 balls out of which 8 are white and 7 are black. In how many ways can 5 balls be selected so that atleast 2 are white
   • e) Use Shortest-Path algorithm shortest path between the vertices of it the following graph Write the Breadth First Search algorithm. Apply Perform a preorder search on the following tree using preorder search algorithin,
   • h) Find the Path matrix for the following graph using Warshall’s
3. Q3 Solve the following (any 4) =
   • a) Write a note on types
   • b) the term Regular expression and regular grammer
   • c) Consider the FSA defined by following state table find i) states letters iii)initial state
   • iv)accepting state diagram
   • d) Let M be the FSM with following state table Find i) input set I, state S, output
   • ii)draw the state diagram
   • iii)suppose u=aababaabbab is an input word find the sequence v and output
   • e)- Let G bea grammer whrer T={a,b,c} and N={S,A) with starting symbol Let P={S—aSb, aS—Aa, Aab—c}. Find L(G) Consider the following finite M Determine which of the following words are accepted by M
   • g) Explain finite. state
   • h) Write a note on Universal turing macnine
4. Q4 Solve the following (any 3)
   • a) Define the Composite relation Let A={1.2,3}, B={a,b,c}, C={x,y,z}. Let from A to Bang from B to C. Find verify M
   • b) Solve the recurrence relation , with ,using generating function, Write a note on Unary operation on the graph
   • d) Write an algorithm on searching the value in binary search tree. Use it to search
   • e) Define the terms i) Grammer ii) Turing Machine
   • f) Write a note on finite state machine

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