CIS 66 Final Exam, Fall 2002

Friday December 20, 2002

2:00 – 4:00 P.M.

Name:
SSN:

Circle Instructor

Myra Wyse Robert Stafford

This exam consists of 12 questions. You must put a line through the two questions on this page that you do not want graded.

Question / Points / Out of
1 / 10
2 / 10
3 / 10
4 / 10
5 / 10
6 / 10
7 / 10
8 / 10
9 / 10
10 / 10
11 / 10
12 / 10
Delete 2
Total / 100


1. True or False (10 points)

a.  propositions: “If 1 + 1 = 3, then 1 + 1 = 2” is a tautology T or F

b.  propositions: $ x $ y Ø P(x,y) Û Ø ("y "x P(x,y)) T or F

c.  if (p«q) is a tautology, then pÛq T or F

d.  sets: {} Í {{}} T or F

e.  sets: (1, a) Í A ´ B where A = {1, 2}, B = {a, b} T or F

f.  If a, b, q, and r are integers and a = bq + r, then
gcd(a, b) = gcd(a, r) T or F

g.  The set S of negative even integers can be defined recursively
as -2 Î S, x + y Î S if x Î S and y Î S. T or F

h.  ë-7/5û = -2 T or F

i.  10 | 0 T or F

j.  if a|c and b|c, then ab|c T or F


2. Mostly True or False (10 points)

a.  propositions: for x Î R, y Î R, " x $ y (x*y=1) T or F

b.  sets: (AÇB) È C Û (AÈC) Ç (BÈC) T or F

c.  35 and 49 are relatively prime. T or F

d.  A problem that is solvable using an algorithm with polynomial
worst-case complexity is called tractable. T or F

e.  Intractable problems are unsolvable. T or F

f.  3x2 + 5x + 2 is O(2x) T or F

g.  The function f(n) = én/4ù from Z to Z (the integers) is a surjection T or F

h.  If events E and F in the sample space S are independent,
p(E | F) = p(F | E) T or F

i.  Convert 1001001 (base 2) to decimal. ______

j.  What is the probability that, when two dice are rolled,
the sum of the numbers on the two dice is 11? ______


3. How Many (10 points) The result must be a number, not a formula

a.  The bitwise result of ((0011)Ú(1010)) Ù (1010) ______
b.  The prime factorization of 10000. ______

c.  GCD(2*3*4, 4*5*6) ______

d.  If today is Friday (and it is), what day of the week will
it be 365 days from today? ______

e.  How many elements are in the set P({a, b}´{c, d, e})
where “´” represents the Cartesian product ______

f.  If an = an-1 - an-2 for n ³ 2, and a0=0, a1=5, what is a6? ______

g.  –22 mod 5 ______

h.  Convert 1001 (base 16) to decimal. ______

i.  If a single card is drawn from a deck of 52 cards, what is
the probability that it is either a 2 or a heart (or both)? ______

j.  How many ways can you elect a president, a vice-president
and a treasurer from a group of 5 students? ______

4 How Many (10 points) The answer must be a FORMULA, not a number

a.  How many different ways can a faculty member assign 5 grades
(A, B, C, D, F) to a class of 10 students.
______

b.  How many different ways can a faculty member assign 5 grades (A, B, C, D, F) to a class of 10 students if she insists on awarding 2 A’s, 2 B’s, 2 C’s, 2 D’s, and 2 F’s? ______
  1. How many solutions are there to the equation x1 + x2 + x3 + x4 + x5 = 23
    where x1 through x5 are nonnegative integers.
    ______
  2. How many solutions are there to the equation x1 + x2 + x3 + x4 + x5 = 23
    where x1 through x5 are nonnegative integers with x2 ³ 2 and x4 2?
    ______
  3. How many functions are there from a set with 20 elements (the domain) to a set with 10 elements (the codomain)?
    ______
  4. How many one-to-one functions (injections) are there from a set with 20 elements to a set with 10 elements?
    ______

g.  How many different ways can you distribute 12 different gifts to 6 people (a given person could get all 12 gifts or no gifts at all).
______

h.  How many different ways can you distribute 12 different gifts to 3 people if each person gets 4 of the gifts.
______

i.  How many ways are there to arrange the letters of the word “BUBBLE”.
______

  1. With the set {1, 2, 3, 4, 5, 6}, what permutation follows
    3 2 6 5 4 1 in lexicographic order?
    ______

5 Propositional Logic (10 points)

a. (3 points) Let F(x,y)mean that x and y are friends, where the universe of discourse for x and y is the set of Temple students. Express the following statement by a simple English sentence.

