0 ratings 0% found this document useful (0 votes) 22 views 16 pages DU MS Spring 2021 Question
The document outlines the Master of Science Admission Test for the University of Dhaka's Department of Computer Science and Engineering, consisting of 50 questions worth 150 marks in total. It includes various topics such as probability, propositional logic, algorithms, programming, and computer architecture. Each question is designed to assess the knowledge and understanding of candidates in computer science concepts.
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content,
claim it here .
Available Formats
Download as PDF or read online on Scribd
Go to previous items Go to next items
Save DU MS Spring 2021 Question For Later University of Dhaka
Department of Computer Science and Engineering
Master of Science Admission Test, 2021
Time: 2 Hours Total Marks: 50 x 3 = 150
Answer alll the following 50 questions, each of which is worth three points.
No marks will be deducted for wrong answers.
1. Suppose it's election season, and the chosen president may or may not be the Green Party candidate.
Pundits believe that Green Party presidents (G) are more likely to legalize terror (T) than candidates from
other parties, but legalization could occur under any administration. Armed with the power of probability,
the analysts model the situation with the Bayesian Network given below.
Green party
president elected
Terror Legalize
What is the marginal probability of “Terror Legalize”?
+g |-8
Pr(G) [01 [0.9
Pr(+t|G) | Prt] G)
0.667 0.333
0.25 0.75
A. 0.667 B. 0.708
c. 0.292 D. 0.917
2. Let’s consider the following propositions
P=“It rained last night”
Q="The sprinkler came on last night”
R=“The lawn was wet this morning”
‘Now, for the following sentence:
“If the lawn was not wet this morning, it didn’t rain last night, and the sprinkler didn’t come on last
night’s,
which one of the following is the correct propositional logic expression?
A R>PV-Q B. “PA Q=-R
Cc. PA-Q>-R D. None of the above 3. The diagram given below depicts the cost of travelling between cities where the nodes are cities, the edges
are the roads between the cities and weight of the edges are the cost to travel along the roads.
Using Uniform Cost Search algorithm, what is the generated path and path cost for a vehicle travelling
from $ to G?
A. S-A-B-G, 10 B, S-C-B-G, 13
C. S-A-C-D-B-G, 15 D. S-A-C-D-B-G, 12
4. A genetic algorithm is used to evolve a binary string of length n into one string where the sum (from left
to right) of the last 3 genes is equal to 2. The initial population is a randomly generated set of binary
strings of length n, such as those shown here:
00110001
01011101
10101111
Which one of the following is a suitable fitness function for this problem?
A. Y(D&C) = 2, where D is a sample of the population and C is a constant with value 7, “&” is a
“bitwise and” operator.
B. Y(D|C) = 2, where D is a sample of the population and C is a constant with value 7, “|” is a
“bitwise or” operator.
€. LD &C) = 2, where Disa sample of the population and C is a constant with value (11100000),
“&” is a “bitwise and” operator.
D. E(D|C) = 2, where D is a sample of the population and C is a constant with value (11100000),
“> is a “bitwise or” operator.
Page 2 of 16 5. What will be the output of the following C program?
#include
void swap(int x, int y){
int temp;
temp
x
a
)
int main(){
int a = 10,
swap (a,b);
printg("8d,
return 0;
7
yi
temp;
= be =5e
ad", a, bi:
‘A, (555 B.
£. 5,10 D,
10, 10
10,5
A system admin was trying to debug a network performance issue from his terminal to a remote end (ip:
104.80.48.128). First he ran the traceroute command (see the output below --- first 4 lines and last few
lines were stripped)
5 103.12.172.221 2.618 ms 1.931 ms
6 103.12.172.201 3.165 ms 2.394 ms
7 103.16.155.89 3.042 ms 3.577 ms 4
8 103.16.152.82 11.824 ms 11.387 ms
9 128.241.9.182 52.214 ms
128.241.9.150 61.002 ms 65.201 ms
10 129.250.2.241 51.563 ms
129.250.2.123 52.525 ms
129.250.2.241 52.540 ms
11 129.250.5.62 67.884 ms
129.250.5.66 67.407 ms
129.250.5.62 65.257 ms
12 180.87.108.162 67.808 ms 67.074 ms
13 180.87.108.193 68.038 ms 66.854 ms
14 120.29.215.36 77.437 ms 66.602 ms
180.87.96.44 67.697 ms
15 180.87.96.22 66.413 ms 66.480 ms
16 180.87.15.6 104.782 ms 98.904 ms *
ips +
18 14.141.24.210 109.189 ms 107.849 m
19 ***
20 ***
Page 3 of 16
2.746 ms
2.628 ms
+204 ms
12.266 ms
83.389 ms
66.947 ms
67.455 ms
is * What is the initial value of the TTL field in the packet #14?
Al B, 255
C14 D. 28
7. Ina local area network using CSMA/CD as its access method, which of the following is an appropriate
description concerning the transmission operation performed by a network node?
‘A. All nodes are connected in a ring topology, B. Each node checks if the transmission
and a special frame is sent around to control ‘medium is in use, and can transmit data if
@ transmission right. Only the node that not in use. If a conflict is detected,
receives it can transmit data. retransmission is done after a random time
interval
C. Bach node is assigned a logical priority, and. ‘Only nodes that have been assigned a time
a transmission right is passed along in order slot for transmitting data can transmit data.
of priority. Only the node with the right can
transmit data,
8. Consider a TCP session in its slow start phase. The packets numbered 1-9 are currently at the source.
cwnd = 1 packets-> 123456789
The slow start threshold (ssthresh) is 4 packets and the initial congestion window, cwnd is 1 packet.
What will be the size of cwnd (in packets) when the acknowledgement for packet 3 is received at the
source?
ACSI B. 2
Cra) D4
9. How many solutions exist for the following congruence equation?
‘9x =6 (mod 15)
A4 BO3
Cn DI
10. What will be the output of the following C program?
#include
int main() {
int a= 5, *p;
int ¢[2] = (20, 25};
prc
a= “ptt;
print£("8d, $d", a, *p)?
return 0;
Page 4 of 16 A. 20,21 B, 20,25
Gazal D. 5,25
11. What will happen if we run the following Java program?
public class Example {
public static void main(String[] args) {
int a[] = new int(10];
a[20] = 100;
System. out.print1n("Hello") ;
A. Run-time exception B. Compile-time error
E. Itwill print the string: Hello D. Logic Error
12. Consider a two-dimensional array A[2][3] = {{1,2,3}, {4, 5, 6}}- Suppose in an intelligent simulation
system, each pass involves reading A in row order and writing back to A in column ordet. For example,
after the first pass the value of A is {{1,3,5}, {2,4,6}}. Now, which is the value of A after 101 passes?
AL A= {{12,3}, {45,63} B. A={{1,3,5}, (2,4,6}}
C. A= {115.4}, 13,2,6}} D. A= {{1,4.2}, (5,3,6})
13. Below is the list of processes P1, P2, P3, and P4 and their burst times for CPU scheduling algorithms.
Process Burst time (millisecond)
PL 9
P2 5
P3 7
Pa 4
Which of the following combinations is the average waiting time in millisecond for a
First-Come-First-Serve (FCFS) scheduling and Shortest-Job-First (SJF) scheduling, given that the
processes arrive in the order P1, P2, P3, and P4, and the latency can be ignored? Note that the burst time is
the actual time required to complete a process.
|A. Average process waiting time under FCFS __B._Average process waiting time under FCFS
is 9.5 and average process waiting time is 9.0 and average process waiting time
under SIF is 6.25. under SIF is 7.0.
C. Average process waiting time under FCFS —_-D._Average process waiting time under FCFS
is 11.0 and average process waiting time is 11.5 and average process waiting time
under SIF is 7.25. under SIF is 8.0,
Page 5 of 16 14. Which of the following is the critical path of the project activities shown in the figure below?
Legend:
‘Activity name
Required number
of days
A-ASBoESISL B. A+C>D>ESHOK
C. ASCOFSISL D. AwC+G>JoL
15. An audio signal is sampled 11,000 times per second while each sample is recorded as an 8-bit data, When
a 512%106-byte capacity flash memory is used, what is the maximum number of minutes to record such
data?
A. 770 B. 96
©. 715 D. 969
16. “a + b” represents the fact that when the value of attribute a is determined, the value of attribute b is
determined uniquely. For example, “Employee number + Employee name” represents that when the
employee number is determined, the employee name is determined uniquely. Based on this notation, when
the relations between attributes a through j are established as shown in the figure below, which of the
following is an appropriate combination of three (3) tables that defines the relations in a relational
database?
=e
ere
Sn 0S
=
4 B,
Table 1 (a) Table | (a, 8, ¢,d,¢)
Table 2 (6, c,d, €) Table 2 (6,f.2, fi)
Table 3 fg, h i) Table 3 (e, 4.)
Page 6 of 16 Table I (a, bf, gh) Table 1 (a, c,d)
Table 2 (c, d) Table 2 (6, f.2, h)
Table 3 (¢, ,/) Table 3 (e, 4,/)
17. A CPU has a clock frequency of 2.0 GHz. When the instructions consist of three types as shown in the
table below, what is the approximate CPU performance in MIPS?
I Sear =e Bas wie lees asa or
[Type Execution time (clocks) | Frequency of
_ Instruction 1 = 15 40
Instruction 2 a 10 _| 20 _|
Instruction 3 10 40 |
A. 16.7 B. 120
Cc. 167 D. 177
18. Which of the following is an explanation of an absolute path name in a file system?
‘A. The path name from the current directory to. _-B._The path name from the home directory to
the target file the target file
C. The path name from the root directory to‘ D.The shortest path name among path names
the target file from a certain directory to the target file
19. Given below are an SQL statement, the “Product” table, the “Inventory” table. Note that the underlined
part indicates the primary key.
SELECT ProductNumber FROM Product
WHERE ProductNumber NOT IN (SELECT ProductNumber FROM Inventory)
Product
| ProductNumber | ProductName | UnitPrice
Inventory
WarehouseNumber | ProductNumber | InventoryQuantity
Which of the following SQL statements gives the same result as the SQL statement given above?
Page 7 of 16 SELECT ProductNumber FROM Product
WHERE EXISTS (SELECT ProductNumber FROM Product)
SELECT ProductNumber FROM Inventory
WHERE NOT EXISTS (SELECT ProductNumber FROM Product)
SELECT ProductNumber FROM Product
WHERE EXISTS (SELECT ProductNumber FROM Inventory
WHERE Product. productNumber = Inventory. ProductNumber)
SELECT ProductNumber FROM Product
WHERE NOT EXISTS (SELECT ProductNumber FROM Inventory
WHERE Product.ProductNumber = Inventory. ProductNumber)
20. Among Extreme Programming (XP) practices, which of the following is adopted to improve program
quality in program development through smooth communication between programmers by exchanging
their roles and checking each other’s work?
A. Agile Programming
C. Planning game
A. A method of memory management in
which multiple records are read and written
8 a block on an auxiliary storage
C. A method of memory management in
which the programs are relocated for
execution in a different area of the main
memory
Page 8 of 16
B. Pair programming
D. Test-driven development
21. Which of the following is an appropriate explanation of the paging method?
B. A method of memory management in
which the main memory is divided into
‘multiple areas so that reading and writing
can be performed simultaneously
D. A method of memory management in
which the virtual memory space and real
memory space are divided into fixed-length
blocks for management 22. A real-time operating system (OS) performs preemptive scheduling on a priority basis and schedules two
tasks A and B. When A has a higher priority than B, which of the following is an appropriate task
‘management by the real-time OS?
A. When 4 is launched during the execution of
B, Bis assigned a “ready” status and A
executed.
C. When B is launched during the execution of
A, A is assigned a “ready” status and B is
executed.
B. When 4 is launched during the execution of
B, B is assigned a “waiting” status and A is
executed,
D. When Bis launched during the execution of
A, A is assigned a “waiting” status and Bis
executed,
23. Consider the following finite automata:
If we want to minimize the above finite automata without affecting any of their properties, how many
states would the corresponding minimized finite automata have?
A4 B. 6
g.3 D. 5
24. Which of the following Context Free Grammar is not ambiguous?
B, S—raAalalAle
Asean
A. SAS|alb
ASS | ab
D. SaAblalAle
An eba
XC. B+E+E|E*E|(®)|xly|z
25. Cache memory is usually organized in multiple levels, such as LI for level 1 and L2 for level 2, with L1
having the smallest storage capacity but the fastest memory speed. The data in L1, L2, and main memory
can be accessed using 1, 10, and 100 clock cycles, respectively. When the cache miss rates in Ll and L2
are 5% and 50% respectively, what is the average memory access time in clock cycles?
A 28 B. 3.7
c. 37 D. 523
Page 9 of 16 26. Consider two one-dimensional arrays A and B of sizes m and n respectively. Each array contains unique
integer values sorted in ascending order. As shown in a sample figure below, these two arrays are merged
into a single one-dimensional array C. Which of the following is the appropriate order of the
computational complexity of this merge algorithm?
4: [3 6 [is lu
B: 7 S iL 18 20
Cc: 3 6 ¥ 9 i 15 17 18 20
A. O(m) B. O(n)
C. O(m +n) D. O(m *n)
27. Every address generated by the CPU is divided into two parts. Which are they?
A. Frame bit and page number B. Page number and page offset
C. Page offset and frame bit D. Frame ofiget and page offset
28. When the size of a still image is (1600 x 1200) pixels and each pixel has a 256-level gray scale ranging
from 0 to 255, approximately how many megabytes are needed at least to store five such still images?
A 2 B.4
c 10 D. 15
29. Which of the following is the appropriate RAID configuration that provides disk striping at the block level
rather than byte level and reserves one disk for parity information?
A. RAIDI B. RAID2
c. RAID3 D. RAID4
30. Suppose process PI and process P2 want to communicate via some Inter-Process Communication (IPC)
model. They want to share information among them via kernel intervention or system call. Which IPC
‘model should be chosen for this type of inter-process communication?
‘A. Shared-Memory Model B. Message Passing Model
C. Both Shared Memory and Message Passing D. None of these.
Model.
Page 10 of 16 31. Regarding matrix manipulation, which of the following is false?
[c*A,]
gives : e[C;]
A. We have a constant scalar'c’ and a matrix 'A'. Then multiplying 'c' with
B. The multiplication of two matrices of orders i*/ and j*# results into a matrix of order i*k.
ion only if the number of columns of the first
C. Two matrices will be compatible for multiplic
matrix and the number of rows of the second one are the same.
D. Transposition simply means interchanging the row and column index.
32. Consider the following snapshot of a system where maximum instances of resource types A, B, C and D
are 3, 14, 12 and 12, respectively.
Process Allocation Max. Available
A,B CoD *|A Bic D lA Bc D
PO OenOl eh 2 (0. 0 1 2 (165 - 210
Pl 10 0 50h (1 7 15 <0
P2 1 Opes Se 4 (2019-4 5 | 6
P3 Opn 3 22. (0 645 2
Pa Ope Oee eed eo|07 6) 5 9 6
If.a request from process P1 arrives for (0, 4, 2, 0), what will be the safe sequence?
A. PO, P2, P3, PI, P4 B. PI, P2,P4, P3, PO
C. Both D. None of them
33. The convergence of which of the following methods is sensitive to starting value?
A. False position B. Gauss Seidel Method
€. Newton-Raphson Method D. None of the above
34. If we flip a biased coin n times, what is the probability that we obtain exactly & heads if the flips are
independent and the probability of heads is p?
Ac pt(1-py™* B. pr(1-p)*
c= ny pb. ph"(1-py
Page 11 of 16 35. Consider the following joint probability distribution involving three binary random variables, namely
Accident, Drowsiness, and Jerking (~ means the respective variable is false, and true otherwise)
accident accident
Jerking | ~jerking | jerking | jerking
drowsiness 0.108 0.012 | 0.072 | 0.008
“drowsiness 0.016 0.064 | 0.144 | 0.576
Determine the following probability distribution: P (Jerking | drowsiness). Note that the vertical bar means
that the term on the right hand side is “evidence” or “given information”.
A. 0.468 B. 0.37
c. 047 D. 0.368
36. When 4-bit signed numbers in 2's complement are used, which of the following operations will cause
either an overflow or an underflow?
A. Add B to A when A is 0110 and B is 1111 B. Add B to A when A is 1110 and B is 0110.
C, Subtract B from A when A is 0111 and B is D. Subtract B from A when A is 1111 and Bis
1010. ii
37. A diagnostic test has a probability 0.95 of giving a positive result when applied to a person suffering from
a certain disease, and a probability 0.10 of giving a (false) positive when applied to a non-sufferer. It is
estimated that 0.5 % of the population are sufferers. Suppose that the test is now administered to a person
about whom we have no relevant information relating to the disease (apart from the fact that he/she comes
from this population). If the person is diagnosed as positive by the test, what is the probability that the
person has indeed the disease?
A. 0.1811 B. 0.4752
C. 0.5013 D. 0.9047
Page 12 of 16 38. A system composed of n separate components is said to be a parallel system if it functions when at least
‘one of the components functions properly (see the figure below). For such a system, if component i,
independent of other components, functions with probability p,, i= 1, 2, ..., 1, what is the probability that
the system functions properly?
Figure: Example of a parallel system that functions if current flows from A to B.
B.1-TG-p)
>. fap)
it
39. Suppose 63, 9, 19, 27, 18, 108, and 99 are inserted in an empty AVL tree sequentially. What will be the
depth of 19 in the constructed tree? Note: depth of the root node is zero.
AO B. 1
Ce? D. 3
40. Suppose f(x) = mx + by, g(x) = mx + by, where m, mz, b, and b, are constants. What is the slope of the
function flg(x))?
Alm a
Boon
Cc mm D. mmx
41. Suppose that a population y grows according to the logistic model given below:
L
tae
where y is the population at time ¢ (¢ > 0) and 4, k, and L are posi
increasing at time t= 0?
fe constants. At what rate is y
Lka
a+ay
A D. LkAe*
aray
Page 13 of 16 42. Consider a binary max-heap implemented using an array. Which one of the following arrays represents a
binary max-heap?
A. 25,12,16,13,10,8,14 B. 25,12,16,13,10,8,14
C. 25,14,16,13,10,8,12 D. 25,14,12,13,10,8,16
43. A B-tree of order 4 is built from scratch by 10 successive insertions. What is the maximum number of
node splitting operations that may take place?
AB B. 4
Gs) D. 6
44. When a series of data shown below is searched using the binary search algorithm, what is the minimum
‘number of comparisons needed to find a value of 5?
2,5, 15, 16,27, 27, 28, 40, 41, 51, 52, 55, 55, $7, 67, 79
Aad B. 2
G3 D. 4
48. Inorder and Preorder traversal of a Binary tree is given below:
Inorder: CSMEDAUOIN
Preorder: DESCMUAION
If each character represents a node, which of the following is the Postorder traversal of the binary tree?
A, DESMCAUION B. DESCMAUNO!
C. CMSEAONIUD D. CMSAEONUID
46. Suppose, x= -5,y=3 and 2=I1. Then what will the value of variable var after executing the following C
code segment?
int var = (x*((x*y) & -(-% < y)))+ (y*((r2*y) & =(z < yD
A -1 B. 2
ei D. 2
Page 14 of 16 47. For the following graph, how many vertices can be matched using maximum matching using « bipartite
graph algorithm?
Oa 6 o ©
Ae? B. 3
a4 D. 5
48. What will be the time complexity of the following code?
int foo(int x, int n){
if (n == 0)
return 1;
eu (ne== 1)
return x;
if ((n & 2) == 0)
return foo(x*x, n/2);
else
return foo(x*x, n/2) * x;
J
A. O(log n) B. O(n)
C. O(n logn) BD. O(n’)
Page 15 of 16 A. ({1,2},{3,2}, 145) B. ({1,0},{4,3},14,2))
C. (£1,2},(2,3),645}) D. ({1,3},14.3}.14,5})
50. Of the following given options, which one does not provide an optimal solution for the 8-queens problem?
A. (62,7,148,533) ” B. (4,1,5,8,6,3,7,2)
C. (1,6,3,8,3,2.4.7) D. (5,3.8,4,7,1,6,2)
Page 16 of 16
