MH SET 2013: 17 February, Paper III, Computer Science and Applications
Text of page 1
FEB - 37313/III
Computer Science and Applications
Paper III
Time Allowed : 2½ Hours] [Maximum Marks : 150
Note : This Paper contains Seventy Five (75) multiple-choice questions, each
question carrying Two (2) marks. Attempt All of them.
1. Which operand addressing mode requires the most complicated circuit in the
CPU ?
(A) immediate (B) direct
(C) indexed (D) indirect
2. The number of combinational functions of n variables is :
(A) 2**n (B) 2**(2*n)
(C) 2**(2**n) (D) None of these
3. The minimum number of radix-64 digits needed to represent an unsigned
64-bit binary number is :
(A) 10 (B) 11
(C) 12 (D) None of these
4. The x86 MOV class of instructions is used to copy data from one location to
another. Which of the following statements is false ?
(A) Integers can be moved between memory locations.
(B) Strings can be moved between memory locations.
(C) Integers can be moved conditionally.
(D) There are several conditions governing a conditional move.
5. Which of these general purpose registers is used in x86 to store
the value returned by a function call ?
(A) ecx (B) esp
(C) eax (D) ebp
6. (Polling versus interrupts) Which of the statements below is correct ?
(A) Polling is done periodically by the CPU
(B) Polling requires less hardware in peripherals than interrupts
(C) Polling makes more demands on CPU resources than interrupts
(D) Polling is harder to implement than interrupts
1 [P.T.O.
Text of page 2
FEB - 37313/III
7. Arts DBMS is designed to maintain general database and provide all facilities
required for wide range of business application software. Arts DBMS has optimal
scheduler to perform transactions for better performance.
Which of the following serializable schedules would Arts DBMS scheduler
prefer ?
(A) Transaction 1 Transaction 2 (B) Transaction 1 Transaction 2
Read X Read X Read X
..... .....
Write X Write X
Write X Read X
Read Y Read Z Write X
Write Y Write Z Read Y
Write Y
Read Z
Write Z
(C) Transaction 1 Transaction 2 (D) Transaction 1 Transaction 2
Read X Read X
Read Y .....
Write X Write X
Write Y Read X
Read X Write X
Read Z Read Y Read Z
Write X Write Y Write Z
Write Z
2
Text of page 3
FEB - 37313/III
8. In order to improve the performance of Arts DBMS mentioned in question number
7, the Scheduler further started handling parallel events in multiuser mode.
At some instant of time the system entered a deadlock state with the following
transaction scenario :
Data items locked Data items transaction
Transaction
by transaction is waiting for
T1 X2 X1, X3
T2 X3, X10 X7, X8
T3 X8 X4, X5
T4 X7 X1
T5 X1, X5 X3
T6 X4, X9 X6
T7 X6 X5
The DBMS started analysing the state and decided to overcome the situation
by aborting minimum number of transactions. The system started testing serially
and found that by aborting some transactions it could remove the deadlock
whereas some transactions were found strong such that by aborting those it
could not remove the deadlock state.
In the situation above, termination of which transaction does not affect the
deadlock state ?
(A) T6 (B) T5
(C) T2 (D) T3
3 [P.T.O.
Text of page 4
FEB - 37313/III
9. In continuation with the scenario described in question number 7 and 8, consider
time stamping mechanism instead of locks for tackling concurrency related
problems. In that case Arts DBMS maintains a record of different transaction
times for each data item in the system. For example, t-In(x) denotes the time
of insertion of the data item x into the system, t-Del(x) denotes the time of
deletion of the data item x from the system. Similarly, t-R(x) denotes the time
when the x was last read and t-W(x) denotes the time of last update of the
item x in the system. The scheduler receives a request from any process regarding
any item x, in the form given below :
(<transaction-type>, <request-time>, <item>).
If the request is valid then it is granted and the corresponding changes are
made in the database. The assumptions are as follows :
(i) Insertion is valid iff the item does not exist in the database.
(ii) Read is valid iff the item does exist in the database and the last update
is older than the current transaction.
(iii) Deletion and update (write) are valid iff the item exists and is not being
used by any other process.
Which concurrency control technique does Arts DBMS follow now ?
(A) Total Timestamp ordering
(B) Partial Timestamp ordering
(C) Multiversion Timestamp ordering
(D) Read-Write Timestamp ordering
4
Text of page 5
FEB - 37313/III
10. Arts DBMS is used to implement automation of Shivam Engineering. Shivam
Engineering is a private organisation manufacturing compressors. It has five
branches located at places 200 to 1000 Kms from the central head office. Instead
of having a centralised database, the MIS manager of Shivam Engineering
opts for a distributed database system. All sites will have Arts DBMS in order
to avoid any problem of mismatched database capabilities.
Which type of distributed database is implemented at Shivam Engineering ?
(A) Heterogeneous DDBS (B) Homogeneous DDBS
(C) Multi-database System (D) Federal database System
11. DBA of Shivam Engineering allocated data to six different sites applying a
technique of data distribution. After a test period, DBA checked the performance
of the system with respect to standard parameters. He found that the locality
of reference, reliability and availability, performance are satisfactory, whereas
communication and storage costs are high.
Which data distribution technique might the DBA have implemented ?
(A) Centralised (B) Partitioned
(C) Replicated (D) Fragmented
12. As Shivam Engineering decided to implement a distributed database system,
Arts DBMS needs to upgrade its components to maintain atomicity and durability
of distributed transactions as well as consistency of data. Arts DBMS recovery
mechanism is upgraded to recover the data even in case of failure of any one
site including the coordinating site, without blocking any site.
Which recovery mechanism was applied in Arts DBMS ?
(A) Two-phase commit (B) Three-phase commit
(C) Roll-backward recovery (D) Roll-forward recovery
5 [P.T.O.
Text of page 6
FEB - 37313/III
For the answers to the next three questions read the paragraph given below :
In My Computer if you want to select a colour, you have a choice of Colour1
or Colour2 or Colour3. Call this set Palette. Further, a colour pixel is either
set to invisible mode or it is visible. I wish to increase the choice for the colour
to be selected in My Computer by adding the following logic : Add 50% white
to get light shades and add 50% black to get dark shades. Call it New Palette.
13. In order to facilitate New Palette, what is minimum number of bits needed
per pixel ?
(A) 10 (B) 7
(C) 5 (D) 6
14. Given : Let Display be the function that takes three parameters (position, colour
and visibility), and paints the pixel. Here position indicates coordinates of the
point to be painted, colour specifies the colour from Palette for painting the
pixel, which is invisible if visibility set to 0 and is visible otherwise.
What is the purpose of the body of the While loop in the following
algorithm ?
x = 0; y = 0
while not keypressed( ) do
Display ((x, y), Colour2, x))
x = x + 1
Display ((x, y), Colour1, x))
delay for 50 milliseconds
enddo
(A) Draw a two colour line (consecutive points are of different colours) that
starts at the origin
(B) A point started at the origin progressing in the positive direction of the
X-axis, leaving the trail in the other colour.
(C) A point moving horizontally
(D) (B) or (C) above
6
Text of page 7
FEB - 37313/III
15. Let Colour1, Colour2 and Colour3 be Red, Green and Blue, respectively. In
your picture, you want to show a butterfly with red and green spots on its
violet wings. Which of the statements below is true ?
(A) It is not possible to show this picture
(B) It is possible to paint the wings of the butterfly in violet
(C) Red and green on violet can be shown by changing the texture of the wings
from violet to red and blue
(D) Both (B) and (C)
16. The entities given in the set {PDF, 3-D Studio Max, graphic design, cartoon
animation, calligraphy} are closely associated with :
(A) Graphics editing (B) Vector graphics
(C) Raster graphics (D) Both (B) and (C)
17. Assuming that a ≠ b ≠ c, to what transformation does this 4 × 4 matrix correspond
to ?
a 0 0 0
0 b 0 0
0 0 c 0
0 0 0 1
(A) shear (B) non-uniform scaling
(C) rotation (D) uniform scaling
7 [P.T.O.
Text of page 8
FEB - 37313/III
18. A 2-dimensional rotation of a point about the origin by 180 degrees in
anticlockwise direction, followed by reflection about the x axis is equivalent
to reflection about which line ?
(A) y = –x (B) y = x
(C) x = 0 (D) y = 0
19. Predict the output of the following pseudo-code for F(5) :
function F(var n : integer)
begin
if n ≠ 0
then
print n
F(n – 1)
print n
end
(A) 5544332211 (B) 554433221100
(C) 54321 (D) 5432112345
8
Text of page 9
FEB - 37313/III
20. Which of the following arrays represents the given binary tree ?
6
2 7
1 4 8
3 5
6 2 7 1 4 8 3 5
1 2 3 4 5 6 7 8 9 10 11 12
(A) 6 2 7 1 4 8 3 5
(B)
(C) 6 2 7 1 4 8 3 5
(D) 1 2 3 4 5 6 7 8
9 [P.T.O.
Text of page 10
FEB - 37313/III
21. Predict the output of the following pseudo-code for F(5) :
function F(var n : integer)
var
n : integer
i : integer
x : integer
begin
i ← 0
while i < n do
begin
print i
i ← i + 1
end
end
(A) 0 1 2 3 4
(B) Output cannot be predicted due to redeclaration of variable ‘n’
(C) Error in pseudo-code due to redeclaration of variable ‘n’
(D) Error in pseudo-code due to unused variable ‘x’
10
Text of page 11
FEB - 37313/III
22. Predict the output of the following flow-chart :
(Note : ++ in post-increment operator in i++ and j++)
i←0
j←0
NO
i++
YES
Display i
j++
(A) 0 1 2 3 4 5 .......... (B) 1 2 3 4 5 6 ..........
(C) No output (D) Error
23. Conceptually which of the following language paradigm is most powerful in
terms of its ability to solve given problems ?
(i) Procedure oriented
(ii) Object oriented
(iii) Functional
(iv) Logical
(A) (i) and (ii) (B) (ii)
(C) (iii) (D) All are equal
11 [P.T.O.
Text of page 12
FEB - 37313/III
24. Consider the following scenario :
• Class ‘A’ contains a variable ‘x’ and a method ‘fa’.
• Class ‘B’ is derived from Class ‘A’.
• Class ‘B’ contains a method ‘fb’.
What should be the visibility of ‘x’ in ‘A’ to satisfy the following requirements :
• ‘x’ should be accessible to ‘fa’ and ‘fb’.
• ‘x’ should not be accessible to users of ‘A’ or ‘B’ objects.
(A) Private
(B) Protected
(C) Public
(D) The requirements cannot be satisfied
25. Let g(x) = x3 + x + 1. Find the cyclic redundancy check (CRC) codeword-
corresponding to the information sequence 1001 :
(A) 0111 (B) 110
(C) 1011 (D) 011
Consider the following information to answer questions 26 and 27 :
Consider an ARQ (Automatic Repeat Request) protocol that uses only negative
acknowledgments (NAKs), but no positive acknowledgements (ACKs). Under these
conditions :
26. The condition for timeouts needed is that :
(A) No Timer required
(B) NAK TIMER is required at receiver side
(C) NAK TIMER is required at sender side
(D) Both (B) and (C)
12
Text of page 13
FEB - 37313/III
27. The ACK based ARQ is preferred to the NAK based protocol due to :
(A) Easy management
(B) Increased complexity at sender and receiver due to NAKs
(C) ACKs are faster than NAKs
(D) NAKs consume more bandwidth
28. Suppose you are designing a sliding window protocol for a 1-Mbps point-to-
point link to Mars, which has a one-way latency of 1.25 seconds. Assuming
that each frame carries 1 kb of data, the minimum number of bits you need
for the sequence number is :
(A) 9 bits (B) 11 bits
(C) 10 bits (D) 12 bits
29. A communications link provides 1 Mbps for communications between the earth
and the moon. The link is used to send color images from the moon. Each image
consists of 10,000 × 10,000 pixels, and 16-bits are used for each of the three-
color components of each pixel. How many images per second can be transmitted
over the link ?
(A) 2.1 × 10–4 (B) 2.1 × 104
(C) 2.1 × 10–5 (D) 2.2 × 106
13 [P.T.O.
Text of page 14
FEB - 37313/III
30. Suppose Ethernet physical addresses are chosen at random (using true
randombits). The probability that on a 1024-host network, two addresses will
be the same is :
(A) 1.77 × 10–9 (B) 1.87 × 10–9
(C) 1.99 × 10–9 (D) 1.98 × 10–8
Q. Nos. 31 to 34 are based on the paragraph given below :
Let us consider a data structure named UD. Storage can be made in UD in
non-increasing order of address. Each address consists of two bytes (i.e., a word).
X is a pointer that points to the most recent element entered in UD. InB stores
a byte in UD, InW stores a word. When a word is stored, X value changes
by 1. If InB stores in the least significant byte of the storage word, X does
not change value, otherwise value of X is changed by 1. Similarly, OutB retrieves
a byte from UD. OutW retrieves a word from UD. If OutB retrieves the most
significant byte, X is not changed. If OutB retrieves the least significant byte,
value of X is changed by 1. OutW changes the value of X by 1. Assume that
UD is not empty.
31. What is UD ?
(A) Dequeue (B) Array
(C) Circular Queue (D) Stack
14
Text of page 15
FEB - 37313/III
32. Assume that we have already applied InW ‘myword’, and InB ‘mybyte’ into
an empty UD, where myword = ‘00001110 00101010’, and mybyte = ‘00001111’.
What is the value of X ? Assume that X value is ‘Limit’ when UD is empty.
(A) Limit + 1 (B) Limit – 1
(C) Limit + 3 (D) Limit – 2
33. The content of UD remains as in Q. No. 32. Now the following operations are
carried out : InB X, InW Y, InB Z, OutB, OutB, OutB, OutW. The contents
of UD is now :
(A) 14, 42 (B) 42, 19, 34
(C) 5, 503, 42 (D) 14, 42, 19
34. The contents of UD are contained in the range R1 and R2 (both excluded and
R1 < R2). What is the maximum number of InB operations that can be carried
out ?
(A) 0 (B) R 2
(C) 2*R2 – 2*R1 + 2 (D) 2*R1 – 2*R2 + 1
35. Let P be the set problems solvable in deterministic polynomial time, NP is the
set of problems solvable in non-deterministic polynomial time, NPC is the set
of NP complete problems.
Given X = P ∩ NP, Y = NP – P, Z = P ∩ NPC, which of the following is
true ?
(A) X = NP, Y ≠ φ, Z = φ (B) X = P, Y ⊇ NPC, Z ≠ φ
(C) X = P, Y ⊇ NPC, Z = φ (D) X = NP, Y ⊇ NPC, Z ≠ φ
15 [P.T.O.
Text of page 16
FEB - 37313/III
36. Multiplication of two complex numbers x = a + ib and y = c + id require only
n multiplications where n = .................... .
(A) 3 (B) 2
(C) 4 (D) 5
37. A polymorphic system :
(A) should be reusable
(B) should have polymorphic data types
(C) should accept generic commands
(D) should morph polygons
38. A class is :
(A) a group of objects
(B) template for objects of a particular type
(C) a class of objects
(D) a classification of objects
39. Which of the following entities can be defined as objects ?
(i) a motor car
(ii) a bank account
(iii) an aircraft
(iv) a linked list
(A) (i) (B) (i), (ii)
(C) (i), (ii), (iii) (D) (i), (ii), (iii), (iv)
16
Text of page 17
FEB - 37313/III
40. By abstraction in object-oriented modeling we mean picking :
(A) only attributes appropriate to model an object
(B) only operations appropriate to model an object
(C) operations and attributes appropriate to model an object
(D) the appropriate abstract data type
41. Inheritance in object-oriented modeling can be used to :
(A) generalize classes
(B) specialize classes
(C) generalize and specialize classes
(D) create new classes
42. An object is selected for modeling a system provided :
(A) its attributes are invariant during operation of the system
(B) its attributes change during operation of the system
(C) it has numerous attributes
(D) it has no attribute relevant to the system
43. In ...................................... the software functionality is verified against
the SRS.
(A) Stress testing (B) Integration testing
(C) White box testing (D) Black box testing
44. Suppose you have to gather requirements from users for a rather complicated
but small scale system in one sitting. In this scenario, which of the following
is a better choice over the others ?
(A) Waterfall model (B) Iterative model
(C) Prototype model (D) Spiral model
17 [P.T.O.
Text of page 18
FEB - 37313/III
45. Which among the following is not a class-oriented software metric ?
(A) Depth of inheritance tree
(B) Weighted methods per class
(C) Coupling between classes
(D) Class content complexity
46. In an application written in Java, it was found that a particular computationally-
intensive module, that contains 1% of the total code of the entire software, takes
40% of the execution time. Call the module HeavyModule.
Given : To code such an application in Java, it takes 100 man days. Programming
in Assembly Language takes 10 times more man days than in Java. However,
the programs coded in Assembly Language runs 10 times faster than the
programs coded in Java. Converting a Java program into Assembly Level
language takes 5 times more man days than that of developing it directly in
Assembly.
What is the cost of converting HeavyModule into Assembly language, compared
to the cost of deciding at design time to write 99% of the code in Java and
1% in Assembly ?
(A) A design-time decision and developing the code in the respective languages
saves around 5% of the time and brings 40% speed up in execution time
(B) Design time decision and developing the code in the respective languages
costs around 4% higher in terms of the time and brought 40% speed up
in the execution time
(C) Late decision to convert HeavyModule into Assembly saves almost 4% of
the man days and reduces the execution time by 36%
(D) Late decision to convert HeavyModule into Assembly increases the man
days by almost 4% but reduces the execution time by 36%
18
Text of page 19
FEB - 37313/III
47. With software emerging as a service on the internet, a useful set of software
metrics for web applications have emerged. Which of the following metrics
measures navigation flow ?
(A) Connectivity density (B) Page complexity
(C) Selection complexity (D) Layout complexity
48. Two programmers, each with productivity 100 LOC per month, were employed
to complete a project of size 48 KLOC within a year’s time. In the 10th month
it was realized that the project was lagging behind the completion schedule.
Two extremely good quality programmers (having productivity 200 LOC/month)
were additionally employed for the next two months. Interpersonal interactions
hampered productivity. Assuming that a line of communication between any
two persons causes 5% reduction in the team’s productivity, what would be the
status of the project at the end of the 12th month ?
(A) Completed before deadline
(B) 4/5 of the work is completed
(C) 3/4 of the work is completed
(D) 2/3 of the work is completed
19 [P.T.O.
Text of page 20
FEB - 37313/III
Consider the following passage to answer questions from Q. Nos. 49 to 54 :
Virtual Memory is a technique that allows the execution of processes that may
not be completely in the memory. In this system of over-allocation, while a
user process is executing, a page fault occurs. The operating system determines
where the desired page is in the memory, but then finds that there are no
free frames. In that case, it finds a victim page to be swapped out, thereby
making a frame free for the desired page to be swapped in. For this, there
are many different page-replacement algorithms. FIFO Page Replacement, LRU
Page Replacement, Optimal Page Replacements, etc. are some of the known
algorithms. The basic objective of page-replacement algorithms is to minimize
the number of page faults. We can do this minimization by distributing heavily-
used pages evenly over all of memory, rather than having them compete for
a small number of page frames. We can also associate with each page frame
a counter of the number of pages that are associated with that frame. Then,
to replace a page, we search for the page frame with the smallest counter. We
20
Text of page 21
FEB - 37313/III
may consider such a customized page-replacement algorithm, known as “Best
CBPR Algorithm” defined as under :
“The initial value of the counter for each page frame is 0. The counter is
incremented whenever a new page is associated with that frame and the counter
is decremented whenever one of the pages associated with that frame is no longer
required. In order to replace a page, the frame with the smallest counter value
is selected. In case of a tie. FIFO is used to break the tie.”
In general, for a process with m frames (initially all empty) assume a page
reference string of length p, with n distinct page numbers occurring in it.
49. What is a lower bound on the number of page faults ?
(A) p page faults (B) n page faults
(C) m page faults (D) p/m page faults
50. What is an upper bound on the number of page faults ?
(A) n page faults (B) n * m page faults
(C) p page faults (D) p/m page faults
21 [P.T.O.
Text of page 22
FEB - 37313/III
Suppose that for a particular process under execution, the following page reference
string is encountered :
1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 4, 2.
51. How many page faults occur for “FIFO Page Replacement Algorithm” for the
above given page reference string for four frames ?
(A) 11 page faults (B) 20 page faults
(C) 16 page faults (D) 13 page faults
52. How many page faults occur for “LRU Page Replacement Algorithm” for the
above given page reference string for four frames ?
(A) 11 page faults (B) 10 page faults
(C) 13 page faults (D) 18 page faults
53. How many page faults occur for “Optimal Page Replacement Algorithm” for
the above given page reference string for four frames ?
(A) 11 page faults (B) 13 page faults
(C) 15 page faults (D) 17 page faults
54. How many page faults occur for “Best CBPR Algorithm” for the above given
page reference string for four frames ?
(A) 09 page faults (B) 10 page faults
(C) 14 page faults (D) 12 page faults
22
Text of page 23
FEB - 37313/III
Data to answer the questions numbered 55 to 58 below :
1 2 3 4
5 6
8 9
7 10
12 13
11 14
15 16
17 18 19 20
Rangoli graph
55. Definitions :
At any instant, dynamicDegree of a node is the number of untraversed edges
that meet at the node.
Heuristic H1 : Among the adjacent nodes, select the one that has the least
non-zero dynamicDegree count. (If there is more than one such node, select
any one of them.)
Heuristic H2 : Visit the selected node by traversing the corresponding edge.
Procedure TraverseRangoli : Begin at Node 1. Keep following H1 and H2
alternately.
Which of the following is true about TraverseRangoli ?
(A) Does not terminate
(B) Traversal is effectively a DFS
(C) Equivalent to the A* algorithm
(D) Generates an AND-OR graph
23 [P.T.O.
Text of page 24
FEB - 37313/III
56. If you employ TraverseRangoli, what is the minimum number of backtrackings
in order to traverse each edge of the Rangoli graph at least once ?
(A) 8 (B) 7
(C) 6 (D) 4
57. Modified heuristic NewH1 : Among the adjacent nodes, select the one that has
the greatest degree. (If there is more than one such node, select any one of
them.)
Procedure NewTraverseRangoli (i) : Begin at Node i. Keep following New H1
and H2 (as in Q. 56) alternately.
Let the cost of traversing one edge be 1 unit.
Which of the following is true about NewTraverseRangoli ?
(A) The cost of reaching Node j from Node i is the same as that of reaching
Node i from Node j.
(B) Starting with Node 5, and without revisiting Node 5 on the way, the cost
of reaching Node 3 is 4, 10 or 16 units for three different paths.
(C) Irrespective of the starting point, NewTraverseRangoli visits at most one
among the four Nodes numbered 1, 4, 17 and 20.
(D) Starting with a Node having degree 4, one can reach back to the same
node in 4 ways without revisiting any of the nodes on the way.
24
Text of page 25
FEB - 37313/III
58. An arbitration mechanism is added to modify NewH1, therefore :
Modified Heuristic NewerH1 : Among the adjacent nodes, select the one with
the greatest degree. Choose the one that has largest label, i.e., Node number,
in case there is more than one such node.
Modified Heuristic NewerH2 : Visit the selected node by traversing the
corresponding edge provided the edge has not been traversed before.
Correspondingly,
Procedure NewerTraverseRangoli (i) : Begin at Node i. Keep the following
NewerH1 and NewerH2 alternately.
Which of the following is true about NewerTraverseRangoli ?
(A) NewerH1 uniquely defines a path to visit all four Nodes of degree 4.
(B) NewerH2 ensures that the path does not involve any cycle.
(C) Both (A) and (B)
(D) Neither (A) nor (B)
Teacher
59. Teacher ⇔ ATRANS ← Chocolate most appropriately
Bablu
represents :
(A) Bablu gives Chocolate to Teacher
(B) Teacher takes Chocolate from Bablu
(C) Both (A) and (B)
(D) Neither (A) nor (B)
25 [P.T.O.
Text of page 26
FEB - 37313/III
60. Teacher ⇔ MBUILD ← Teacher ⇔ LOVE ← Bablu is to represent :
(A) Teacher understands that she loves Bablu
(B) Teacher understands that Bablu loves her
(C) Bablu understands that Teacher loves him
(D) Bablu understands that he loves Teacher
61. The number of states in the minimal state DFA, where the transition diagram
is given as follows, are :
b
a, b
q0 a q1 a, b q2
b a
b
b
q3 a q4 q5
a
b
(A) 2 (B) 3
(C) 4 (D) 5
26
Text of page 27
FEB - 37313/III
62. Match the following :
(a) Matching Parenthesis (1) P : {S → aSb|bSa|ε}
(b) Palindromes (2) P : {S → SS|aSa|bSb|ε}
(c) Expressions (3) P : {S → aSa|bSb|a|b|ε}
(c) Matching count (4) P : {S → SaS|SbS|c|d}
(A) (a)—(2), (b)—(1), (c)—(4), (d)—(3)
(B) (a)—(2), (b)—(3), (c)—(4), (d)—(1)
(C) (a)—(1), (b)—(2), (c)—(3), (d)—(4)
(D) (a)—(1), (b)—(3), (c)—(4), (d)—(2)
63. Which of the following pairs have different expressive power ?
P Deterministic Finite Automata (DFA) and Non-Deterministic Finite
Automata (NFA)
Q Deterministic Pushdown Automata (DPDA) and Non-Deterministic
Pushdown Automata (NPDA)
R Single Tape Turing Machine and Multi-tape Turing Machine
S Turing Machine and Two Stack Pushdown Automata
T Single Stack Pushdown Automata and Two Stack Pushdown Automata
(A) Q, R, S and T (B) Q and S
(C) Q and T (D) All of these
27 [P.T.O.
Text of page 28
FEB - 37313/III
64. A channel has two input and output symbols {0, 1} and a common probability
p of incorrect decoding of an input at the output. The channel is :
(A) binary symmetric channel (B) discrete memoryless channel
(C) burst channel (D) binary asymmetric channel
65. When an error-detecting code with even parity check is used, 101101 will be
transmitted as :
(A) 101100 (B) 101101
(C) 1011011 (D) 1011010
66. Elimination of which redundancy will lead to loss of quantitative
information ?
(A) Coding redundancy
(B) Interpixel redundancy
(C) Psychovisual redundancy
(D) Coding and interpixel redundancy
Information for Question Nos. 67 and 68 :
Consider the following problem :
Hardbrick Company has two kilns. Kiln-I can produce 3000 grey bricks,
2000 red bricks and 300 glazed bricks daily. For Kiln-II the corresponding
figures are 2000, 5000 and 1500. Daily operating costs of Kiln-I and Kiln-II
are Rs. 4,000 and Rs. 6,000 respectively. Find the number of days of operation
for each kiln so that the operation cost incurred in meeting an order of 9000
grey, 17000 red and 4500 glazed bricks is minimized.
Let x1 and x2 be the number of operation days for Kiln-I and Kiln-II
respectively.
28
Text of page 29
FEB - 37313/III
67. The mathematical form of the above problem is :
(A) Minimize : 4000x1 + 6000x2
Subject to 3000x1 + 2000x2 ≥ 9000
2000x1 + 5000x2 ≥ 17000
300x1 + 1500x2 ≥ 4500
x1, x2 ≥ 0
(B) Minimize : 4000x1 + 6000x2
Subject to 3000x1 + 2000x2 = 9000
2000x1 + 5000x2 = 17000
300x1 + 1500x2 = 4500
x1, x2 ≥ 0
(C) Maximize : –4000x1 – 6000x2
Subject to 3000x1 + 2000x2 ≤ 9000
2000x1 + 5000x2 ≤ 17000
300x1 + 1500x2 ≤ 4500
x1, x2 ≥ 0
(D) None of the above
29 [P.T.O.
Text of page 30
FEB - 37313/III
68. The dual of the above problem is :
(A) Maximize Z′ = 9000y1 + 17000y2 + 4500y3
Subject to 3000y1 + 2000y2 + 300y3 ≥ 4000
2000y1 + 5000y2 + 1500y3 ≥ 6000
y1, y2 ≥ 0
(B) Maximize Z′ = 9000y1 + 17000y2 + 4500y3
Subject to 3000y1 + 2000y2 + 300y3 ≤ 4000
2000y1 + 5000y2 + 1500y3 ≤ 6000
y1, y2 ≥ 0
(C) Maximize Z′ = 9000y1 + 17000y2 + 4500y3
Subject to 3000y1 + 2000y2 + 300y3 = 4000
2000y1 + 5000y2 + 1500y3 = 6000
y1, y2 ≥ 0
(D) Maximize Z′ = –9000y1 – 17000y2 – 4500y3
Subject to 3000y1 + 2000y2 + 300y3 ≥ 4000
2000y1 + 5000y2 + 1500y3 ≥ 6000
y1, y2 ≥ 0
30
Text of page 31
FEB - 37313/III
69. Consider the following assignment problem. The cost matrix of assignments
of 4 jobs (J1, J2, J3, J4) on 4 machines (M1, M2, M3, M4) is given by :
J1 J2 J3 J4
M1 10 9 8 7
M2 3 4 5 6
M3 2 1 1 2
M4 4 3 5 6
An assignment of jobs on machines is as follows :
M1 → J3 M2 → J1 M3 → J4 M4 → J2
Which of the following is true about this assignments ?
(A) Given assignment is not feasible.
(B) Given assignment is feasible, but not optimal.
(C) Given assignment is feasible and optimal.
(D) The problem is degenerate and cannot be solved by Hugarian method.
70. Commonly used neuron activation functions are :
(I) Linear function
(II) Threshold binary function
(III) Sigmoid function
(IV) Hyperbolic Tangent function
(V) Gaussian function
Which functions have the good properties of being differentiable, monotonic
and bounded ?
(A) (I), (II) and (III) (B) (III) and (IV)
(C) (III), (IV) and (V) (D) (I), (II), (IV) and (V)
31 [P.T.O.
Text of page 32
FEB - 37313/III
71. There are five jobs {1, 2, 3, 4, 5} and the criteria to be applied are interestingness
of the job involved and the demands on time required to carry out the job.
The two fuzzy sets are given as follows :
.7 .3 .5 .3 .4
InterestingJob = + + + +
1 2 3 4 5
.4 .8 .4 .3 .7
DemandingJob = + + + +
1 2 3 4 5
The fuzzy set for the job that is interesting but not demanding is given
by :
.7 .8 .5 .3 .7 .4 .3 .4 .3 .4
(A) + + + + (B) + + + +
1 2 3 4 5 1 2 3 4 5
.6 .2 .5 .3 .3 .3 .7 .5 .7 .6
(C) + + + + (D) + + + +
1 2 3 4 5 1 2 3 4 5
72. Crisp sets follow certain good properties some of which are given below :
(I) DeMorgan’s law
(II) Law of excluded middle
(III) Involution
(IV) Idempotency
(V) Law of contradiction
(VI) Commutativity
Fuzzy sets follow all these properties, except :
(A) (I), (II) and (III) (B) (II) and (V)
(C) (III) and (IV) (D) (II) and (III)
32
Text of page 33
FEB - 37313/III
73. The ‘touch’ command on UNIX system :
(A) Creates a new file without opening it
(B) Creates a new file after opening it
(C) Creates a new file by opening and closing it immediately
(D) Creates a new file by renaming an old file
74. The following is the source code corresponding to a ‘bash’ shell script ‘s1.sh’
in UNIX system;
echo “$0 $# $* $1 $2”
What will be the output if ‘s1.sh’ is executed from the console as follows :
$sh s1.sh sh s1.sh
(A) s1.sh 2 sh s1.sh
(B) s1.sh 2 sh s1.sh sh
(C) s1.sh 2 sh s1.sh sh s1.sh
(D) Displays an error message
75. Which of the following statements is most appropriate ?
(A) MFC programming can be done through C language.
(B) MFC programming can be done through C++ language.
(C) MFC programming can be done through C and C++ languages.
(D) MFC programming can be done through any language.
33 [P.T.O.
Text of page 34
FEB - 37313/III
ROUGH WORK
34Official key not published for this paper.
Page 1 of 34
Source: Savitribai Phule Pune University. Question paper published by Savitribai Phule Pune University.