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.
What is the number of swaps required to sort n elements using selection sort, in the worst case?

Q38.
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?

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?