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

It consists of four problems and 2 warm-up problems.

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

**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.

**Problem 1. Karel goes home**

Your job in this problem is to write a recursive function

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).`int CountPaths(int street, int avenue)`

**Problem 2. Balancing parentheses**

Write a function

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.)`bool IsBalanced(string exp);`

**Free Lessons for Chruch Pianists:**

Free lessons, tips and downloads for church pianists

**DVD Courses (Reharmonization, Play by Ear!, Arranging, Accompanying, Theory for Church Pianists, etc.):**

Over 30 hours of DVD instruction for church pianists

**Problem 3. Cell phone mind-reading**

Write a function

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:`void ListCompletions(string digits, Lexicon & lex);`

palisade

palisaded

palisades

palisading

palish

rakis

rakish

rakishly

rakishness

sakis

**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.

**Happy coding!!!**