CISC 1100 Prof. Zhao Spring 2011

CISC 1100 – Prof. Zhao–Spring 2011

Practice FinalExamSolutions

Note this practice exam is significantly longer than the actual exam. It is intended to help you review all the material we have covered in class.

Relations and Functions

Know the properties of a relation. Be able to determine if a relation is reflexive, anti-reflexive, symmetric, anti-symmetric, transitive or non-transitive.

Problem 1: Determineeach of the relations below defined on set Z (all integers) is

reflexive, anti-reflexive or neither

symmetric, anti-symmetric or neither

transitive or non-transitive

R≤: “smaller or equal to” (reflexive, anti-symmetric, transitive)

Rd: “greater than” (anti-reflexive, anti-symmetric, transitive)

Ra: “adds up to 6” (neither, symmetric, non-transitive)

Know the difference between relations and functions.

Problem 1: Given the relation A = {(5,2), (7,4), (9,10), (11, 20), (x, 5)}

Which of the following values for x will make relation A a function?

7
9Answer: C
4
11

Problem 2: Which graph represents a function y = f(x)?Answer: A

(A) (B) (C) (D)

Know how to evaluate a function, including composed functions.

Problem 1: Given f (x) = 3x + 7, findf (5). Answer: 22

Problem 2:Given f(x) = x+2, g(x) = (4x-1)

Compute f (g (2)), g(f(2)), f(f(1)), g(g(1)) Answer: 9, 15, 5, 11

Problem 3:Given and ,

find and .

Answer: and

Problem 4:Given ,, and ,
find.Answer:

Know how to find inverse of a given function

Problem 1:Findthe inverse for the function y = 2x - 12.

Answer: y=(x+12)/2

Problem 2:Findthe inverse for the function y = 2(x – 12).

Answer: y=x/2 + 12

Problem 3:Findthe inverse for the function

Answer: y=

Problem 4:Using composition of functions, show that
f (x) = 2x - 3 andg(x) = 0.5x + 1.5 are inverse functions.

Answer : need to show both f(g(x)) = x and g(f(x)) = x

f(g(x)) = 2(0.5x+1.5) – 3 = x + 3 – 3 = x

g(f(x)) = 0.5(2x-3) + 1.5 = x – 1.5 + 1.5 = x

Therefore, f, and g are inverse to each other.

Problem 5:What is value for

25
5Answer: B
10
Can’t be determined

Counting

Be fluent with addition principle and multiplication principle. They are the foundation of all of our counting problems. The problems are paired up on purpose. Try to feel the difference between addition and multiplication principles.

Problem 1:Suppose there are 15 boys and 12 girls in a class. How many ways can you select one person to check attendance? 15+12 = 27

Problem 2:Suppose there are 15 boys and 12 girls in a class. We need to select one boy and one girl to host a performance show. How many possible selections are there? 15x12 = 180

Problem 3:A man has 3 different suits, 4 different shirts and 5 different pairs of shoes. In how many different ways can this man wear a suit, a shirt and a pair of shoes? 3x4x5 = 60

Problem 4:A man has 3 white short sleeve shirts, 4 blue short sleeve shirts, and 5 long sleeve shirts. In how many different ways can he choose to wear a shirt? 3+4+5 = 12

Problem 5:A person is traveling from city A to city B. There are 8 ways to take buses, 5 ways to drive, and 2 ways to take a train, 1 way to fly. How many choices does he have to travel from A to B. 8+5+2+1=16

Problem 6:A person is traveling from city A to city C. But there is no direct route from A to C. He must first get to city B, then to city C. There are 8 ways to go from A to B, 5 ways to go from B to C. How many choices does he have to travel from A to C. 8x5 =40

Know how to compute P(n, r), C(n, r). Know how to use permutation and combination to solve two special kinds of counting problems (i.e. reuse objects? Order or objects?).

The problems are paired up on purpose. Try to feel the difference between permutation problems and combination problems.

Problem 1:Compute P(10, 5), P(59, 2), P(8,8)

Problem 2:Compute C(10, 5),C(59, 2), C(8,8)

