Q. The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7}exactly once is Ans: 80 Sol: Set minimum element as root (i.e 1), now 6 are remaining and left subtree will have 3 elements, each left subtree combination can be permuted in 2! ways. Total ways to design min-heap with 7-elements = ^6C_3 *2! * 2! = 20*2*2 = 80 […]
Q. Consider the following program written in pseudo-code. Assume that x and y are integers. The number of times that the print statement is executed by the call Count(1024,1024) is_______. Ans: 10230
Consider the following program written in pseudo-code Read More »
Q. Consider Guwahati (G) and Delhi (D) whose temperatures can be classified as high (𝐻), medium (𝑀) and low (𝐿). Let 𝑃(𝐻𝐺) denote the probability that Guwahati has high temperature. Similarly, 𝑃(𝑀𝐺) and 𝑃(𝐿𝐺) denotes the probability of Guwahati having medium and low temperatures respectively. Similarly, we use 𝑃(𝐻𝐷), 𝑃(𝑀𝐷) and 𝑃(𝐿𝐷) for Delhi. The
Q. Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2, … , 100. There is an edge between vertices 𝑢 and 𝑣 if and only if the label of 𝑢 can be obtained by swapping two adjacent numbers in the label of 𝑣. Let
Q. Consider the following four relational schemas. For each schema, all non-trivial functional dependencies are listed. The underlined attributes are the respective primary keys. Schema I: Registration (rollno, courses) Field ‘courses’ is a set-valued attribute containing the set of courses a student has registered for. Non-trivial functional dependency: rollno ® courses Schema II: Registration (rollno,
Q. Consider the relations r(A, B) and s(B, C), where s.B is a primary key and r.B is a foreign key referencing s.B. Consider the query Q: 𝑟 ⋈ (𝜎𝐵<5(𝑠)) Let LOJ denote the natural left outer-join operation. Assume that r and s contain no null values. Which one of the following queries is NOT
Q. Consider the following solution to the producer-consumer synchronization problem. The shared buffer size is 𝑁. Three semaphores empty, full and mutex are defined with respective initial values of 0, 𝑁 and 1. Semaphore empty denotes the number of available slots in the buffer, for the consumer to read from. Semaphore full denotes the number
Consider the following solution to the producer-consumer synchronization problem Read More »
Q. In a system, there are three types of resources: E, F and G. Four processes P0, P1, P2 and P3 execute concurrently. At the outset, the processes have declared their maximum resource requirements using a matrix named Max as given below. For example, Max[P2,F] is the maximum number of instances of F that P2
Q. Consider the following parse tree for the expression a#b$c$d#e#f, involving two binary operators $ and #. Which one of the following is correct for the given parse tree? A. $ has higher precedence and is left associative; # is right associative B. # has higher precedence and is left associative; $ is right associative
Q. A lexical analyzer uses the following patterns to recognize three tokens T1, T2, and T3 over the alphabet {a,b,c}. 𝑇1: 𝑎? (𝑏|𝑐)∗𝑎 𝑇2: 𝑏? (𝑎|𝑐)∗𝑏 𝑇3: 𝑐? (𝑏|𝑎)∗𝑐 Note that ‘x?’ means 0 or 1 occurrence of the symbol x. Note also that the analyzer outputs the token that matches the longest possible prefix.
