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
✓
n+ k 1
k 1
◆
solutions.
Find the number of integer solutions of the equation x1 + x2 + x3 = 50 such that 0  xi  19, for
i = 1, 2, 3. You may leave your answer in terms of the binomial coecients.
(Hint: Let Ai be the set of all solutions in which xi 20.)
4. Encoding Battle Pirates is the hottest new board game to be sweeping the globe. In this two player game,
the players secretly place three pirate ships on their individual 8x8 maps. Then, they take alternating
turns guessing tiles to try and sink the other player’s ships. If one player destroys all the other player’s
ships, they win a big chest o’ doubloons! (Any similarities to existing naval ship board games are purely
coincidental.)
1
Each player’s board consists of an 8x8 grid, labeled AH on the x-axis and 0 7 on the y-axis. Each
player has three ships to place: a red, blue, and green ship. Every ship is five tiles long. Ships can be
placed anywhere either horizontally or vertically as long as they fit within the map (the edge of a ship
cannot go past the boundary of the grid). Ships can also overlap because, y’arr!, a pirate’s life be full of
skullduggery!
An example map is shown below. In this example, the red ship is located from (A, 1) to (E, 1), the blue
ship from (E, 1) to (E, 5), and the green ship from (B, 6) to (F, 6).
0
1
2
3
4
5
6
7
A B C D E F G H
(a.) How many board arrangements of ships are possible? (Hint: Think about how a ship’s orientation,
vertical or horizontal, limits where the ship can be placed in a column or row.)
(b.) What is the minimum number of bits needed to represent a board arrangement?
(c.) Devise an encoding that uses the minimum number of bits.
(d.) Use your encoding scheme to encode the board arrangement above.
5. Ranking/Unranking Battle Pirates: Scurvy Edition adds a new, special attack to the Battle Pirates
game from question 4. Once per game, players can unleash a volley of four shots, hitting any four tiles
in a row or column. Shiver me timbers!
We can represent the tiles hit in a specific row using a fixed-length, fixed-density binary string. Since
each row consists of eight tiles, we can represent it with a string of eight 0s. Then, we set each tile hit
by the special attack with a 1.
For example, given the following attack:
We would represent it with the string 11011000.
i. Encode the following attacks by converting them into binary strings and then ranking them.
(a)
(b)
2
(c)
ii. Decode the following attacks by unranking them into a binary string.
(a) 62
(b) 31
(c) 19
6. Hu↵man Encoding Suppose a certain file contains only the following letters with the corresponding
frequencies
E R S T N L Z X
34 22 24 28 15 10 9 8
Construct the Hu↵man code that enables you to encrypt the file so that you can store it using the least
number of bits. Specify the binary representation for each letter and compute the length of the encoded
file under Hu↵man coding. (Use the procedure shown in class and in the book: (Rosen p.764))
7. Order questions. For each of the following pairs of functions f and g, choose whether f 2 o(g), f 2 ⇥(g),
or f 2 !(g) (exactly one will be true).
(a) f(n) = n, g(n) = 2blognc
(b) f(n) = log(n4), g(n) = (log n)4.
(c) f(n) = n2, g(n) = 1000n2 + 2100
(d) f(n) = 22n, g(n) = 2n.
(e) f(n) = n!, g(n) = nn.
8. Analyzing algorithms. What is the order of the standard multiplication algorithm for multiplying two
n⇥ n matrices? Suppose that any two matrix entries can be multiplied together in constant time, and
that addition takes constant time.
9. Loop Invariants The online version of the Battle Pirates game from problem 4 has recently been released.
However, in a shocking twist for a game about pirates, the online community has attracted some less
than honorable players. Cheaters have been abusing glitches to place their ships partially or fully outside
the 8x8 grid!
While they work on a more permanent solution, the developers have released a hotfix: an algorithm that
checks whether a boat is fully within the grid or not.
IsShipInBounds
1. if the boat is horizontal then
2. for y = 0, 1, 2, . . . , 7
3. if parts of the boat occupy tiles (’D’, y) and (’E’, y) then
4. return TRUE
5. else
6. for x =’A’,’B’,’C’,. . . ,’H’
7. if parts of the boat occupy tiles (x, 3) and (x, 4) then
8. return TRUE
9. return FALSE
(a) What loop invariant(s) are required to prove the algorithm’s correctness?
(b) Prove the correctness of the loop invariants.
3
(c) Use the loop invariants to conclude the correctness of the algorithm.
10. Recursive algorithms. Here’s a recursive algorithm, that given an n bit number in binary, x = xn1 . . . x0
and an m < n bit number in binary y, computes x mod y. It uses the following sub-routines: Add(x, y)
adds two n bit binary numbers in O(n) time, AsLarge(x, y) returns true if and only if x y and also
takes O(n) time, and Subtract(x, y) computes x y and is also O(n) time. We assume y 2 and n 1.
Mod (x = xn1 . . . x1x0, y)
1. IF n = 1, return x0.
2. v Mod(xn1 . . . x1, y).
3. v Add(v, v)
4. v Add(v, x0).
5. IF AsLarge(v, y) THEN v Subtract(v, y).
6. Return v
(a) Correctness. Prove by induction on n that Mod(x, y) returns x mod y.
Hints:
- Let x = 2a+ x0, where a = xn1 . . . x1.
- To show that two numbers are the same mod y, show that their di↵erence is a multiple of y.
(b) Recurrence. Give a recurrence for T (n), the time this algorithm takes on an input of size n.
(c) Solving recurrences. Solve this recurrence to give the Big O time of this algorithm.
11. Master Theorem and Solving Recurrences Solve the following recurrences the give a big-O order
for the runtime T (n).
(a) T (n) = 4T (n 1) +O(1)
(b) T (n) = 3T (n/4) +O(
p
n)
(c) T (n) = 2T (n/2) +O(n)
4
5
6

























































































































































学霸联盟