Problem 3:You have 5 book and you want to put 3 of them onto the shelf. In how many different ways could you arrange them? P(5,3) = 60

Problem 4:You have 5 books, you want to choose 3 of them to read. In how many different ways could you choose? C(5,3) = 10

Problem 5:How many ways can you pick 3 dessert out of a menu of 10? C(10, 3) = 120

Problem 6:How many ways can a restaurant offer 3 favorite dessert with order of preference out of a menu of 10? P(10,3) = 720

Be able to use combined counting skills to solve more complicated problems.

Problem 1:Assuming that any arrangement of letters forms a 'word', how many 'words' of any length can be formed from the letters of the word SQUARE? (No repeating of letters)

Answer: P(6,6) + P(6,5)+P(6,4)+P(6,3) + P(6,2)+P(6,1)

Problem 2:How many distinguishable ways are there to arrange the letters in the word “ MISSISSIPPI ”? Answer: 11!/ ( 4!*4!*2!) = 34,650

Probability

Use definition of probability and counting techniques to solve problems.

Problem 1:If you flip a fair coin 3 times,

What’s the probability of getting exactly one head? 3/8

What’s the probability of getting exactly two heads? 3/8

What’s the probability of getting at least one head? 1-1/8 =7/8

Problem 2:A die is rolled, find the probability that the number obtained is greater than 4. 2/6 = 1/3

Understand disjoint and independent events. Use addition rule and multiplication rule to solve problems.

Problem 1:A box contains 8 red marbles, 4 white marbles, and 12 black marbles. A marble is drawn at random, what is the chance of getting a red or black marble?

Answer: + = =

Problem 2:Carlos plays college soccer. He makes a goal 65% of the time he shoots. If Carlos is going to attempt two goals in the next game.

What’s the probability Carlos makes one of the goals?

0.65*0.35 + 0.35*0.65 = 0.455

What’s the probability Carlos makes both goals?

0.65*0.65 = 0.4225

What’s the probability Carlos makes at least one goal?

1-0.35*0.35 = 0.8775

What’s the probability Carlos makes no goals?

0.35*0.35 = 0.1225

Problem 3:You have one standard 6-sided die. You roll it 3 times and record the results.

How many possible outcomes are there?

6x6x6 = 216

What is the probability that you get all 6’s ?

1/6 *1/6*1/6 = 1/216

What is the probability that you get exactly two 6’s?

5/6*1/6*1/6 + 1/6*5/6*1/6+1/6*1/6*5/6 = 15/216

Understand the concept of expected value. Be able to determine a fair price for a probability game.

Problem 1:500 tickets for prizes are sold for $2 each. Five prizes will be awarded – one for $300, one for $200, and three for $50. Steven purchases one of the tickets. What is the expected value of his ticket?

300x(1/500 )+ 200*(1/500) + 50*(3/500) = 650/500 = $1.3

Algorithms

Problem 1: We want to sort (3, 5, 1, 9, 2) into ascending order

A)How many comparisons are there if we use the following BubbleSort algorithm? Show your steps. ( 4+3+2+1 = 10)

B) If we use the following MergeSort algorithm, how many times the function merge(l1; l2) will be invoked? (merge will be called 4 times)

BubbleSort Algorithm

1 Repeat as ivaries from n down to 2

2 Repeat as j varies from 1 to i- 1

3 If lj> lj+1 swap ljwith lj+1

Note. First Repeat loop spans both line 2 &3

MergeSort Algorithm

functionmergesort(L)

1 if L has one element then return(L); otherwise continue

2 l1 = mergesort(left half of L)

3 l2 =mergesort(right half of L)

4 L = merge(l1; l2)

5 return(L)

Problem 2: 7 positive integers are stored in an ascending order:

2 5 10 15 40 48 60

If we want to write an algorithm to locate the position of a given number, e.g. position(5) = 2

What searching algorithm would you choose?

Answer: Binary Search

Give an example of the worst case scenario of your algorithm and specify how many comparisons does it need to locate the number.

Answer: first number (2 in the example)is always one of the hardest ones to locate in binary search. In this example, It will take 3 comparisons.