Question Papers of JEST

Will you please provide me the Theoretical Computer Science question paper of JEST ?

[Kiran Chandar]

JEST is Joint Entrance Screening Test, you want the JEST question paper of Theoretical Computer Science, so I am giving you some questions of that paper :

1. Select the correct alternative in each of the following:
(a) Let a and b be positive integers such that a > b and a2 − b2 is a prime number.
Then a2 − b2 is equal to
(A) a − b (B) a + b (C) a × b (D) none of the above
(b) When is the following statement true? (A [ B) \ C = A \ C
(A) If ¯ A \ B \ C = (B) If A \ B \ C =
(C) always (D) never
(c) If a fair die (with 6 faces) is cast twice, what is the probability that the two
numbers obtained differ by 2?
(A) 1/12 (B) 1/6 (C) 2/9 (D) 1/2
(d) T(n) = T(n/2) + 2; T(1) = 1
When n is a power of 2, the correct expression for T(n) is:
(A) 2(log n + 1) (B) 2 log n (C) log n + 1 (D) 2 log n + 1

2. Consider the following function, defined by a recursive program:
function AP(x,y: integer) returns integer;
if x = 0 then return y+1
else if y = 0 then return AP(x-1,1)
else return AP(x-1, AP(x,y-1))
(a) Show that on all nonnegative arguments x and y, the function AP terminates.
(b) Show that for any x, AP(x, y) > y.

3. How many subsets of even cardinality does an n-element set have ? Justify answer.

4. A tournament is a directed graph in which there is exactly one directed edge between
every pair of vertices. Let Tn be a tournament on n vertices.
(a) Use induction to prove the following statement:
Tn has a directed hamiltonian path (a directed path that visits all vertices).
(b) Describe an algorithm that finds a directed hamiltonian path in a given tourna-
ment. Do not write whole programs; pseudocode, or a simple description of the
steps in the algorithm, will suffice. What is the worst case time complexity of
your algorithm?

5. Describe two different data structures to represent a graph. For each such representa-
tion, specify a simple property about the graph that can be more efficiently checked
in that representation than in the other representation. Indicate the worst case time
required for verifying both of your properties in either representation.