Q. An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is   Solution: ...

Q. Consider the grammar given below: S → Aa A → BD B → b | ϵ D → d | ϵ Let a, b, d, and $ be indexed as follows: abd$3210 Compute the FOLLOW set of the non-terminal B and write the index values for the symbols in the FOLLOW set in the descending order. (For example, if the ...

Q. Which of the following protocol pairs can be used to send and retrieve e-mails (in that order)? (A) IMAP, POP3 (B) SMTP, POP3 (C) SMTP, MIME (D) IMAP, SMTP Ans: SMTP, POP3 Solution: SMTP is push protocol and send e-mail andPOP3 is pull protocol i.e. to retrieve e-mail.

Q. Which one of the following statements is NOT correct about the B+ tree data structure used for creating an index of a relational database table? (A) B+ Tree is a height-balanced tree (B) Non-leaf nodes have pointers to data records (C) Key values in each node are kept in sorted order ...

Q. Let 𝐺 be an undirected complete graph on 𝑛 vertices, where 𝑛 > 2. Then, the number of different Hamiltonian cycles in 𝐺 is equal to Ans: Option D Solution: A simple circuit in a graph G that passes through every vertex exactly once is called a Hamiltonian circuit. In Hamiltonian ...

Q. Consider the following two statements about database transaction schedules: Strict two-phase locking protocol generates conflict serializable schedules that are also recoverable. Timestamp-ordering concurrency control protocol with Thomas’ Write Rule can generate view serializable ...

Q. Let 𝐺 be an arbitrary group. Consider the following relations on 𝐺: 𝑅1: ∀𝑎, 𝑏 ∈ 𝐺, 𝑎 𝑅1𝑏 if and only if ∃𝑔 ∈ 𝐺 such that 𝑎 = 𝑔−1𝑏𝑔 𝑅2: ∀𝑎, 𝑏 ∈ 𝐺, 𝑎 𝑅2𝑏 if and only if 𝑎 = 𝑏−1 Which of the above is/are equivalence relation/relations? (A) 𝑅1 and 𝑅2 (B) 𝑅1 only (C) 𝑅2 only (D) ...

Q. Let 𝑋 be a square matrix. Consider the following two statements on 𝑋. 𝑋 is invertible. Determinant of 𝑋 is non-zero. Which one of the following is TRUE? (A) I implies II; II does not imply I. (B) II implies I; I does not imply II. (C) I does not imply II; II does not imply ...

Q. Consider Z = X – Y, where X, Y and Z are all in sign-magnitude form. X and Y are each represented in 𝑛 bits. To avoid overflow, the representation of Z would require a minimum of: (A) 𝑛 bits (B) 𝑛 − 1 bits (C) 𝑛 + 1 bits (D) 𝑛 + 2 bits Ans: 𝑛 + 1 bits Solution: Overflow can ...

Q. If 𝐿 is a regular language over Σ = {𝑎, 𝑏}, which one of the following languages is NOT regular ? (A) 𝐿 ⋅ 𝐿𝑅 = {𝑥𝑦 | 𝑥 ∈ 𝐿, 𝑦𝑅 ∈ 𝐿} (B) {𝑤𝑤𝑅 | 𝑤 ∈ 𝐿} (C) Prefix (𝐿) = {𝑥 ∈ 𝛴∗|∃𝑦 ∈ 𝛴∗ such that 𝑥𝑦 ∈ 𝐿} (D) Suffix (𝐿) = {𝑦 ∈ 𝛴∗|∃𝑥 ∈ 𝛴∗ such that 𝑥𝑦 ∈ 𝐿} Ans:{𝑤𝑤𝑅 | 𝑤 ∈ 𝐿} ...