$ x " y " z ((F(x,y) Ù F(x,z) Ù (y ¹ z)) ® F(y, z))

b. (7 points) Make a truth table for the prepositional form:

[(p ® q) Ù (q ® r)] ® (p Ú Ør)


6 Functions (10 points)

Find the indicated functions (and simplify the result to a polynomial) when f(x), and g(x) (from R to R) are defined as follows:

f(x) = (x+2)2

g(x) = 3x + 4

a. (two points each)

(f°g)(x) ______

(g°f)(x) ______

(g-1)(x) ______


b. (1 point each)

h(x) = x3 (from R to R) is an injection (one to one). True False

h(x) = x3 (from R to R) is a surjection (onto). True False

h(n) = n3 (from Z to Z) is a injection (one to one). True False

h(n) = n3 (from Z to Z) is a surjection (onto). True False


7 Big O (10 points)

a. (5 points) Provide the best possible big O estimate (that is, a big Theta estimate) for each of the following functions.

f(x) = (3x + 2)3 * (x + 3)2 ______

f(x) = (3x + 2)3 / (x + 3)2 ______

f(x) = log x 4 + x2 + 5 ______

f(x) = (3x4 + log x) / (x + 3)3 ______

f(x) = (xx + x2x + 5x) * (x! + 5x) ______

b. (5 points) Show (prove) that (x2 + 2x + 3) (x2 + x!) = O(x2x!).


8. Induction and recursion (10 points)

a.  Inductive proof (6 points). Using mathematical induction, prove that:

1 + 2 + 22 +…+ 2n = / 2n+1 - 1 / for n ³ 0
  1. (3 points) Using the formulas:
    f(0) = 0
    f(n) = 2 - f(n-1) for n > 0
    calculate f(4) and f(10) f(4) ______

f(10) ______


9. More Recursion

  1. (4 points) Define a recursive procedure gcd(a, b) which accepts two nonnegative integers a and b with a < b and computes the greatest common divisor of a and b (Euclid’s algorithm).

______
______
______
______
______

b.  (2 points) Provide a recursive definition for the set
S = {1, 10, 100, 1000, …}
______

  1. (2 points) Give a recursive definition (with initial conditions) of the sequence
    an = 2n for n = 1, 2, 3, …
    ______
  2. (2 points) Give a recursive definition (with initial conditions) of the sequence
    an = (n + 1)/3 for n = 1, 2, 3, …
    ______


10. Probability (10 points)

  1. What is the probability that a 5-card poker hand contains 3 queens and another pair of cards (e.g. 3 queens and 2 kings, or 3 queens and 2 fives). A formula (rather than a number) is OK.

______

  1. A six sided die is rolled 10 times. What is the probability that exactly 4 of the 10 rolls result in a 1 or a 2 (and the other 6 rolls result in 3 through 6)? A formula (rather than a number) is OK.

______

  1. Two fair coins are flipped and a random variable X(s) is defined as the number of heads that appear (0 to 2). The answers are numbers.
    Compute E(X) ______
    Compute E(X-E(X))2 ______
  1. Compute the conditional probability that exactly four heads appear when a fair coin is flipped five times, given that the first flip came up tails. The answer is a number.
    P(4 heads on 5 flips | first flip tails) ______

Question 11, recurrence relations (10 points)

  1. (2 points) Find a recurrence relation for the number of ways to climb n stairs if the person climbing the stairs can take one or three stairs at a time.
    ______
  2. (2 points) What are the initial conditions for part (a) above?
    ______
  3. (6 points) Solve the following recurrence relation given the initial conditions shown.
    an = an-1 + 2an-2 for n ³ 2 with a0 = 2 and a1 = 7

an =______
Question 12 Simple Computations(10 points)

a.  Inclusion-Exclusion. Of 60 computer science freshman. 24 have studied Java, 26 have studied C, and 28 have studied Visual Basic. Further 8 have studied both C and Java, 6 have studied both Java and Visual Basic, and 10 have studied both Visual Basic and C. Finally 4 have studied all three languages.

1.  (2 points) How many students have not studied
any of these programming languages? _____

2.  (2 points).How many students have studied Java
but no other programming language. _____

3.  (2 points) How many students have studied exactly
one of these three programming languages. _____

  1. (4 points) Compute the product of the following matrices:

1 / -3 / 1
1 / 0 / 2
2 / 1 / -1
/ 1 / -1 / 2 / 3
-1 / 0 / 3 / -1
0 / -2 / -0 / 2