1. We need to choose a team of 11 from a pool of 15 players and also select a captain.
The number of different ways this can be done is:
(a)C(15,11)
(b) 11 ·C(15,11)
(c) 15 · 14 · 13 · 12 · 11 · 10 · 9 · 8 · 7 · 6 · 5
(d) (15 · 14 · 13 · 12 · 11 · 10 · 9 · 8 · 7 · 6 · 5) · 11
2. You have two normal, fair, dice, with faces labelled 1,2,. . . ,6. If you throw both dice, which of the following is true about the total value shown by the dice?
(a) The probability that the total is 6 is less than the probability that the total is 9.
(b) The probability that the total is 6 is equal to the probability that the total is 9.
(c) The probability that the total is 6 is greater than the probability that the total is 9.
(d) None of the above.
3. A simple graph is one with no self-loops or multiple edges. Among the simple graphs with n vertices and at most 20n − 3 edges:
(a) There is always a graph with all vertices connected to at least 42 other vertices.
(b) For all such graphs the number of vertices connected to at least 42 other vertices
is at most cn for some constant c < 1.
(c) There are no graphs with each vertex connected to at most 38 other vertices.
(d) None of the above.
4.For integer values of n, the expression n(5n + 1)(10n + 1)/6
(a) Is always divisible by 5.
(b) Is always divisible by 3.
(c) Is always an integer.
(d) None of the above.
5. Consider the following functions f() and g().
f(){
w = 3;
w = 4; }
g(){
z = w;
z = z + 2*w;
print(z);
}
6. We start with w set to 0 and execute f() and g() in parallel—that is, at each step we either execute one statement from f() or one statement from g(). What is the set of possible values printed by g()?
(a) 0,9,12 (b) 0,8,9,12 (c) 0,6,8,9,11,12 (d) 0,4,6,9,10,12
7. Let G = (V, E) be a graph. Define H to be (V, F), where for all u, v ∈ V , (u, v) ∈ F if and only if (u, v) not in E. Then, which of the following is true:
(a) H is always connected.
(b) H is connected iff G is not connected.
(c) At least one of G and H is connected.
(d) G is not connected or H is not connected.
8. Let T be a tree on 100 vertices. Let n(i) be the number of vertices in T which have exactly i neighbors. Let s =1*n(1)+2*n(2)+...+100*n(100)
Which of the following is true?
(a) s = 99
(b) s = 198
(c) 99 < s < 198
(d) None of the above
The next two questions are based on the following program. In the program, we assume that
integer division returns only the quotient. For example 7/3 returns 2 since 2 is the quotient
and 1 is the remainder.
mystery(a,b){
if (b == 0) return a;
if (a < b) return mystery(b,a);
if (eo(a,b) == 0){
return(2*mystery(a/2,b/2));
}
if (eo(a,b) == 1){
return(mystery(a,b/2));
}
if (eo(a,b) == 2){
return(mystery(a/2,b));
}
if (eo(a,b) == 3){
return (mystery((a-b)/2,b));
}
}
eo(a,b){
if ((a/2)*2 == a and (b/2)*2 == b) return 0; end;
if ((a/2)*2 < a and (b/2)*2 == b) return 1; end;
if ((a/2)*2 == a and (b/2)*2 < b) return 2; end;
return 3;
}
9. mystery(75,210) returns
(a) 2 (b) 6 (c) 10 (d) 15
10. When a and b are n bit positive numbers the number of recursive calls to mystery on
input a, b is
(a) O(n) (b) O(log log n) (c) O(log n) (d) O(n^(1/2))