Joint Entrance Screening Test 2018 Theoretical Computer Science Sample Paper

Name of the Organization : Indira Gandhi Centre for Atomic Research
Exam : Joint Entrance Screening Test 2018
Document Type : Sample Question Paper
Category or Subject : Theoretical Computer Science
Website : https://www.jest.org.in/
Download Model Question Paper : https://www.pdfquestion.in/uploads/23164-tcs2017.pdf

Joint Entrance Screening Test Question

** Applicants seeking admission for a Ph.D / Integrated Ph.D Programme in Physics or Theoretical Computer Science or Neuroscience or Computational Biology in one of the Participating Institutes may appear for the Joint Entrance Screening Test (JEST) at one of the Exam Centers.

Related : Abhimanu IAS Test Series 2017 Sample Question Paper : www.pdfquestion.in/23153.html

Eligibility

** Participating Institutes have their own eligibility criteria.
** Applicants who are expected to complete their final examinations by August of each year are also eligible to appear for the JEST exam of that year.

Instructions

Please Read The Instructions Carefully :
1. Do not open the seal of the question paper before 10:00 AM.
2. You are given a question paper including a few blank sheets, and a machine readable Optical Mark Reader (OMR) sheet.

3. Enter your registration number on top of this question paper with black/blue pen.

4. Part A contains 15 questions, and carry 3 (three) marks each for correct answer, and -1 (negative one) mark for incorrect answer. Part B contains 10 questions and each carries 3 (three marks). These questions must be answered by integers of 4 digits each. Answer these questions on the OMR by filling in bubbles in the OMR sheet.

Note that if the answer is, e.g. 25, you must fill in 0025 and if it is, e.g. 5, you must fill in 0005. If it is 0, you must fill in 0000. If the zeros are not filled in (where required), the answer will be not be credited. There are NO NEGATIVE MARKS for these questions. Part C contains 25 questions, and each carries 1 (one) mark for the correct answer, and -1/3 (negative one third) mark for incorrect answer. Multiple choice questions have only one correct answer.

5. On the OMR sheet, enter the appropriate Question Booklet Series (X, Y or Z) that is mentioned on the top right of the question paper.

6. On the OMR sheet, enter your name, registration number, and signature at the appropriate places. Strictly follow the instructions written on the OMR sheet.
7. On the OMR sheet, completely darken the bubble corresponding to your answer. Strictly follow the instructions written on the OMR sheet.

8. Only non-programmable scientific calculator is allowed, and exchange of calculators among the candidates is not permitted. Use of other items like electronic diary, writing pads, pencil box, beeper, cameras, mobile phones, palmtops, laptops, pagers etc., are not permitted inside the examination hall.

9. For rough work, use only the blank pages attached at the end of the question paper.
10. At the end of the examination, carefully separate the OMR sheet at the marked position, and return the original copy of the OMR sheet to the invigilator. Candidates are allowed to take away the candidates’ copy of the OMR, and the question paper.

Theoretical Computer Science Sample Paper

** Joint Entrance Screening Test (JEST) is a preliminary screening test conducted jointly by several premier research institutes. Among these institutes, The Institute of Mathematical Sciences, Chennai is the only one that offers a Ph.D. programme in Theoretical Computer Science.
** There is no specified “portion” for the test; rather, the test is designed to check the applicant’s understanding of foundational aspects of computing.

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 representation, 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.

6. Two gamblers have an argument. The first one claims that if a fair coin is tossed repeatedly, getting two consecutive heads is very unlikely. The second, naturally, is denying this. They decide to settle this by an actual trial; if, within n coin tosses, no two consecutive heads turn up, the first gambler wins.

(a) What value of n should the second gambler insist on to have more than a 50% chance of winning?

(b) In general, let P(n) denote the probability that two consecutive heads show up within n trials. Write a recurrence relation for P(n).

(c) Implicit in the second gambler’s stand is the claim that for all sufficiently large n, there is a good chance of getting two consecutive heads in n trials; i.e. P(n) > 1/2. In the first part of this question, one such n has been demonstrated. What happens for larger values of n? Is it true that P(n) only increases with n? Justify our answer.

7. Consider the following program:
function mu(a,b:integer) returns integer;
var i,y: integer;
begin
———P———-
i = 0; y = 0;
while (i < a) do
begin ——–Q————
y := y + b ;
i = i + 1
end
return y
end
Write a condition P such that the program terminates, and a condition Q which is true whenever program execution reaches the place marked Q above.