Recursion

This is Assignment #3 of Stanford's CS106B class last Spring Quarter 2011.

It consists of four problems and 2 warm-up problems.
(I only did 3 of the 4 problems because the last one was fairly difficult). Click here here to download the assignment handout.

The link for downloads below might not work. Please use this link to download all solutions to the problems.

Warm-up problem 0a. Binary encoding

Write a recursive function GenerateBinaryCode(nBits) that generates the bit patterns
for the standard binary representation of all integers that can be represented using the
specified number of bits. For example, calling GenerateBinaryCode(3) should produce
the following output:

000
001
010
011
100
101
110
111

Download my solution for Warm-up problem 0a here.
Warm-up problem 0b. Subset sum

The subset sum problem is an important and classic problem in computer theory. Given  a set of integers and a target number, your goal is to find a subset of those numbers that sum to that target number. For example, given the numbers {3, 7, 1, 8, -3} and the target sum 4, the subset {3, 1} sums to 4. On the other hand, if the target value were 2, the result is false since there is no subset that sums to 2.

 Download my solution for Warm-up problem 0b here.
Problem 1. Karel goes home

Your job in this problem is to write a recursive function

int CountPaths(int street, int avenue)

that returns the number of paths Karel could take back to the origin from the specified starting position, subject to the condition that Karel doesn’t want to take any  unnecessary steps and can therefore only move west or south (left or down in the diagram).

 Download my solution for problem 1 here.
 Problem 2. Balancing parentheses

Write a function

bool IsBalanced(string exp);

that takes a string consisting only of parentheses, brackets, and curly braces and returns true or false according to whether that expression has properly balanced operators. (Your function should operate recursively.)

Download my solution for problem 2  here.

Problem 3. Cell phone mind-reading

Write a function

void ListCompletions(string digits, Lexicon & lex);

that prints all words from the lexicon that can be formed by extending the given digit sequence. For example, calling ListCompletions("72547", english) should generate the following sample run:

palisade
palisaded
palisades
palisading
palish
rakis
rakish
rakishly
rakishness
sakis

 Download my solution for problem 3  here.

Problem 4. Stock Cutting

You are charged with buying the plumbing pipes for a construction project. Your
foreman gives you a list of the varying lengths of pipe needed. Home Depot sells stock
pipe in one fixed length. You can divide each stock pipe in any way needed. Your job is
to figure out the minimum number of stock pipes required to satisfy the list of requests,
thereby saving money and minimizing waste.

Your job is to write a recursive function

int CutStock(Vector<int> & requests, int stockLength);


that takes two arguments—a vector of the lengths needed and the length of stock pipe
that Home Depot sells—and returns the minimum number of stock pipes needed to
service all requests in the vector. For example, if the vector contains [ 4, 3, 4, 1, 7, 8 ]
and the stock pipe length is 10, you can purchase three stock pipes and divide them as
follows:

Pipe 1: 4, 4, 1
Pipe 2: 3, 7
Pipe 3: 8

Doing so leaves you with two small remnants left over. There are other possible
arrangements that also fit into three stock pipes, but it cannot be done with fewer.

Download my solution for problem 4 here or  here.
Happy coding!!!