DOEACC Society 2009 M.C.A B level - Question Paper
B4.2-R3: DISCRETE STRUCTURES
NOTE:
1. Answer question 1 and any FOUR questions from 2 to 7.
2. Parts of the same question should be answered together and in the same sequence.
Total Marks: 100
Time: 3 Hours
1.
a) Determine {} n {a, d, {<}.
b) Obtain an equivalent formula for pA(qr) containing neither the biconditional nor the conditional.
c) For any Boolean Algebra(B,+,V) or (B,v,a,/) , Vae B, show that (a ')' = a.
d) If the binary operation o:R XR R is defined by a o b = a + b -5, prove that o operation has an identity. Also find inverse of an element a e R with respect to this binary operation.
e) Prove that the product of r consecutive integers is divisible by r!.
f) If G =(V,E) where V={ v1 ,v2,v3,v4,v5,v6) and E = {v1 v2, v1v5,v1v6,v2v3,v2v5,v3v4,v4v5}
Then find complement of G.
g) Represent the following set by regular expression:
(an| n is divisible by 2 or 3 or n= 5)
(7x4)
2.
a) If R1 and R2 are two equivalence relations on a set A, then prove that R1nR2 is also an equivalence relation on A. What can you say for R1 u R2,?
b) Hasse diagram of poset S = {1,2,3,4,5,6} is given below. If A={2,3,4} is a subset of S, find upper bounds, lower bounds, supremum and infimum of A.
 |
|
2 |
c) Let N be the set of natural numbers including zero. Determine which of the following functions are one to one, which are onto and which are one to one onto?
i) f: N N f(j) = j2 +2
ii) f: N N f(j)= 1 if j is odd
3.
a) Without using truth table show that
((P v Q) a ( P a ( Qv R)) v ( P a Q) v( P a R)) is a tautology.
b) Check the validity of the following argument:
If the rents of Hotels in Bombay are fixed or the prices of the commodities are reduced, then the income of businessmen shall decrease. If the income of businessmen decrease then the farmers shall feel happy. The farmers never feel happy. Therefore the rents of the hotels are not fixed.
c) Show that the operations +,-, and . on Zm are well defined functions.
(6+6+6) 4.
a) Simplify the following expressions in a Boolean algebra.
i) (a+b) a' .b'
ii) (a + a' b) (a' + a b)
b) Show that the set Pn of all permutations on the set A={ai,a2,a3,....an} is a finite group of order n! with respect to the composition of "product of permutations or composition of permutations.
c) Determine a railway network of minimal cost for the cities in the figure:
|
15 |
 |
