Sikkim-Manipal University of Health Medical and Technological Sciences (SMUHMTS) 2009 B.C.A Computer Application BC0052 Theory of computer science Assignment - Question Paper

August 2009

Bachelor of Computer Application (BCA) Semester 5

BC0052 Theory of computer science 4 Credits
(Book ID: B0972)

 

Each Question Carries 10 Marks 10 X 6 = 60 Marks

 

 

1. For any set s of strings prove that .

 

2. What do you mean by equivalence relation. Give atleast two examples of equivalence relation.

 

3. Prove by Mathematical Induction that

 

4. Prove that a graph G is connected if and only if it has a spanning tree.

 

5. Construct a grammer for the language .

 

6. Write short notes on Deterministic Finite Automata.

 

 

 

 

 

 

August 2009

Bachelor of Computer Application (BCA) Semester 5

BC0052 Theory of computer science 4 Credits
(Book ID: B0972)

Each Question Carries 10 Marks 10 X 6 = 60 Marks

 

 

Book ID: B0972

1. Prove that the relation is an equivalence relation.

 

2. Calculate the g.c.d. (48, 18).

 

3. Prove that if and only if n is a positive integer.

 

4. Using the definition of order show that is O(x²).

 

5. Prove by mathematical induction that

 

6. Let G be a graph such that f(G) k. Use the principle of induction to show that h has a path of length k starting at any given vertex.