Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

DEPARTMENT OF COMPUTER SCIENCE

CSIS1118/COMP2121 Fmmdations of Computer Science and Discrete Mathematics: Final Exam

Date: 27 May, 2013

Question 1: The Basics (50 points)

You may give short answers in this question.

1. (2 pt) Suppose your parents set up the following rules:

Rule 1: If you finish your homework or clean the apartment, then you are permitted to watch TV.

Rule 2: If you watch TV, then you must sleep early.

Suppose in the end you were NOT permitted to watch TV. Circle all of the following that must be true.

A. You did not finish your homework.

B. You did dean the apartment.

C. You did not sleep early.

2. Suppose the domain for the variable xis the set of creatures. Let S(x) denote the statement that creature x can swim; C(x) denote the statement that creature x can clhnb; P(x) denote the statement that creature x is a predator. Express the following statements using quantifiers and logical operators.

(i) (2 pt) There exists a creature that can neither swim nor climb

(ii) ( 2 pt) Every predator can swim.

3. (4 pt) True or False

4. Let A be a finite set with n elements. Recall that a relation on A can be represented by either a table with n rows and n columns, or a directed graph with n nodes.

(i) ( 2pt) How many relations on A are there?

(ii) (2 pt) How many relations on A are reflexive?

(iii) (2 pt) How many relations on A are symmetric?

(iv) (4 pt) How many relations on A are both reflexive and symmetric?

5. Consider integer solutions to the equation:

X1 + X2 + X3 + X4 + X5 = 10.

(i) (3 pt) How many non-negative integer solutions are there?

(ii) (3 pt) How many non-negative integer solutions are there such that x1 = x2?

(iii) (4 pt) How many non-negative integer solutions are there such that x1 > x2?

6. (10 pt) Suppose G = (V, E) is a simple undirected graph with no self-loop; moreover, the graph G has n = |V| ≥ 1 vertices, m = |E| edges, k connected components, p odd cycles, q even cycles and chromatic number X.

7. Suppose a lion and a zebra live in a forest. On a sunny day, the lion appears with probability 0.6 and the zebra appears with probability 0.8; on a non-sunny day, the lion appears with probability 0.2 and the zebra appears with probability 0.4. Suppose the probability that a day is sunny is 0.6.

(i) (2 pt) What is the probability that the lion appears on a random day?

(ii) (3 pt) Suppose that the lion =d the zebra are not aware of each other's activities. Given that the zebra appears, what is the probability that the lion also appears?

8. Suppose you are one of 10 players in a game, where each player has a chance 0.2 of winning, independent of other players. The prize money is $100, and if there is more than one winner, the prize money is shared equally among the winners.

(i) (1 pt) What is the probability that there is at least one winner? (to 5 decimal places)

(ii) (4 pt) What is the expected amount of money that you will win? (to 4 decimal places)

(Hint: the allswer is not $20.)

Question 2: Inequalities (10 points)

(a) (3 pt) Suppose a::; band c:O;d. Prove that (a+b)(c+d)::; 2(ac+bd).

(b) (7pt) Suppose that x and y are non-negative real numbers. Prove that for all positive integers k, (x+y)k≤zk-l(xk+yk).

Question 3: Hunters and Rabbits (10 points)

Suppose there are m different hunters and n different rabbits. Each hunter selects a rabbit uniformly at random independently as a target. Suppose all the hunters shoot at their chosen targets at the same time and every hunter hits his target.

(a) (2 pt) Consider a particular Rabbit 1. What is the probability that Rabbit 1 survives?

(b) (2 pt) Suppose m= 7 and n = 5. What is the expected number of surviving rabbits? Compute the answer up to 6 decimal places.

(c) (6 pt) Suppose m= 7 and n = 5. What is the probability that no rabbit survives? Compute the answer up to 5 decimal places.

Question 4: Euler Circuits (15 points)

We consider undirected multi-graphs with no self-loops.

(a) (4 pt) Give necessary and sufficient conditions for an Euler circuit to exist in a graph.

(b) (3pt) Suppose a graph is connected and there are exactly 8 vertices with odd degrees. What is the minimum number of edges that need to be added such that the graph has an Euler circuit?

(c) (3pt) Suppose a graph has 4 connected components and all vertices have even degrees. What is the minimum. number of edges that need to be added such that the graph has an Euler circuit?

(d) (5pt) In general, given a graph, describe a method to add the minimum number of edges such that the graph has an Euler circuit. Illustrate your method with a graph which has '10 connected components, and the number of vertices with odd degrees in each component is as follows: 0,2,2,4,6,8,8,10,10,12. What is the total number of edges added?

Question 5: Picking from [0, 1] Uniformly at Random (15 points)

In this question, we show how to pick a real number from [0, 1] uniformly at random by flipping an infinite but countable number of fair coins independently. Suppose for each positive integer n, Coin n is flipped and the result is Xn E {0, 1}, where 1 represents heads and 0 represents tails. You may assume that for any positive integer m, it is impossible that for all i :;,: m, Coin i is heads. You need to give brief justification to your answers in this question.

1. ( 5 pt) What is the sample space 0 associated with this experiment? Explain whether the sample space is finite, countable, or uncountable.

2. (5pt) Define a random variable  What is Pr[Z :S: 0.625]? (Hint: 0.625 = 2/1 + 8/1.)

3. (5pt) In general, for a real number x E [0, 1], what is Pr[Z≤x]? Explain your answer.