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

Questions asked in this paper

1. Q1 Solve the rrange the numbers 6, ;
   • b) Define the terms mre in ascending order using Bubble sorting algorith
   • iv) Symmetric closure product of two matrices
   • c) Solve the recur simple path ) rite a note on Tower of Hanoj with using generating function given by gorithm find the transitive closure of R whose matrix Define the Composite s aRbiff a/b then prove that (Z ,/) is also poset “Solve the m B to Find SoR,Msor-Also verify M
   • 2) Solve the following (any
   • a) Perform a postorder search on the following tree using postorder search algorithm Define. i) ordered rooted tree Write the Breadth First Search algorithm. ‘Apply it on the following graph starting with Write an algorithm on deleting the value binary
   • i) Build a binary tree for a list- begin, break, else, end, Give adjacency structure and linked representation the Path matrix for the followirig graph using Warshall’s algorithm the term i) Binary ii) Complete binary tree Extended binary
   • i) Construct a tree of the algebraic expression ((7*3)+(4-(5*3)))+(3-(3*6)) Give the adjacency list and adjacency matrix of complete graph Solve the following (any 4) State the Inclusion — exclusion principle How many positive integers not exceeding 100 are divisible. by 2,3 State the pigeonhole Show that colours are used to paint 60 bicycles, atleast 9 bicycles will be of the same
   • c) State the sum and product How many bit string are there of length 8? Also find how many of them ends With two
   • d) A family of 4 brothers and 3 sisters are to, be seated for photograph in one In-how many ways can they selected i) ifall sisters are theorem, Use it to prove for positive integer n
   • f) State and prove
   • g) State and prove ident: ntity
   • h) Consider following FSA it’s state table states, input letters, initial state, accepting state, f(s,,b), write
2. Q4 Solve the following (any 3) 415]
   • a) Solve the non-homogenous recurrence relation a,=
   • b) -Write a note on Binary Operations on the
   • c) Use Shortest-P ath algor ithm to find shortest path between of the following graph
   • d) Define the term Grammar. Write a noté on ‘the types of Grammar
   • e) Define a) Turning Machine b) finite state automata types of languages: Determi ne whether the relation R whose diagraph is given is reflexive, irreflexive, symmetric,

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