CMP337

Sample Questions for Midterm Exam 2

Each question counts 4 points

1. What is a binary relation from X to Y?
   
   
2. Define a symmetric relation and give an example.
   
   
3. Define partial order and give an example.
   
   
4. Write the relation R as a table, where R is defined by (x,y) in R if x² > y
   
   
5. List the elements of the following relations R on the set {1,2,3,4,5}
1. (x,y) in R if 3 divides x-y.
2. (x,y) in R if 3 divides x+y.
   
   
6. Show that the relation R on the set of all positive integers defined by (x,y) in R if 3 divides x-y is a partial order
   
   
7. What is an equivalence relation?
   
   
8. Suppose that R is an equivalence relation over a set X and that [a] = { b | bRa }. Show that the set S = { [a] | a in S } is a partition of X.
   
   
9. Is the relation {(1,1), (2,2), (3,3), (4,4), (5,5), (1,3), (3,1) } an equivalence relation?
   
   
10. Which of the following relations are functions?
1. { (1,a), (2,a), (3,a), (4,a) }
2. { (1,c), (2,a), (3,b), (4,c), (2,d)}
3. { (x,y) | y = x² }
4. { (x,y) | x = y² }
   
   
11. What is the domain of a function from X to Y?
    
    
12. How is the modulus operator used to define a hash function?
    
    
13. Draw the arrow diagram for the function f: { (x,a), (y,c), (z,a), (w,d) }.
    
    
14. Which of the following functions is injective?
1. f(x) = x², where domain(f) = positive and negative real numbers
2. f(x) = x³, where domain(f) = positive and negative real numbers
3. f(x) = x mod 5, where domain(f) = positive integers
4. f(x) = floor(x), where domain(f) = positive real numbers
   
   
15. Let X={1,2,…,10}. Define a relation R on X x X by (a,b)R(c,d) if ad=bc. Show that R is an equivalence relation.
    
    
16. Let f (n) = n² and g (n) = 2ⁿ. What is f°g?
    
    
17. Let f be a function from X to Y and g be a function from Y to Z. Is it true or false that if f and g are both onto (surjective), then so is f°g? Explain why or why not.
    
18. Write an algorithm to multiply two numbers, digit by digit, as is taught in elementary school.
    
    
19. Trace the Euclidean algorithm with inputs 110, 273.
    
    
20. Write an algorithm to tile a “deficient” board with 2ⁿ squares on a side with right trominoes.
    
    
21. Select a theta notation for each of the following functions:
1. 6n+1
2. (6n+1)2
3. 1 + 2 + 3 + … + n
4. 2 lg n + 4
   
   
22. How many times is the statement x:=x+1 executed in the following code:
    
    for i:= 1 to n
    for j := 1 to n
    for k := 1 to n
    x := x+1
    
    Explain why.
    
    
23. Suppose that you have a deck of 52 cards, with 4 suits and denominations 2,…,10,J,Q,K,A
1. How many ways can you order the cards?
2. How many ways can you pick a 5-card hand from the deck?
3. How many 5 card hands include either the ace of spades or the king of hearts?
4. Suppose we ignore suit – how many ways are there to pick a 4-card hand?
   
   
24. Consider the set of letters { U, V, W, X, Y, Z }
1. How many 5-letter strings can you make with these letters, with no repetitions?
2. How many 5-letter strings can you make with these letters, with repetitions?
3. How many 12-letter strings have 4 U’s, 3 V’s, and 2 W’s?
4. How many ways can you pick sets of 5 letters from this string consisting only of U’s, V’s, and W’s?
   
   
25. Show by induction that the tromino (or Euclidean) algorithm works.