BC0052 – THEORY OF COMPUTER SCIENCE

Dear students get fully solved assignments

Send your semester & Specialization name to our mail id :

  “ help.mbaassignments@gmail.com ”

or

Call us at : 08263069601

FALL  2014, ASSIGNMENT

PRIGRAM	BCA(REVISED 2007)
SEMESTER	5TH
SUBJECT CODE & NAME	BC0052 – THEORY OF COMPUTER SCIENCE
CREDIT	4
BK ID	B0972
MAX. MARKS	60

Note: Answer all questions. Kindly note that answers for 10 marks questions should be approximately of 400 words. Each question is followed by evaluation scheme.

                                                                                                                                                           

1. What are the five ways used to describe a set? Describe the set containing all the nonnegative integers less than or equal to 4.

Answer: A set is a collection of objects, things or symbols which areclearly defined.
The individual objects in a set are called the members orelements of the set.
A set must be properly defined so that we can find out whether an object is a member of the set.

There are two ways of describing, or specifying the members of, a set. One way is by intensional definition, using a rule or semantic description:

A is the set whose members are the first four positive integers.

B is the set of colors of the French flag.

2. What is Recursion Theorem? How do you define n! recursively and compute 5! recursively.

Answer: The Recursion Theorem simply expresses the fact that definitions by recursion are mathematically valid, in other words, that we are indeed able correctly and successfully to define functions by recursion. Mathematicians implicitly use this fact whenever they define a function by recursion.

A more general version of the Recursion Theorem would allow the function f to use the argument n as well as F(n). A still more general version of the Recursion Theorem, called course-of-values recursion, allows f to use as an argument the entire restriction of the function F∣n to earlier values. (These more complex versions of the Recursion theorem can be derived solely from the single-value theorem you have stated, by using a function f that takes a

3. State and prove Pigeonhole Principle.

Answer: In mathematics and computer science, the pigeonhole principle states that if n items are put into m pigeonholes with n > m, then at least one pigeonhole must contain more than one item. This theorem is exemplified in real-life by truisms like "there must be at least two left gloves or two right gloves in a group of three gloves". It is an example of a counting argument, and despite seeming intuitive it can be used to demonstrate possibly unexpected results.

The first formalization of the idea is believed to have been made by Johann Dirichlet in 1834 under the name Schubfachprinzip ("drawer principle" or "shelf principle"). For this reason it is also commonly called Dirichlet's box principle or Dirichlet's drawer principle. In Russian and some other languages, it is contracted to simply "Dirichlet

4. Prove that in Graph the number of vertices of odd degrees is always even.

Answer: 1. Each edge (including loops) contributes 2 to the vertex order total.

2. This means the vertex order total must be even because it increments by 2 for every edge.

3. For the vertex order total to be even, the number of vertices with odd orders must be even because:

(a) odd number + odd number = even number

(b) odd number + even number = odd number

(c) even number + even number = even number

5. What is Deterministic finite machine? What are the various components of DFA? Illustrate it using the pictorial representation of DFA.

Answer: In automata theory, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite state machine—is a finite state machine that accepts/rejects finite strings of symbols and only produces a unique computation (or run) of the automaton for each input string. 'Deterministic' refers to the uniqueness of the computation.

In automata theory (a branch of computer science), DFA minimization is the task of transforming a given deterministic finite automaton (DFA) into an equivalent DFA that has a minimum number of states. Here, two DFAs are called equivalent if they

Q.6 Prove that “A tree G with n vertices has (n–1) edges”

Answer:- We prove this theorem by induction on the number vertices n.

Basic step: If n = 1, then G contains only one vertex and no edge. So the number of edges in

G is n –1 = 1 – 1 = 0.

Induction hypothesis: The statement is true for all trees with less than ‘n’ vertices. Induction step: Now

let us consider a tree with ‘n’ vertices. Let ‘ek ’ be any edge in T whose end vertices are vi and v j.

Since T is a tree, by there is no other path between vI and v j. So by removing ek from T , we get a disconnected

graph. Furthermore, T - ek consists of exactly

Dear students get fully solved assignments

Send your semester & Specialization name to our mail id :

  “ help.mbaassignments@gmail.com ”

or

Call us at : 08263069601