CS202 Midterm Exam

Question 1: Dueling Recurrences

Given:
S(0) ≤ T(0)

S(n + 1) = aS(n) + f(n)
T(n + 1) = bT(n) + g(n)

Where:
0 ≤ a ≤ b
0 ≤ f(n) ≤ g(n)

To Prove:
S(n) ≤ T(n) for all n ∈ N.

Solution (Using Mathematical Induction):

Step 1: Base Case

Given that
S(0) ≤ T(0)

So the statement is true for n = 0.

Step 2: Inductive Hypothesis

Assume that for some k:

S(k) ≤ T(k)

Step 3: Inductive Step

Now we prove for n = k + 1.

S(k + 1) = aS(k) + f(k)
T(k + 1) = bT(k) + g(k)

Since
a ≤ b
S(k) ≤ T(k)

Therefore

aS(k) ≤ bT(k)

Also given

f(k) ≤ g(k)

Adding both inequalities:

aS(k) + f(k) ≤ bT(k) + g(k)

So

S(k + 1) ≤ T(k + 1)

Conclusion

By mathematical induction,

S(n) ≤ T(n) for all n ∈ N.

Question 2: Seating Arrangements

Given conditions:

1. Students sit in alphabetical order.
2. Each student must have one empty seat to the right.

Let:

k = number of students
n = total seats

Each student requires:

1 seat for themselves + 1 empty seat

So total required seats:

2k

But the last student does not require an empty seat after them, therefore required seats are:

2k − 1

Remaining empty seats:

n − (2k − 1)

Now we need to distribute these extra empty seats among positions.

The number of ways to arrange students is given by:

Formula:

Number of ways =
(n − k choose k)

This counts the number of valid placements while maintaining alphabetical order and spacing.

Question 3: Non-Attacking Rooks

We place n rooks randomly on an n × n chessboard.

Total squares =

n²

Each rook can be placed anywhere.

Total possible placements:

(n²)ⁿ

Favorable Case

We want exactly one rook in every row and every column.

This corresponds to a permutation of columns for rows.

Number of valid placements:

n!

Probability

Probability = Favorable outcomes / Total outcomes

Probability =

n! / (n²)ⁿ

Question 4: Subsets

Given:

A ⊆ B

Part 1: Injection

Statement:
There exists an injection f : A → B.

Answer: TRUE

Reason:

An injection means each element of A maps to a unique element in B.

Since A is a subset of B, every element of A already belongs to B.

We can define the function:

f(a) = a

This is called the identity function, and it is clearly one-to-one.

Therefore an injection always exists.

Part 2: Surjection

Statement:
There exists a surjection g : B → A.

Answer: NOT ALWAYS TRUE

Reason:

A surjection means every element of A must have at least one element in B that maps to it.

If B has more elements than A, we can map multiple elements of B to the same element in A.

However if A is empty or certain conditions fail, a surjection may not exist.

Therefore the statement is not always true in general.