Professor Callahan
Name: ________________________
NYU NetID: ____________________
3 points each
1. How many possibilities are there for the first, second, third and fourth positions in a car race with 12 cars if all orders of finish are possible?
*a. 11,880
b. 8027
c. 27330
d. 8360
2. The total number of strings of five decimal digits have exactly four digits that are 4s is...?
a. 36
b. 95
*c. 45
d. 544
3. Using a greedy algorithm to make change for 97 cents (assuming we only have .25, .10, .05, and .01 coins available), we would wind up employing:
a. Nine dimes, one nickel, and two pennies.
b. Three quarters, two nickels, and seven pennies.
c. Two quarters, four dimes, one nickel, two pennies
*d. Three quarters, two dimes, and two pennies.
4. In the English alphabet using only the 21 lowercase consonants, how many different three-letter initials with none of the consonant repeated can people have?
a. 9261
b. 63
*c. 7980
d. Around 2.03e21.
5. If you have 5 types of hats, 6 types of t-shirts, 3 types of jeans and 2 types of shoes available. How many different attires can you have from these possibilities choosing exactly one from each?
*a. 180
b. 16
c. 4
d. 720
6. You have 3 blue, 2 red and 5 green balls in a box. If you choose one ball randomly from the box, what is the probability that it is a blue ball ?
a. .2
*b. .3
c. .1
d .5
7. Tickets numbered 1 to 30 are mixed up and then a ticket is drawn at random. What is the probability that the ticket drawn has a number which is a multiple of 3 or 5?
a. 8/15
*b. 7/15
c. 4/15
d. 1/2
8. (2 points) The following statement is TRUE for what value of n?
Whenever n dogs and n cats are seated around a circular table there is always an animal both of whose neighbors are cats.
a. Even numbers
*b. Odd numbers
c. Numbers greater than 10
d. Negative numbers
9. (2 points) If there are 26 students in a class, on how many months were at least 3 students born?
a. 1
*b. at least 1
c. 2
d. at least 2
10. (2 points) In a series of 15 consecutive numbers, what is the minimum number of integers that will have the same remainder as another number when divided by 13?
a. 3
b. 6
c. 5
*d. 2
11. (2 points) A class has 530 students enrolled. In how many ways can all 530 students be put into 10 equal rows?
a. 10! * 530
*b. 530!
c. 530! * 10
d. (530 /10)!
12. (2 points) If f(x) = 1/x and g(x) = x, out of the following possible functions, which one is both the upper bound for f(x) and the lower bound for g(x)?
a. h(x) = log x
b. h(x) = x2
c. h(x) = x1/2
*d. Both a and c
13. Given a recurrence of the form T(n) = aT(n/b) + cn, what does ‘a’ signify?
a. The cost at each level in the recursion tree for T(n).
b. The cost of each leaf node in the recursion tree for T(n).
*c. The number of children for each node at every level in the recursion tree for T(n).
d. The total number of children at every level in the recursion tree for T(n).
14. The base case in any recurrence formula-
a. Is used to define the memory space needed by the program.
*b. Is the place where the recurrence finally ends and a definite value is returned.
c. Can be omitted.
d. All of the above.
15. How many terms are there in the expansion of (x + y)9 after like terms are collected?
*a. 10
b. 11
c. 5
d. 12
16. Given that T(n) = T(n - 2) + T(n - 3) and T(n) = 2 if n < 4, what is T(9)?
a. 8
b. 10
*c. 14
d. 18
17. There are 3 available subway lines from Jay Street to Wall Street and, regardless of which of these lines is taken, there are 6 lines from Wall Street to Grand Central Station. In how many ways can a person take the subway from Jay Street to Grand Central Station?
a. 8
b. 16
*c. 18
d. 32
18. Find the ninth term in the expansion of (a + b)11.
a. 462a5b6
b. 66a2b9
*c. 465a3b8
d. 11ab11
19. If f(x) = 6, then f(x) is (not restricting ourselves to the tightest bound):
a. O(1)
b. O(x)
c. O(x2)
*d. all of the above
20. If f(x) = 6, then f(x) is (restricting ourselves to the tightest bound):
*a. O(1)
b. O(x)
c. O(x2)
d. all of the above
21. Using the master theorem, give the big-Theta run time for the recurrence T(n) = 16T(n / 4) + n2:
a. n2
*b. n lg n
c. n lg n2
d. master method does not apply
21. Using the master theorem, give the big-Theta run time for the recurrence T(n) = .25T(n / .5) + n2:
a. n2
b. n lg n
c. n lg n2
*d. master method does not apply
22. If set A = {all integers} and set B = {all prime integers}, then the complement of B is:
a. all odd integers
b. all even integers
*c. all composite integers
d. all integers that are multiples of 3
23. What is the powerset of {7, 5, 9}?
a. {null-set, {7}, {5}, {9}, {7, 5, 9}}
b. {null-set, {7}, {5}, {9}}
c. {null-set, {7, 5, 9}}
*d. {null-set, {7}, {5}, {9}, {7, 5}, {7, 9}, {5, 9}, {7, 5, 9}}
24. What is the most significant problem with the recurrence T(n) = 2T(n / .5) + n lg n?
a. We can't solve it with the master theorem.
b. It has n lg n work at each level, which makes it closed form hard to compute.
*c. It will never finish.
d. The 2T means we have to call it twice at each level.
25. If the domain and codomain of f is the integers, then f(n) = n1/2 is:
a. an injective function
b. a surjective function
c. a bijective function
*d. not a function
6 points each
1. Explain why the formula for "choose" (a combination where we pick k items from n items and order does not matter) is C(n, k) = n! / (k!(n - k)!)
2. What is "discrete" about discrete mathematics? Use this fact to explain the difference between an analog and a digital computer.
3. Prove by induction that the sum of the first n odd integers = n2. (Hint: the n-th odd integer is (2n - 1). Remember you need to show a base case and prove the inductive step.)
4. The cardinality of the powerset of {a, b, c} is the same as the number of items in the third row of Pascal's triangle (1 3 3 1). This is not a coincidence. Please explain why these numbers are the same.