Sardar Patel University 2008 B.E Computer Science CP201-Introduction to Theoretical %28Internal Test%29 - Question Paper

ADIT/BVM/GCET
A.Y. 2007-08, Semester II
INTERNAL exam
CP201-Introduction to Theoretical Computer Science

Date: 11/03/2008 Time: 12:00 P.M to 1:00 P.M Max Marks: 20

Note: Write ans to the ques. point to point.
Q.1 Attempt following:
[A] 1) Show that
12 + 32 +52 + …+(2n-1)2 = n (2n-1) (2n+1) / three
[2]
2) Among 100 students, 32 study mathematics, 20 study physics, 45 study biology, 15 study mathematics and biology, seven study mathematics and physics, 10 study physics and biology, and 30 do not study any of the 3 subjects.
(a) Find the number of students studying all 3 subjects.
(b) Find the number of students studying exactly 1 of the 3 subjects. [2]
3) Construct the truth table for the subsequent statements:
(a) (a ? a) ? (a ? a)
(b) a ?? (e V a) [1]

[B] 1) In the subsequent let {A, B, C, S} be the set of nonterminals, with S being the starting symbol. Let {a, b, c} be the set of terminals. define the language specified by set of productions verbally as well as in set-theoretic notations. (Any one)

(a) {S?AB, A?aA, A?a, B?Bb, B?b}
(b) {S?aA, A?bA, A?bC, C?cC, C?c} [2]
2) Give the grammar that specifies the subsequent language. (Any one)
(a) L={ai bj cq | i+j=q, i>=1, j>=1}
(b) L={a2i c b2j+1 | i>=1, j>=1} [2]
3) Consider the grammar in which N={signed_interger,sign, integer,digit} and T={+, -, 0, 1} with signed_integer being the starting symbol. Let the set of productions be:
signed_interger ? sign integer
sign ? +
sign ? -
integer ? digit integer
integer ? digit
digit ? 0
digit ? 1
Show the derivation of the string -010 in the language.
[1]
Q-2 Attempt following:
[A] 1) Consider the experiment of tossing a fair coin until 2 heads or 2 tails appears in succession.
(a) Describe the sample space.
(b) What is the probability that the experiment ends before the 6th toss?
[1]
2)



2) In how many ways can the letters in the English alphabet be organizes so that there are exactly 7 letters ranging from the letters a and b?
OR
In how many ways can the letters in the word MISSISSIPPI be arranged? In how many ways can they organizes if the 2 P’s must be separated?
[2]
3)




3) There are 50 students in every of the junior and the senior classes. every class has 25 male and 25 female students. In how many ways can 8 representatives be opted so that there are 4 female and 3 juniors?
OR
A farmer buys 3 cows, 2 pigs, and 4 hens from a man who has 6 cows, 5 pigs and 8 hens. How many options does the farmer have? [2]

[B] 1) Let R be a binary relation on the set of all positive integers such that R= {(a, b) | a - b is an odd positive integer}
Is R reflexive? Symmetric? Antisymmetric? Transitive? An equivalence relation? A partial ordering relation?
[2]
2) The procedures of scheduling a set of tasks according to the rule of never leaving a processor idle intentionally. obtain total elapsed time for set of tasks T = {T1, T2, …, T9} to be executed on 3 processors. A relationship ranging from the tasks is provided in subsequent figure and execution time for every task is {(T1, 2), (T2, 3), (T3, 4), (T4, 2), (T5, 3), (T6, 2), (T7, 3), (T8, 2),(T9,4)} also the priorities is assign in increasing order to the tasks T1, T2, T3 ,T4, T5 ,T6, T7, T8, T9. Construct the corresponding schedule. Schedule a task that has the highest priority among all executable tasks at any time instant on a processor that is free at that time instant.

Earning:   Approval pending.