(6+6+6) 5.
a) How many vertices will the following graphs have if they contain:
i) 16 edges and all vertices of degree 2.
ii) 21 edges, 3 vertices of degree 4, and the other vertices of degree 3.
iii) 24 edges and all the vertices of the same degree.
b) Apply Dijkstras algorithm to find shortest paths from the source node a to all other nodes in the following graph:
c) Show that any graph with 4 or fewer vertices is planar.
(6+6+6)
b) Let ={a,b} and let na(w) and nb(w) denote the number of as and number of bs in the string w respectively. Then write a grammar to generate the language L.
a) Convert the non deterministic finite automata in the following graph into equivalent deterministic machine:
L ={w: na(w) =nb(w)}
c) Show that the language
L={an bk cn+k : n >0, k>0} is non regular.
(6+6+6)
7.
a) Find a generating function for ar = the number of ways the sum r can be obtained when:
i) 2 distinguishable dice are tossed.
ii) 2 distinguishable dice are tossed and the first shows an even number and the second shows an odd number.
b) Solve the following recurrence relation by substitution: an = an-1 +1/n(n+1) where a0 = 1
c) Prove that in a connected (simple) plane graph G, with |E| >1
i) |E| < 3|V|-6
ii) there exists a vertex of G such that degree(v) <5
(6+6+6)
B4.2-R3 Page 3 of 3 January, 2009
B3.4-R3: OPERATING SYSTEMS
1. Answer question 1 and any FOUR questions from 2 to 7.
NOTE:
2. Parts of the same question should be answered together and in the same sequence.
Time: 3 Hours Total Marks: 100
1.
a) What are the basic functions of an operating system?
b) Differentiate between monitor mode and user mode with respect to protection (security) in a computer system.
c) Explain Petersons solution for avoiding race condition.
d) Explain in detail the structure of PCB.
e) What is a thread? How are thread implemented in Kernel mode?
f) What is the cause of thrashing? How does the system detect thrashing? Once it detects thrashing, what can the system do to eliminate this problem?
g) List four modules of an operating system and explain in detail of functionality of each module.
(7x4)
2.
a) Suppose that a disk drive is currently serving a request at cylinder 11. The queue of pending requests in FIFO order is 98, 183, 37, 122, 14, 124, 65 and 67. Starting from the current head position, what is the total distance that the disk arm moves to satisfy all the pending requests, for each of the following disk-scheduling algorithm?
i) FCFS ii) SSTF iii) SCAN/Elevator
b) Distinguish between internal and external fragmentation. Provide any two solutions to avoid external fragmentation.
c) What is a Deadlock? How can it be prevented?
(9+5+4)
3.
a) Consider a 'claim matrix', an 'allocation matrix' and a 'available vector' for a set of processes.
Claim Matrix Allocation Matrix Available Vector
|
R1 |
R2 |
R3 |
R1 |
R2 |
R3 | ||
|
P1 |
3 |
2 |
2 |
P1 |
1 |
0 |
0 |
|
P2 |
6 |
1 |
3 |
P2 |
5 |
1 |
1 |
|
P3 |
3 |
1 |
4 |
P3 |
2 |
1 |
1 |
|
P4 |
4 |
2 |
2 |
P4 |
0 |
0 |
2 |
R1 R2 R3 1 1 2
Answer the following questions using the Bankers algorithms:
i) What are the maximum units of all resources?
ii) What are the contents of the matrix need?
iii) Is the system in a safe state?
iv) A resource request for one of the processes is given. For example, if process P3 request 1 unit of R3, is this request be granted? If yes, give a <sequence> in which all processes can run to completion.
b) What is a semaphore? Which are operations done on semaphore? Give implementation of producer-consumer problem with bounded buffer using semaphore.
c) What is the difference between system call and system program.
(10+6+2)
4.
a) Explain contiguous allocation and linked list allocation for implementing file storage.
b) What are the various layers of I/O software? Explain the function of each layer.
c) What are the advantages of a Distributed File System over a file system in a centralized system?
(6+6+6)
5.
a) Draw and explain a process state transition diagram with one suspended state.
b) Discuss swapping in brief. How does buddy system speed up merging when process swaps out?
c) Consider the following set of processes in order P1, P2, P3, P4 and P5 with the length of the CPU burst time given in milliseconds. Their priorities are 3,5,2,1 and 4 respectively, with 5 being the highest priority, calculate average waiting time and turn-around time using following scheduling algorithms.
(1) Shortest Remaining Time First (2) Round Robin (q=2)
(3) Shortest Job First (4) Priority Scheduling (Preemptive)
|
Process |
Arrival Time |
Burst Time |
|
P1 |
0 |
10 |
|
P2 |
1 |
9 |
|
P3 |
2 |
6 |
|
P4 |
3 |
7 |
|
P5 |
4 |
4 |
(5+5+8)
6.
a) Explain the protection domain in UNIX.
b) Discuss interleaving in brief. How does DMA increase system concurrency?
c) How long does it take to load 64 Kbyte program from a disk whose average seek time is 10 msec, rotation time is 10 msec and track holds 32 Kbytes. Calculate time when page size is 2 Kbyte and also when page size is 4 Kbyte. Assume that pages are spread around the disk and no two pages are on the same cylinder.
d) What information is saved and restored during a context switch?
(6+6+4+2)
7.
a) What is a page fault? What are the steps to be followed by operating system after occurring page fault?
b) Explain the following terms:
i) Spooling
ii) Beladys Anomaly
iii) Priority Inversion Problem
iv) Shared Pages
c) Explain architecture of UNIX Operating System.
(6+8+4)
B3.4-R3 Page 2 of 2 January, 2009
|
Attachment: |
| Earning: Approval pending. |
