Sardar Patel University 2008 B.E Computer Science CP201-Introduction to Theoretical (Internal Test) - Question Paper

[1]
Ans. a) Sample space: Which contains the entire sample until there is 2 heads or tails appears in succession.
{H, T, HT, TH, HTH, THT, HTHT, THTH…. }
b) Probability that the experiment ends before the 6th toss:
- When coin is tossed 2 times 1 after other then sample space: {HT, TH, HH, TT}. So, out of 4 samples there are 2 samples in which 2 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 6th toss:
= 0.5 + 0.25 + 0.125 + 0.0625
= 0.9375


Marking Strategy:
1. For every accurate ans 0.5 marks.

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]
Ans. There are 26 alphabets in English we have to organize seven letters ranging from a & b.
So, here 24P7 ways in which we can organize seven letters.
2! Ways we can organize a & b.
Total no. of ways to organize seven letters ranging from a & b is
= 24P7 * 2!

Remaining 17 letters and block of nine letters can be organizes 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 organize so that 2 p’s must be together are:

= 10! / 4! 4!
= 6300
Now total no of ways they can be organize so that 2 p’s must be separated are:
= 11! / 2! 4! 4! - 10! / 4! 4!
= 34650 - 6300
= 28350
Marking Strategy:
1. For every accurate ans one mark.


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]
Ans.
Male Female
Junior 25 25
Senior 25 25

No of ways we choose the junior female are: 0 1 2 3
No of ways we choose the senior female are: 4 3 2 1
No of ways we choose the junior male are: 3 2 1 0
No of ways we choose the senior male are: 1 2 3 4

So the total no of ways we choose the four females and three juniors are = 25C0 * 25C4 * 25C3 * 25C1 + 25C1 * 25C3 * 25C2 * 25C2 + 25C2 * 25C2 * 25C1 * 25C3 + 25C3 * 25C1 * 25C0 * 25C4

OR
Number of option the farmer have = 6C3 * 5C2 * 8C4
= 100800 / 72
= 14000
Marking Strategy:
1. If accurate ans for any of above then two marks.
2. If accurate selection is made then one 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 accurate then two marks.
2. Otherwise 0.25 for every accurate ans.

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.














[2].
Ans.

P1 T5 T9 T8

P2 T3 T7 T6

P3 T2 T1 T4 ?1



Total elapsed time = nine (maximum time on any processor)
Marking Strategy:
1. If diagram is drawn without keeping processor idle intentionally with priority then two marks.
2. If diagram is drawn without keeping processor idle and without priority consideration then one 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

four 6

2
Hasse diagram lattice

Lattice: A partially ordered set is stated to be a lattice if every 2 elements in the set have unique lowest upper bound and a unique greatest lower bound.

Marking Strategy:
1. For every definition with example 0.5 mark.

Earning:   Approval pending.