GATE PYQ

GATE CSE 2009

Q31.
The running time of an algorithm is represented by the following recurrence relation: T(n)=\left\{\begin{matrix} n & n\leq 3\\ T(\frac{n}{3})+cn& otherwise \end{matrix}\right. Which one of the following represents the time complexity of the algorithm?

Q32.
S\rightarrowaSa|bSb|a|b; The language generated by the above grammar over the alphabet {a,b} is the set of

Q33.
Consider the binary relation R = {(x,y), (x,z), (z,x), (z,y)} on the set {x,y,z}. Which one of the following is TRUE?

Q34.
Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)0(0+1)0(0+1)*?

Q35.
A hard disk has 63 sectors per track, 10 platters each with 2 recording surfaces and 1000 cylinders. The address of a sector is given as a triple (c,h,s), where c is the cylinder number, h is the surface number and s is the sector number. Thus, the 0^{th} sector is addressed as (0,0,0), the 1^{st} sector as (0,0,1), and so on The address (400, 16, 29) corresponds to sector number:

Q36.
A hard disk has 63 sectors per track, 10 platters each with 2 recording surfaces and 1000 cylinders. The address of a sector is given as a triple (c,h,s), where c is the cylinder number, h is the surface number and s is the sector number. Thus, the 0^{th} sector is addressed as (0,0,0), the 1^{st} sector as (0,0,1), and so on The address of the 1039^{th} sector is

Q37.
In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?

Q38.
What is the number of swaps required to sort n elements using selection sort, in the worst case?

Q39.
Which of the following statement(s) is/are correct regarding Bellman-Ford shortest path algorithm? P. Always finds a negative weighted cycle, if one exists. Q. Finds whether any negative weighted cycle is reachable from the source.

Q40.
Consider the following relational schema: Suppliers(sid:integer, sname:string, city:string, street:string) Parts(pid:integer, pname:string, color:string) Catalog(sid:integer, pid:integer, cost:real) Consider the following relational query on the above database: SELECT S.sname FROM Suppliers S WHERE S.sid NOT IN (SELECT C.sid FROM Catalog C WHERE C.pid NOT (SELECT P.pid FROM Parts P WHERE P.color<> 'blue')) Assume that relations corresponding to the above schema are not empty. Which one of the following is the correct interpretation of the above query?