CSE 21 – Spring 2021 – Practice Final Part 1
1. Counting (a) How many 5-card hands can be formed from an ordinary deck of 52 cards if exactly two
suits are present in the hand
(b) In any bit string, the longest consecutive run length is the maximum number of consecutive 1’s or
consecutive 0’s in the string. For example, in the string 1101000111, the longest consecutive run
length is 3. How many bit strings of length 10 have a longest consecutive run length of 6
(c) A software company assigns its summer interns to one of three divisions: design, implementation,
and testing. In how many ways can a group of ten interns be assigned to these divisions if each
division needs at least one intern
(d) How many numbers in the interval [1,10000] are divisible by 7, 9, or 11
(e) A California license plate follows the format DLLLDDD, where D represents a digit and L rep-
resents an upper case letter. For example, a valid California license plate is 5JBC434 (Quang’s
plate). How many California license plates are possible
Under a fixed-length encoding scheme, how many bits of memory does the California DMV need
to allocate in its database to store each license plate number
2. Recursive Counting For problems (a)-(d), it is not required to solve the recurrence.
(a) In a round-robin tennis tournament with n players, every tennis player plays against every other
player. Let T (n) be the total number of tennis matches taking place among the n players. Find a
recurrence for T (n) and explain in words why T (n) satisfies this recurrence.
(b) In a board game, players must place colored tiles in a single row. There are red 1 1 tiles, yellow
2 1 tiles, blue 2 1 tiles, purple 3 1 tiles, and green 3 1 tiles. Let C(n) be the number of
di erent 1 1 colored rows that can be created using these tiles. Find a recurrence for C(n) and
explain in words why C(n) satisfies this recurrence.
(c) Any binary string can be broken into contiguous chunks of the same character, called runs. For
example, 001110100000 has:
a run of 0s of length 2
a run of 1s of length 3
a run of 0s of length 1
a run of 1s of length 1
a run of 0s of length 5
Let B(n) be the number of length n binary strings where each run of 1s has even length. Find a
recurrence for B(n) and explain in words why B(n) satisfies this recurrence.
(d) Let S(n) be the number of subsets of {1, 2, . . . , n} having the following property: there are no three
elements in the subset that are consecutive integers. Find a recurrence for S(n) and explain in
words why S(n) satisfies this recurrence.
3. Stars and Bars item Let n, k be positive integers. Recall the Stars and Bars Problem that the integer
equations a1 + a2 + . . .+ ak = n, where ai 0, has
