1. For each of the following maps, where f : Z Z Z , determine...
Question:
1. For each of the following maps, where f : Z×Z→Z, determine whether f is:
i.) onto and one-to-one
ii.) onto but not one-to-one
iii.) not onto but one-to-one
iv.) neither onto nor one-to-one
v.) not a function
a) f (x, y) = 3x2 −2y
b) f (x, y) = y! + x
c) f (x, y) = 2x ∗3y
d) f (x, y) = x −y
e) f (x, y) =|x |+y
2. Use the cashier’s algorithm to make change using quarters, dimes, nickels, and pennies for the following
amounts of money. You do not have to specifically show how you greedily formed change, but rather there
are many ways to make this change and only the cashier’s/greedy distribution will be accepted.
a) 43 cents
b) 68 cents
c) 98 cents
3. Imagine that a new coin that is worth exactly 4 cents has been introduced to our existing currency system.
Prove or disprove the statement: “The cashier’s algorithm using quarters, dimes, nickels, 4-cent coins, and
pennies and will always produce change using the fewest coins possible.”
4. State whether the following is True of False and explaining your reasoning for full credit:
a) Given two integers x and c, if x + c < 10, then ⌊x/10⌋= ⌊(x + c)/10⌋.
b) Given two functions f(x) and g(x), if f(g(x)) is defined, then g(f(x)) must also be defined.
5. For each of these functions from R+ → R, find the least integer n such that f(x) is O(xn) if possible. If not,
explain why the function cannot be O(xn).
a) f (x) = x2√x
b) f (x) = 2x3 + x2 log(3x)
c) f (x) = x5+x4
x4+5 log5(5x)
d) f (x) = log(1000)
e) f (x) = 3x
x3+ x3
log(x)
6. Consider the linear search algorithm as outlined in class. How many values would 15 be compared to in the
sequence (1, 7, 13, 22, 44, 15, 7, 9)?
7. Consider the binary search algorithm as outlined in class. (You must use this exact version of the binary
search algorithm):
a) List the values that 44 would be compared to in a search for 44 in the following sequence: (1, 7, 9, 13, 15, 44, 57, 88).
Make sure to include the final value in the “equality” check as well.
b) List the values that 103 would be compared to in a search for 103 in the following sequence: (3, 8, 17, 21, 44, 73, 88,
101, 113). Make sure to include the final value in the “equality” check as well.
8. Prove or disprove the following statements.
a) ⌊2x⌋= ⌊x⌋+ ⌊x + 0.5⌋, for all x ∈R.
b) x3 + x2+ log(x) is O(x3). (If you choose to prove this statement, you must do so using witnesses).
Statistics for Psychology
ISBN: 978-0205258154
6th edition
Authors: Arthur Aron, Elaine N. Aron, Elliot J. Coups