# 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**

**)**

**Assignment
Set 1 (60 Marks)**

** **

** **

**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**

**)**

**Assignment
Set 2 (60 Marks)**

** **

**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^{2}).

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.

Earning: Approval pending. |