CS 3333 Spring 2012. Final
CS 3333 Mathematical Foundations of CS. FinalPage 1/10
Final / 2.5 Hours
No books or notes, except the supplied formulas sheet, may be used. Calculators are allowed. Answer all questions in the spaces provided. For problem solving questions, be sure to indicate the major steps and the final answer.
Some results on counting
- There are -combinations of distinct elements, is a positive integer and is a nonnegative integer, when repetitions of elements are allowed.
- The number of permutations of objects, where there are indistinguishable objects of type 1, indistinguishable objects of type 2, ..., and indistinguishable objects of type k, such that and are nonnegative integers, is.
- The number of ways to distribute distinguishable objects into distinct boxes so that objects are placed in box , where and are nonnegative integers, is.
- The number of ways of placing indistinguishable objects in distinguishable boxes, where is a nonnegative integer and is a positive integer, is .
- Generalized principle of inclusion-exclusion (PIE): Let be n sets.
PART I
1.(2 points) Let a, b, c and d be integers and a ≠ 0, b ≠ 0. Prove, or give a counterexample, that if a | b and b | c, then a | c.
2.(1 point) State the division algorithm.
3.(2 points) Find the smallest positive integer such that .
4.(2 points) and , what is ______
5.(2+2=4 points) (a) Use Euclidean algorithm to find (b) Find integers x and y such that
6.(2 points) Find the sequence of pseudorandom numbers described by the recursion with seed value .
7.(2 points) Let A, B and C be matrices of sizes , respectively. What is the most efficient way to calculate the product ABC, as (AB)C or A(BC)?Give the number of multiplications required in each case.
8.(3 points) Change the decimal number 150814 to binary, octal and hexadecimal forms.
9.(1 point) If, does A-1 exist? Justify.
10.(3 points) Describe the three elementary row operations on a matrix.
11.(4 points) Let A be a nonsingular matrix and |A| = 3. Let 03 denote a null matrix.
a. What is |A-1|?
b. If B be the matrix obtained by interchanging rows 2 and 3. What is |B|?
c.What is |At|?
d. What is |04- A|?
12.(2 points) Find the inverse of .
PART II
13.(3 points) A restaurant has 6 varieties of sandwiches, 5 kinds of side items, and 7 kinds of sodas.
a. How many distinct ways are there to have a meal consisting of one sandwich, twodifferent kinds of side items and one soda?
b. How many ways are there to have exactly two items—each of a different type (e.g., one sandwich and one soda)?
c. How many ways are there to have two items (not-necessarily different) of one variety (e.g., two sandwiches or two sodas)?
14.(3 points) State the generalized pigeonhole principle and prove it.
15.(2 points) Suppose every person in our class of 21 students is either a sophomore, junior or senior. Show that there are at least 10 sophomores, at least 6 juniors, or at least 6 seniors.
16.(2 points) What is the number of ways to seat 10 men and 12 women in a row of 22 seats such that
a. no two men are together? ______
b. no two women are together? ______
17.(2 points) The following questions deal with bit strings of length 18.
a. How many bit strings have exactly six 1s and none of these 1s is adjacent to another?
b. How many bit strings begin with 11110 or end with 011? ______
18.(1 point) What is the coefficient of the in the expansion of ? ______
19.(3 points) Give a combinatorial proof for Pascal’s Identity.
20.(2 points) Consider the permutations of the letters of the word HELLODOLLY.
a)How many distinct strings can be made using all 10 letters? ______
b)How many of these permutations start with the substring ‘LO’? ______
21.(1+1+1+2 = 5 points) Count the number of 20-bit strings with the following properties.
a. Bit strings that start with 111 or 000? ______
b. Bit strings that have a 11 right in the middle? ______
c. Bit strings that have more 1s than 0s? ______
d. Bit strings that have exactly four 1s and none of them adjacent to one another? ______
22.(1 point) What is the number of terms in the expansion of (1+a+b+c)18? ______
23.(3 points) Find the number of solutions to , if
(a) x, y, and z are nonnegative integers.
(b) x, y, and z are nonnegative integers,.
PART III
24.(2 points) In a word game, you choose 6 letters at random (without replacement) from the 26 distinct letters of the alphabet – A, B, C, …., Z. The order of picking does not matter.
a)Find the probability that the letters chosen could be arranged to form the word BASKET. ____
b)What is the probability that none of the chosen letters is a vowel (A,E,I,O,U)? ______
25.(1 point) If two books are picked at random from 20 distinct math books and 8 distinct science books, what is the probability of picking one math and one science book?
26.(2 points)
a. What is conditional probability?
b. What must be true for two events A and B in the sample space of a random experiment to be independent?
27.(3 points) Suppose X and Y are events in a sample space with P(X) = 1/2, and P(Y) = 1/3, and P(X∩Y) = 1/6.
(a) Are X and Y independent events? Justify.
(b) Are X and Y mutually exclusive events? Justify.
(c) Calculate P(X | Y).
28. (4 points) A random experiment consists of tossing a fair coin 4 times and counting the number of times a head comes up. Let X be the random variable for this experiment.
a)What are the values that X takes on?
b)What is P(X=5)?
c)What is P(X 2)?
d)What is P(X is even)?
29.(4 points) A letter is chosen at random from among the letters in the word “quartile”. Let event X = {l, i}, event Y = {q, u, a, t}, event Z = {l, q, t}, and event V = {a, e, i ,u}.
a)What is P(X) ?
b)What is P(X | V) ?
c)What is P(V | X) ?
d)What is P(ZY) ?
30.(up to 5 points) Make up an interesting, non-trivial problem reflecting the mathematics discussed during the course. Solve it.
BONUS: Take any positive integer (base 10) of any length satisfying the following conditions:
a)From left to right, the digits are monotonically increasing (i.e., ).
b)The last two digits are different (i.e.,).
Show that the digit sum of is always exactly 9.
As an example, 133448 is a satisfactory starting number, which when multiplied by 9 gives you 1201032, whose digit sum is 1+2+0+1+0+3+2 = 9.