#1
25th September 2014, 08:27 AM
| |||
| |||
JEST Exam Question Paper
Will you please provide the question paper of JEST Exam?
|
#2
25th September 2014, 10:35 AM
| |||
| |||
Re: JEST Exam Question Paper
Here is the list of few questions of JEST Exam which you are looking for . 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 di_er 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 tournament. 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 your 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. |
#3
26th September 2014, 09:47 AM
| |||
| |||
JEST Exam Question Paper
Will you please provide the Question Paper of the JEST Exam ?
|
#4
26th September 2014, 10:23 AM
| |||
| |||
Re: JEST Exam Question Paper
Here is the list of few questions of JEST Exam paper which you are looking for . 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 di_er 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 tournament. 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 your 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. |
|