Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

EECS 376: Foundations of Computer Science

Fall 2025

Homework 3

Due 8:00pm, September 17

(accepted until 10:00 pm, no credit after)

This homework has 9 questions, for a total of 100 points and 3 extra-credit points.

Unless otherwise stated, each question requires clear, logically correct, and su!cient justification to convince the reader.

We strongly encourage you to typeset your solutions in LATEX.

If you collaborated with someone, you must state their name(s). You must write your own solution for all problems and may not use any other student’s write-up or any AI tools.

0. Before you start; before you submit. If applicable, state the name(s) and uniqname(s) of your collaborator(s).

(10 pts) 1. Self assessment. Carefully read and understand the posted solutions to the previous homework.

Identify one part for which your own solution has the most room for improvement (e.g., has unsound reasoning, doesn’t show what was required, could be significantly clearer or better organized, etc.). Copy or screenshot this solution, then in a few sentences, explain what was deficient and how it could be fixed.

(Alternatively, if you think one of your solutions is significantly better than the posted one, copy it here and explain why you think it is better.)

If you didn’t do last week’s homework, choose a problem from it that looks challenging to you, and in a few sentences, explain the key ideas behind its solution in your own words.

2. Counting strings! Let C(n) denote the number of binary strings of length n that have no consecutive occurrences of 1. For example, C(3) = 5; we see this by listing all binary strings of length 3 and checking that only the strings 000, 001, 010, 100, and 101 have no consecutive 1s.

(2 pts) Compute (a) C(5).

(4 pts) (b) Derive, with justification, a recurrence relation for C(n). Remember to include appropriate base case(s).

Hint: Consider two cases depending on whether the first character is a 0 or a 1.

(3 pts) (c) Translate your recurrence into pseudocode that is top-down recursive, without memoization. You may use Algorithm 26 in the course notes as an example. (Note that this algorithm runs in time exponential in the input value n.)

Finally, show a lower bound on the runtime of the algorithm, which establishes that the runtime is exponential in n.

(Note that since the input is n, the input size is !(log n), so this exponential-in-n algorithm runs in double exponential time with respect to the input size, i.e. ablog n for some constants a and b.)

(3 pts) (d) Translate your recurrence into dynamic-programming pseudocode. (Algorithm 28 in the course notes is a good model.)

In this and subsequent DP questions, credit for pseudocode will be determined based only on how “faithful” (i.e., properly derived) it is to your recurrence—regardless of whether the recurrence itself is correct. (So, pseudocode that isn’t faithful to your recurrence will not get full credit—but pseudocode that properly matches an incorrect recurrence will get full credit.)

Additionally, for all DP questions, your pseudocode should be written in the “bottom-up” form, rather than top-down memoization.

Analyze the running time of your code, as a function of n. Note that unlike most problems, you are not being asked to write the running time in terms of the input size (n is the input value, not the input size.) You may use the fact (without proof) that C(n) has !(n) bits, so adding together two entries of the dynamic programming table takes O(n) time.

3. Seems Familiar? In this course, pattern matching is a crucial skill. Many problems you will see on homeworks and exams are, at their cores, similar to those you have previously solved in lecture or discussion. Noticing these similarities allows you to use familiar strategies and techniques to solve new problems e”ectively.

In this problem, you are given 3 dynamic programming problems below. For each of the following parts, you are given another problem that is the same as one of aforementioned problems and can be solved with same recurrence.

For each part, state and briefly justify which problem it is a reformulation of. Explain which aspects of the two problems correspond to each other.

You do not need to provide the recurrence (though you may want to in order to justify your solution).

• Knapsack Variant: Given n items where each item i has an associated value vi and weight wi, and no two weights are the same, find a subset of items with maximum possible value, whose total weight is at most C.

• Coin Change: Given a list of coins c = [c1,...,ck], where ci is the value of coin i, and a target amount n, find the number of di”erent collections of coins that have a total value of n.

• Stair Climbing: Given a staircase with n stairs, determine the number of distinct ways a person starting at the bottom can reach the top if each time they take a step they can advance either 1 or 2 stairs.

(4 pts) (a) Pipe Cutting: Given a pipe of length L, and a list of pipe lengths with associated prices, find the maximum revenue obtainable by cutting the pipe into pieces, and selling the pieces (discarding any leftover pipe), under the constraint that you may only sell each length of pipe a maximum of one time.

(4 pts) (b) Domino Tiling: Given a 2 → n board, determine the number of ways to completely tile the board using 2→1 dominoes, which can be placed either vertically or horizontally. Every square of the board must be covered by precisely one domino.

4. Minimum Subarray Product

Given an array A[1,...,n] of n ≥ 1 positive real numbers, we are interested in finding the smallest product of any contiguous subarray of A, i.e.,

min{A[i]A[i + 1] ··· A[j]:1 ≤ i ≤ j ≤ n} .

(8 pts) (a) In this problem you may assume for simplicity that multiplying a pair of real numbers can be done in O(1) time. Give a recurrence relation, including base case(s), that would yield an O(n)-time dynamic-programming algorithm for the smallest product problem. Briefly justify why your recurrence relation is correct. You will analyze the running time of the resulting algorithm in part (b).

Hint: The longest increasing subsequence recurrence might give you some inspiration (but this recurrence should be simpler than that one).

(6 pts)

(b) Give pseudocode implementing an O(n)-time dynamic programming solution to the smallest product problem, and justify the running time. Recall that for simplicity, you may assume that multiplying a pair of real numbers can be done in O(1) time. For all DP problems, remember to refer to the “DP Recipe” from lecture and discussion.

5. Sugar Rush!

You and a friend have won first prize at a Halloween costume party (due to your brilliant Alan Turing and Alonzo Church costumes): a bucket of several pieces of candy, each having some amount of sugar. You and your friend plan to celebrate your win by staying up late and eating all of the candy, but first you need to divide it between yourselves. The problem is that if you and your friend consume di”erent amounts of sugar, the one who eats less sugar will crash first, leaving the other person to stay up alone. You need a way to divide the candy between the two of you so that you both eat the same amount of sugar, and crash at the same time.

In this problem you will give a dynamic-programming algorithm that, given an array S = [s1, s2,...,sn] where the i th piece of candy has a non-negative integer si grams of sugar, either divides the pieces into two ‘piles’ that have equal amounts of sugar, or (correctly) says that no such piles exist. (Each piece must be in exactly one of the piles.)

(10 pts) (a) For a given array S, define P(c, i) to be true if there exists a pile drawn from the first i pieces of candy having a total of c grams of sugar, and false otherwise. Derive, with justification, a recurrence relation for P(c, i). Remember to include appropriate base case(s).

When writing recurrences with Boolean values, you may use operators such as ∧ (and), ∨ (or), and ¬ (not).

(3 pts) (b) Briefly state, with justification, the values of c and i to plug into P(c, i), to determine if it is possible to split the candy into two piles having equal amounts of sugar.

(5 pts) (c) Give pseudocode for a dynamic-programming algorithm that determines whether the candy can be divided into two piles that have the same amount of sugar. Analyze the running time.

Note that this is not an e#cient algorithm (in fact, there is no known e#cient algorithm for this problem!). However, if each si is upper bounded by a constant, then your algorithm should be e#cient.

(4 pts) (d) Not eating the candy is not an option! Given the completed DP table from the previous part, describe in clear English how you would find the smallest possible di”erence in sugar between two piles.