CSE 016 PRACTICE Midterm 2

Multiple-Choice Scoring: no answer for question: 0 ; correct answer: +2 ; each wrong answer: −1

Multiple-Choice Scoring cont’d: multiple answers for question: each answer is graded per the above line;

e.g., 1 right and 1 wrong earns +2 -1, better than 0.

Full Multiple-Choice credit can be earned leaving one question blank.

Some Multiple-Choice questions may be similar to Midterm 1.

Closed book Answer on this Exam

Possibly helpful information appears on last several pages. Exam on Nov. 16, 2022

1 Multiple-Choice 30

12 Solve a Problem 8

13 Solve a Problem 12

TOTAL 50

Mult. Choice: 2 * ——– less —— = ——

right wrong

The above point total and breakdown is just an example.

The actual point total and breakdown may be different.

CSE 016 Fall, 2022, Handout 12 1

CSE 016 PRACTICE Midterm 2

1 Multiple-Choice (32 pts)

1. (2 pts.) For an arbitrary set S, the expression |S| denotes:

(a) Whether S is empty or finite or infinite.

(b) The number of elements in S.

(c) The number of subsets of of S.

(d) The set of all subsets of S.

2. (2 pts.) Let P and Q be two infinite sets. What do P ∪Q and P ∩Q denote among the choices?

(a) P ∪Q means P is a superset of Q and P ∩Q means P is a subset of Q.

(b) P ∪Q means P is a subset of Q and P ∩Q means P is a superset of Q.

(c) P ∪Q denotes the set of elements that are in either P or Q, while P ∩Q denotes the set of elements that

are in both P and Q.

(d) P ∪Q denotes the set of elements that are in both P and Q, while P ∩Q denotes the set of elements that

are in either P or Q.

3. (2 pts.) For any set S P(S) denotes:

(a) The set of all subsets of S.

(b) The set of all nonempty subsets of S.

(c) The set of all ordered pairs of elements in S.

(d) The set of all ordered pairs of distinct elements in S.

4. (2 pts.) Let P and Q be two sets. What does P −Q denote among the choices?

(a) P −Q denotes the elements in P and not in Q, provided that Q is finite.

(b) P −Q denotes the elements in P and not in Q, provided that P is infinite and Q is finite.

(c) P −Q denotes the elements in P and not in Q, regardless of whether either set is finite or infinite.

(d) P −Q denotes the elements in P and not in Q, provided that Q is a subset of P , regardless of whether P

is infinite.

CSE 016 Fall, 2022, Handout 12 2 Right: Wrong:

CSE 016 PRACTICE Midterm 2

Figure 1: The next several questions are about the following sets and information.

Let U be the “universe”, also called the “domain of discourse”.

Recall that for any set S, S denotes the set of elements that are in U and not in S.

Let A ⊆ U and B ⊆ U .

Let U be the nonnegative integers.

Let A be the positive even integers, and

let B be the nonnegative integers divisible by 3.

Let C = (A ∩B).

5. (2 pts.) The set C consists of:

(a) The set of positive integers divisible by 6.

(b) The set of nonnegative integers divisible by 6.

(c) The set of positive integers divisible by 2 and not divisible by 3.

(d) The set of nonnegative integers divisible by 2 and not divisible by 3.

6. (2 pts.) A ∪B consists of:

(a) The set of nonnegative integers divisible by 2 and divisible by 3.

(b) The set of positive integers divisible by 2 and divisible by 3.

(c) The set of nonnegative integers not divisible by 2 and not divisible by 3.

(d) The set of positive integers not divisible by 2 and not divisible by 3.

7. (2 pts.) Which statement is most accurate among the choices?

(a) C is finite and A ∪B is finite.

(b) C is finite and A ∪B is infinite.

(c) C is infinite and A ∪B is infinite.

(d) C is infinite and A ∪B is finite.

CSE 016 Fall, 2022, Handout 12 3 Right: Wrong:

CSE 016 PRACTICE Midterm 2

8. (2 pts.) Consider the binomial expansion of

(

x+ 1

x

)6

. The coefficient of the term containing x−2 is:

(a) 6.

(b) 15.

(c) 20.

(d) 30.

9. (2 pts.) Let T be the set of strings of length 6 made from the alphabet {A,B,C} and containing exactly 3 A’s

and 2 B’s. Then |T | is:

(a) 6.

(b) 12.

(c) 60.

(d) 64.

10. (2 pts.) Recall that ⊕ means “exclusive or”. Consider the logical expression

(P ⊕Q) ∨ (Q⇒∼ R).

Which statement is most accurate?

(a) The expression might be false if P is false.

(b) The expression might be false if Q is false.

(c) The expression might be false if R is false.

(d) The expression cannot be false.

11. (2 pts.) Let P , Q, and R be statements. Which sequent (in textbook notation) is logically incorrect?

(a)

P ∨Q

∼ P

Q

(b)

P → Q

∼ Q

∼ P

(c)

P → Q

∼ P

∼ Q

(d)

P → Q

Q→ R

P → R

CSE 016 Fall, 2022, Handout 12 4 Right: Wrong:

CSE 016 PRACTICE Midterm 2

NOTE: Each long answer problem will be on a separate page.

12 Greatest Common Divisors

Recall the definition that the greatest common divisor positive integers x and y, written gcd(x, y), is the largest

common factor of x and y.

Let b, c, and d be positive integers. You may use without proof the fact that:

IF (d | b) AND (d | c),

THEN (d | b · c).

Prove that

IF x, y, and z are positive integers,

AND (x | y · z) AND gcd(x, y) = 1,

THEN (x | z).

13 Fibonacci Recurrence

The Fibonacci function F(n) is defined by for nonnegative integers as:

F (0) = 0; F (0) = 1; F (n) = F (n− 1) + F (n− 2);

Prove the following equation is correct for all n ≥ 1:

F (n+ 1)2 − F (n+ 1)F (n) = F (n)2 + (−1)n

14 Congruences

Let n be any integer.

Prove that n2 ≡ 2 (mod 3) is not true.

CSE 016 Fall, 2022, Handout 12 5

CSE 016 PRACTICE Midterm 2

MISC. INFORMATION, NO QUESTIONS.

(

7

4

)

= 35.

(

8

5

)

= 56.

(

8

3

)

= 56.

4! = 24; 5! = 120; 6! = 720; 7! = 5040; 8! = 40320;

1 2 3 5 5 6 7 8 9

2 2 4 6 8 10 12 14 16 18

3 3 6 9 12 15 . . .

4 4 8 12 16 20 . . .

. . .

CSE 016 Fall, 2022, Handout 12 6

欢迎咨询51作业君