CS GATE 2013 - Online Test
Q1. Using public key cryptography, X adds a digital signature σ to message M, encrypts , and sends it to Y, where it is decrypted. Which one of the following sequences of keys is
used for the operations?
Answer : Option D
Explaination / Solution:
Encryption: Source has to encrypt with its p r ivate key for formin g Digital signature for Authentication. source has to encrypt the <M, σ > with Y ' s
public key to send it confidentially
Decryption: Destination Y has to decrypt first with its private key, then decrypt using source public key
Q2. A computer uses 46–bit virtual address, 32–bit physical address, and a three–level paged page
table organization. The page table base register stores the base address of the first–level table
(T1) ,which occupies exactly one page. Each entry of T1 stores the base address of a page of the
second–level table (T2) Each entry of T2 stores the base address of a page of the third–level table
(T3) Each entry of T3 stores a page table entry (PTE). The PTE is 32 bits in size. The processor
used in the computer has a 1 MB 16 way set associative virtually indexed physically tagged cache.
The cache block size is 64 bytes.
What is the size of a page in KB in this computer?
Answer : Option C
Explaination / Solution:
Let the page size be 2x Bytes. 
Then, the page offset = X bits
Now, we are using 3-level paging. First level page table is contained in one page. Each page
table entry is 32-bit.
Q3. Three concurrent processes X, Y, and Z execute three different code segments that access and
update certain shared variables. Process X executes the P operation (i.e., wait) on semaphores
a, b and c; process Y executes the P operation on semaphores b, c and d; process Z executes
the P operation on semaphores c, d, and a before entering the respective code segments. After
completing the execution of its code segment, each process invokes the V operation (i.e.,
signal) on its three semaphores. All semaphores are binary semaphores initialized to one.
Which one of the following represents a deadlock-free order of invoking the P operations by
the processes?
Answer : Option B
Explaination / Solution:
Suppose X performs P(b) and preempts, Y gets chance, but cannot do its first wait i.e., P(b),
so waits for X, now Z gets the chance and performs P(a) and preempts, next X gets chance.
X cannot continue as wait on ‘a’ is done by Z already, so X waits for Z. At this time Z can
continue its operations as down on c and d. Once Z finishes, X can do its operations and so Y.
In any of execution order of X, Y, Z one process can continue and finish, such that waiting is
not circular. In options (A),(C) and (D) we can easily find circular wait, thus deadlock
Q4.
Consider the following relational schema.
Students(rollno: integer, sname: string)
Courses(courseno: integer, cname: string)
Registration(rollno: integer, courseno; integer, percent: real)
Which of the following queries are equivalent to this query in English?
“Find the distinct names of all students who score more than 90% in the course numbered 107”
(I) SELECT DISTINCT S.sname
FROM Students as S, Registration as R
WHERE R.rollno=S.rollno AND R.Courseno=107 AND R.percent>90
(II) 
(III) {T | ∃S∈ Students, ∃R∈ Registration (S.rollno = R.rollno ∧ R.courseno = 107 ∧ R.percent > 90 ∧ T.sname = S.name)}
(IV) 
Answer : Option A
Explaination / Solution:
Four queries given in SQL, RA, TRC and DRC in four statements respectively retrieve the
required information.
Q5. A computer uses 46–bit virtual address, 32–bit physical address, and a three–level paged page table organization. The page table base register stores the base address of the first–level table (T1) ,which occupies exactly one page. Each entry of T1 stores the base address of a page of the second–level table (T2) Each entry of T2 stores the base address of a page of the third–level table (T3) Each entry of T3 stores a page table entry (PTE). The PTE is 32 bits in size. The processor used in the computer has a 1 MB 16 way set associative virtually indexed physically tagged cache. The cache block size is 64 bytes.
What is the minimum number of page colours needed to guarantee that no two synonyms map to
different sets in the processor cache of this computer?
Answer : Option C
Explaination / Solution:
As the page size is 213 Bytes and page coloring is asked so we divide cache size by page
size and group 16 pages in one set.
Number of pages in cache=1MB/8KB=128 pages
Number of set in cache=128/16=8 sets
Take any page of LAS, it will be mapped with cache on any one of these 8 sets (set
association mapping).For any two synonym to map with same set they should be colored with
same color of that respective set. So minimum we need 8 colors for this mapping.
Q6. Which one of the following options is the closest in meaning to the word given below?
Nadir
Answer : Option B
Explaination / Solution:
Nadir in the lowest point on a curve
Q7. Which of the following statements is/are FALSE?
(1) For every non-deterministic Turing machine, there exists an equivalent deterministic
Turing machine.
(2) Turing recognizable languages are closed under union and complementation.
(3) Turing decidable languages are closed under intersection and complementation
(4) Turing recognizable languages are closed under union and intersection.
Answer : Option C
Explaination / Solution:
(1) NTM ≅ DTM
(2) RELs are closed under union & but not complementation
(3) Turing decidable languages are recursive and recursive languages are closed under
intersection and complementation
(4) RELs are closed under union & intersection but not under complementation
Q8. A shared variable x, initialized to zero, is operated on by four concurrent processes W, X, Y, Z as
follows. Each of the processes W and X reads x from memory, increments by one, stores it to
memory, and then terminates. Each of the processes Y and Z reads x from memory, decrements by
two, stores it to memory, and then terminates. Each process before reading x invokes the P
operation (i.e., wait) on a counting semaphore S and invokes the V operation (i.e., signal) on the
semaphore S after storing x to memory. Semaphore S is initialized to two. What is the maximum
possible value of x after all processes complete execution?
Answer : Option D
Explaination / Solution:
No Explaination.
Q9. Relation R has eight attributes ABCDEFGH. Fields of R contain only atomic values.
F = {CH → G, A → BC, B → CFH, E → A, F → EG} is a set of functional dependencies (FDs) so that F+ is exactly the set of FDs that hold for R
How many candidate keys does the relation R have?
Answer : Option B
Explaination / Solution:
Candidate keys are AD, BD, ED and FD
Q10. What is the maximum number of reduce moves that can be taken by a bottom-up parser for a
grammar with no epsilon- and unit-production (i.e., of type A → ∈ and A → a) to parse a
string with n tokens?
Answer : Option B
Explaination / Solution:
To have maximum number of reduce moves, all the productions will be of the typeA→αβ
(where α and β could be terminals or non-terminals). Consider the following illustration
then:
