Computer Science Engineering - Online Test
Q1. Consider the relational schema given below, where eId of the relation dependentis a foreign
key referring to empId of the relation employee. Assume that every employee has at least one
associated dependent in the dependent relation.
employee (empId, empName, empAge)
dependent (depId, eId, depName, depAge)
Consider the following relational algebra query
The above query evaluates to the set of empIds of employees whose age is greater than that of
Answer : Option D
Explaination / Solution:
Part A of the above given relational algebra query will give the set of empIds of those
employees whose age is less than or equal to the age of some of his/her dependents.
Now when set of empIds of all employees minus set of empIds obtained from part A is done,
then we get the set of empIds of employees whose age is greater than that of all of his/her
dependents.
Q2. Which one of the following statements is NOT correct about HTTP cookies?
Answer : Option B
Explaination / Solution:
(A) is correct 
(B) Option B is false
(C) Option C is correct
(D) Option D is correct
Q3. A sender S sends a message m to receiver R, which is digitally signed by S with its
private key. In this scenario, one or more of the following security violations can take
place.
I. S can launch a birthday attack to replace m with a fraudulent message.
II. A third party attacker can launch a birthday attack to replace m with a fraudulent
message.
III. R can launch a birthday attack to replace m with a fraudulent message.
Which of the following are possible security violations?
Answer : Option B
Explaination / Solution:
Sender can launch a Birthday Attack to replace with fraudulent message, because he has the
signature and he can decrypt the signature by his own public key and gets the hash value.
With that same hash value, he can create another message and can be sent instead of original.
Hence option(B) is correct.
Q4. When two 8-bit numbers A7....A0 and B7.....B0 in 2’s complement representation (with A0 and B0 as the least significant bits ) are added using a ripple-carry adder, the sum bits
obtained are S7….S0 and the carry bits are C7….C0. An overflow is said to have occurred if
Answer : Option C
Explaination / Solution:
Overflow flag indicates an over flow condition for a signed operation. Some points to
remember in a signed operation:
* MSB is always reserved to indicate sign of the number.
* Negative numbers are represented in 2’s – complement.
* An overflow results in invalid operation.
2's complement overflow rules:
* If the sum of two positive numbers yields a negative result, the sum has- overflowed.
* If the sum of two negative number yields a positive result, the sum has overflowed.
* Otherwise, the sum has not overflowed.
Overflow for signed numbers occurs when the carry-in into the MSB (most significant bit) is
not equal to carry-out. Conveniently, an XOR-operation on these two bits can quickly
determine if an overflow condition exists.
Q5. Consider the virtual page reference string
1,2,3,2,4,1,3,2,4,1
on a demand paged virtual memory system running on a computer system that has main
memory size of 3 page frames which are initially empty. Let LRU, FIFO and OPTIMAL
denote the number of page faults under the corresponding page replacement policy. Then
Answer : Option B
Explaination / Solution:
FIFO
1 1 1 4 4 4
2 2 2 1 1 → (6) faults
3 3 3 2
Optimal
1 1 1 1 1
2 2 4 4 → (5) faults
3 3 2
LRU
1 1 1 4 4 4 2 2 2
2 2 2 2 3 3 3 1 → (9) faults
3 3 1 1 1 4 4
Optimal < FIFO < LRU
Q6. Consider the following languages
Which one of the following statements is FALSE?
Answer : Option D
Explaination / Solution:
Q7. Let Σ be a finite non-empty alphabet and let 2Σ* be the power set of Σ* . Which one of the following is TRUE?
Answer : Option C
Explaination / Solution:
2ε* is the power set of ε *
ε * is countabily infinite.
The power set of countabily infinite set is uncountable.
So 2ε* is uncountable, and ε * is countable
Q8. Consider the decision problem 2CNFSAT defined as follows:
{ φ | φ is a satisfiable propositional formula in CNF with at most two literal per clause}
For example, 
is a Boolean formula and it is in 2CNFSAT.
is a Boolean formula and it is in 2CNFSAT.The decision problem 2CNFSAT is
Answer : Option B
Explaination / Solution:
2 SAT is in P. This we can prove by reducing 2 SAT to directed graph reachability problem
which is known to be in P.
Procedure for reducing 2 SAT to reachability problem:
1. Let ϕ be CNF with clauses of length 2 and let P be the set of propositional
variables(literals) in ϕ
2. Build a graph G=(V,E) with V= P { p|p P} ∪ ¬ ∈ and (x, y E )∈ iff there is a clause in ϕ
that is equivalent to x y → (all the clauses are converted to equivalent implications and
the graph built is called as implication graph)
3. Observe that ϕ is unsatisfiable iff there is a p P ∈ such that there is both a path from p to
to ¬p and from ¬p to p in G.
This condition can be tested by running the reachability algorithm several times.
Q9. Consider six memory partitions of sizes 200 KB, 400 KB, 600 KB, 500 KB, 300 KB and 250
KB, where KB refers to kilobyte. These partitions need to be allotted to four processes of
sizes 357 KB, 210KB, 468 KB and 491 KB in that order. If the best fit algorithm is used,
which partitions are NOT allotted to any process?
Answer : Option A
Explaination / Solution:
Q10. Consider a TCP client and a TCP server running on two different machines. After completing
data transfer, the TCP client calls close to terminate the connectional and a FIN segment is
sent to the TCP server. Server-side TCP responds by sending an ACK which is received by
the client-side TCP. As per the TCP connections state diagram (RFC 793), in which state does
the client-side TCP connection wait for the FIN from the sever-side TCP?
Answer : Option D
Explaination / Solution:
No Explaination.
