My Profile
Active Members
TodayLast 7 Days
more...
Awards & Gifts
Online Exams
Fresher Jobs
Our fresher job section is exclusively for fresh graduates! Find jobs for freshers in major Indian
cities including Bangalore, Chennai, Hyderabad, Pune or Kochi
Resources
Find educational articles, blogs, discussion threads and other resources.
Colleges
Find details about any college in India or search for courses.
|
Download Model question papers & previous years question papers
|
Posted By: nishit Member Level: Silver Posted Date: 28 Aug 2008
|
2008 Sardar Patel University B.E Computer Science CP201-Introduction to Theoretical Computer Science(Internal Test) Question paper
|
|
|
ADIT/BVM/GCET
A.Y. 2007-08, Semester II
INTERNAL EXAMINATION
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 answer to the question point to point.
Q.1 Attempt following:
[A] 1) Show that
12 + 32 +52 + …+(2n-1)2 = n (2n-1) (2n+1) / 3
[2]
2) Among 100 students, 32 study mathematics, 20 study physics, 45 study biology, 15 study mathematics and biology, 7 study mathematics and physics, 10 study physics and biology, and 30 do not study any of the three subjects.
(a) Find the number of students studying all three subjects.
(b) Find the number of students studying exactly one of the three subjects. [2]
3) Construct the truth table for the following statements:
(a) (a ? a) ? (a ? a)
(b) a ?? (e V a) [1]
[B] 1) In the following 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. Describe 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 following 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 two heads or two tails appears in succession.
(a) Describe the sample space.
(b) What is the probability that the experiment ends before the sixth toss?
[1]
2)
2) In how many ways can the letters in the English alphabet be arranged so that there are exactly seven letters between 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 arranged if the two P’s must be separated?
[2]
3)
3) There are 50 students in each of the junior and the senior classes. Each class has 25 male and 25 female students. In how many ways can eight representatives be selected so that there are four female and three juniors?
OR
A farmer buys three cows, two pigs, and four hens from a man who has six cows, five pigs and eight hens. How many choices 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. Find total elapsed time for set of tasks T = {T1, T2, …, T9} to be executed on three processors. A relationship between the tasks is given in following figure and execution time for each 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.
[2].
3) Define ‘hasse diagram’ and ‘lattice’ with example. [1]
**********
******Best of Luck******
***********
Solution
ADIT/BVM/GCET
A.Y. 2007-08, Semester II
INTERNAL EXAMINATION
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 answer to the question point to point.
Q.1 Attempt following:
[A] 1) Show that
12 + 32 +52 + …+(2n-1)2 = n (2n-1) (2n+1) / 3
[2]
Ans. Basic of the induction:
For n=1
L.H.S = 1
R.H.S = 3/3 = 1
Induction hypothesis:
Assume that for n= k it is true,
12 + 32 +52 + …+(2k-1)2 = k (2k-1) (2k+1) / 3
Now n = k +1
L.H.S = 12 + 32 +52 + …+(2k-1)2 + ( 2k + 1)2
= k (2k-1) (2k+1) / 3 + ( 2k + 1)2
= (2k + 1) [ 2k2 + 2k + 3k + 3 ]/3
= (2k + 1) ( k +1 ) ( 2k + 3) /3
Marking Strategy:
1. If above steps are shown correctly then 2 marks.
2) Among 100 students, 32 study mathematics, 20 study physics, 45 study biology, 15 study mathematics and biology, 7 study mathematics and physics, 10 study physics and biology, and 30 do not study any of the three subjects.
(c) Find the number of students studying all three subjects.
(d) Find the number of students studying exactly one of the three subjects. [2]
Ans. We are given following data:
| M | = 32, | P | = 20, | B | = 45
| M ? B | = 15, | M ? P | = 7, | P ? B | = 10
~|M U P U B | = 30
a) Number of students are studying all the three subjects:
|M U P U B | = 1 - ~|M U P U B | = 100 – 30 = 70
|M U P U B | = | M | + | P | + | B | - | M ? B | - |M ? P | -| P ? B | + | M ? P ? B |
70 = 32 + 20 + 45 – 15 – 7 – 10 + | M ? P ? B |
| M ? P ? B | = 5 students are studying all the three subjects
b) Number of students who studying exactly one of three subjects:
= | M | + | P | + | B |
= 25 + 15 + 8
= 48
Marking Strategy:
1. For each of the correct answer 1 mark.
3) Construct the truth table for the following statements:
(c) (a ? a) ? (a ? a)
(d) a ?? (e V a) [1]
Ans.
a a a ? a a ? a (a ? a) ? (a ? a)
T F T F F
F T T T T
a e a e e V a a ?? (e V a)
T T F F F F
T F F T T T
F T T F T F
F F T T T F
Marking Strategy:
1. For each correct truth table 0.5 marks.
[B] 1) In the following 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. Describe the language specified by set of productions verbally as well as in set-theoretic notations. (Any one)
(c) {S?AB, A?aA, A?a, B?Bb, B?b}
(d) {S?aA, A?bA, A?bC, C?cC, C?c} [2]
Ans. {S?AB, A?aA, A?a, B?Bb, B?b}
Language generated by grammar rules is:
L = { ai bj | i >= 1, j >=1}
OR
{S?aA, A?bA, A?bC, C?cC, C?c}
Language generated by grammar rules is:
L = { a bi cj | i >=1, j >=1}
Marking Strategy:
1. If correct set theoretic notation then 2marks.
2) Give the grammar that specifies the following language. (Any one)
(c) L={ai bj cq | i+j=q, i>=1, j>=1}
(d) L={a2i c b2j+1 | i>=1, j>=1} [2]
Ans. a) L={ai bj cq | i+j=q, i>=1, j>=1}
First we find which type of strings are generated in the language:
L = { abcc, aabccc, abbccc, abbbccc… }
Grammar rule for the above language:
S ? aSc
S ? aBc
B ? bBc
B ? bc
OR
b) L={a2i c b2j+1 | i>=1, j>=1}
First we find which type of strings are generated in the language:
L = { aacbbb, aaaacbbb, aaaacbbbbb…}
Grammar rule for the above language:
S ? AB
S ? Bbb | cbbb
A ? aaA | aa
Marking Strategy:
1. If all the rules are written correctly then 2 marks.
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]
Ans. signed_interger ? sign integer
? - digit integer
? - 0 digit integer
? - 0 0 digit
? - 0 1 0
Marking Strategy:
1. If all the steps are correct shown then 1 mark.
Q-2 Attempt following:
[A] 1) Consider the experiment of tossing a fair coin until two heads or two tails appears in succession.
(c) Describe the sample space.
(d) What is the probability that the experiment ends before the sixth toss?
[1]
Ans. a) Sample space: Which contains the entire sample until there is two heads or tails appears in succession.
{H, T, HT, TH, HTH, THT, HTHT, THTH…. }
b) Probability that the experiment ends before the sixth toss:
- When coin is tossed two times one after other then sample space: {HT, TH, HH, TT}. So, out of four samples there are two samples in which two heads of tails appear.
1. Two times: {HH, TT} then probability is 2/4 = 0.5
2. Three times: { HTT, THH } = 2/8 = 0.25
3. Four times: { HTHH, THTT} = 2/16 = 0.125
4. Five times: { HTHTT, THTHH } = 2/32 = 0.0625
So, probability that the experiment ends before the sixth toss:
= 0.5 + 0.25 + 0.125 + 0.0625
= 0.9375
Marking Strategy:
1. For each correct answer 0.5 marks.
2)
2) In how many ways can the letters in the English alphabet be arranged so that there are exactly seven letters between 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 arranged if the two P’s must be separated?
[2]
Ans. There are 26 alphabets in English we have to arrange 7 letters between a & b.
So, here 24P7 ways in which we can arrange 7 letters.
2! Ways we can arrange a & b.
Total no. of ways to arrange 7 letters between a & b is
= 24P7 * 2!
Remaining 17 letters and block of 9 letters can be arranged in 18! Ways.
Total number of ways = 24P7 * 2! * 18!
OR
Total number of arrangements are = 11! / 2! 4! 4!
= 34650
Total no of ways they can arrange so that two p’s must be together are:
= 10! / 4! 4!
= 6300
Now total no of ways they can be arrange so that two p’s must be separated are:
= 11! / 2! 4! 4! - 10! / 4! 4!
= 34650 - 6300
= 28350
Marking Strategy:
1. For each correct answer 1 mark.
3)
3) There are 50 students in each of the junior and the senior classes. Each class has 25 male and 25 female students. In how many ways can eight representatives be selected so that there are four female and three juniors?
OR
A farmer buys three cows, two pigs, and four hens from a man who has six cows, five pigs and eight hens. How many choices does the farmer have? [2]
Ans.
Male Female
Junior 25 25
Senior 25 25
No of ways we select the junior female are: 0 1 2 3
No of ways we select the senior female are: 4 3 2 1
No of ways we select the junior male are: 3 2 1 0
No of ways we select the senior male are: 1 2 3 4
So the total no of ways we select the 4 females and 3 juniors are = 25C0 * 25C4 * 25C3 * 25C1 + 25C1 * 25C3 * 25C2 * 25C2 + 25C2 * 25C2 * 25C1 * 25C3 + 25C3 * 25C1 * 25C0 * 25C4
OR
Number of choice the farmer have = 6C3 * 5C2 * 8C4
= 100800 / 72
= 14000
Marking Strategy:
1. If correct answer for any of above then 2 marks.
2. If correct selection is made then 1 marks.
[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]
Ans. Reflexive: If we take any pair then we get 0, which is neither odd nor even. So, relation is not reflexive.
Symmetric: If we take the ordered pair (6,3) then we can’t include ordered pair (3,6). So, relation is not symmetric.
Antisymmetric: If we take the ordered pair (6,3) then there is not (3, 6) in the relation. Hence, relation is antisymmetric.
Transitive: The ordered pair (8, 5) and (5, 2) in relation but (8, 2) does not in the relation. So, relation is not transitive.
Equivalence relation: No
Partial ordering relation: No
Marking Strategy:
1. If all relations are correct then 2 marks.
2. Otherwise 0.25 for each correct answer.
2) The procedures of scheduling a set of tasks according to the rule of never leaving a processor idle intentionally. Find total elapsed time for set of tasks T = {T1, T2, …, T9} to be executed on three processors. A relationship between the tasks is given in following figure and execution time for each 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.
[2].
Ans.
P1 T5 T9 T8
P2 T3 T7 T6
P3 T2 T1 T4 ?1
Total elapsed time = 9 (maximum time on any processor)
Marking Strategy:
1. If diagram is drawn without keeping processor idle intentionally with priority then 2 marks.
2. If diagram is drawn without keeping processor idle and without priority consideration then 1 mark.
3. If any executable task is there and processor is idle then zero mark.
3) Define ‘hasse diagram’ and ‘lattice’ with example. [1]
Ans. Hasse diagram: graphical representation of a partially ordering relation in which all arrowheads are understandable to be pointing upward is known as the hasse diagram of the relation.
For example: poset(A,/), where A = { 2, 4, 6, 12 }
12
4 6
2
Hasse diagram lattice
Lattice: A partially ordered set is said to be a lattice if every two elements in the set have unique least upper bound and a unique greatest lower bound.
Marking Strategy:
1. For each definition with example 0.5 mark.
Return to question paper search
|
|
|
Submit Previous Years University Question Papers and make money from adsense revenue sharing program
Are you preparing for a university examination? Download model question papers
and practise before you write the exam.
|
Watch TV Channels
|