Lab 4: Recursion

This week we will pratice recursion – with Karel, and with a special-purpose calculator.

This is the farmer sowing the corn, that kept the cock that
crowed in the morn, that waked the priest all shaven and
shorn, that married the man all tattered and torn, that kissed
the maiden all forlorn, that milked the cow with the crumpled
horn, that tossed the dog, that worried the cat, that killed
the rat, that ate the malt that lay in the house that Jack
built.

Children's song "The House that Jack Built", from 
http://www.ling.upenn.edu/~dringe/CorpStuff/Thesis/IntroSyntax.html#detour

Recursion is a phenomena, that exist not only in mathematics, but also in linguistics and physics, arts ….

Snap link: the URL to open Snap! with the environment for this week already loaded is here.

Marking rubric: Getting either one of the two questions right is worth 70%, getting the other one right is worth another 30% of this assignment.

Excercise 4.1 A calculator for combinations (50%)

Motivation:

There are 10 friends wanting to play basketball, how many different arrangements are there to split them into two teams of 5?
There are 8 courses to choose from in Semester 2. You want to take one of them because a good friend is taking it, and need to choose the other three. How many possible choices do you have for the remaining 3 courses?

More broadly, computing combinations is useful in other scientific problems, such as:

Sampling design in ecology, for example https://theoreticalecology.wordpress.com/2014/01/14/sampling-design-combinatorics/
Combinatorial chemistry for designing and discovering drugs, as illustrated in this video.

Calculation: Here is a standard recipe for counting combinations. One way to visualize this recipe is to pile such counts as a triangle, known as Pascal’s triangle. The $k$ -th number in the $n$ -th row is the number of combinations for choosing $(k)$ -items out of a total of $n$ items. Note that you should count both $n$ and $k$ from zero, not from $1$ .

For example, the number $1$ circled in green means there is one way to take $0$ items among $3$ choices, denoted as $C(3,0)$ ; the number $6$ in the blue circle in the figure is the number of taking $k=2$ items from a collection of $n=4$ items, , denoted as $C(4,2)$ .

This triangle has two prominent properties, which will allow us to construct the solution to $C(n,k)$ for any number of choices $n$ and size of selection $k$ .

The boundary of this triangle are all $1$ s. Or intuitively, there is only one way to take $0$ items or all $n$ items from $n$ choices.

A number in the middle of the triangle is the sum of the two number on its shoulder rows above. Intuitively, let’s say we label the first one among $n$ items as “special”, and the combination $C(n,k)$ now breaks down into two cases: (A) We include the special item in the selection, then the problem becomes taking $k-1$ items among the remaining $n-1$ choices (i.e. $C(n-1, k-1)$ ). (B) We do not include the special item in the selection, then we still need to take $k$ items among the remaining $n-1$ choices (i.e. $C(n-1, k-1)$ ). Adding the results from these two possibilities will give us the number of combinations gives us $C(n, k)$ . This insight can be summarized with the following equation, and by the animation on the right.

$$C(n,k) = C(n-1,k-1) + C(n-1,k)$$

Programming:

In the Snap workspace you will find this block , its content has been left blank.

Finish the implementation for , with the following summary of a recursive solution to Pascal’s Triangle.

if k=0 OR k=n
	report 1
otherwise
	report compute_combination(n-1, k-1) + compute_combination(n-1, k)

Note: Your code should check for invalid input. i.e. n and k should be integers, otherwise report error and stop; and k should be less or equal than n, otherwise return 0.

Testing your block: Here, you should test your block for syntax (i.e. it runs and reports back a number), but also compare its results against known results of combinations, such as on the triangle above, and other values of $n$ and $k$ from online calculator http://stattrek.com/online-calculator/combinations-permutations.aspx

Showing errors: If you need to output a warning or an error to the user, you can get Karel to say it for you! warning

Explore more (this part is worth 0 marks):

This excercise focuses on buidling a recursive solution for the combination problem. There are ready-made formulas for computing combinations, such as listed on this page http://www.mathwords.com/c/combination_formula.htm You can compare the two solutions.

First implement another block for the formula on the webpage $C(n,k)=\dfrac{n (n-1)\ldots(n-k+1)}{k!}$ using loops.
Call both blocks with some larger $n$ and $k$ , e.g., $n=10$ ( $15$ , $20$ , $25$ , etc.) and $k=5$ .

Which block is faster? Why? Which Solution do you prefer?

Excercise 4.2 Karel as a navigator: following a trace and coming back (50%)

In Excercise 2.1 you told Karel how to follow a trail of beepers. In Excercise 4.2 Karel will gain navigation skills, by tracing the same trail backwards and return to where she started, as follows.

Karel start from the lower left corner of the grid.
Karel follows a trail of beepers until the end, picks up the beepers (at most one at each location) as she goes.
Karel stacks all the collected beepers at the end of the trail.
Karel traces back to the origin on the same trail. Furthermore, she marks her path with a beeper whenever she has made a turn.

You will find a block Follow trail and come back in the motion category, put your implementation there. You should feel free to change the input of this block as you see fit, or change it to a reporter if you feel it is useful to return values. Leaving it with a default input of 0 also works.

Here are two ways that you can implement this.

Method 1 – one step at a time, using recursion

Follow trail and come back (beepers to drop = 0)

Find the next beeper in the trail
If it is straight ahead
	go forward one step
	pick up the beeper
	Follow trail and come back (beepers to drop + 1)
	go backward one step

If it is left or right
	turn and go forward one step
	pick up the beeper
	Follow trail and come back (beepers to drop)
	go backward one step
	drop the beeper (to mark the turn)
	turn back

If there is no next beeper
	put down beeper (beepers to drop) times

Method 2 – using arrays and reusing “Follow a Trail” from lab 2

Follow a Trail -- but modified to record trail directions in an array

put down beepers at the end (remember to keep enough to mark the turns!)

Follow the recorded trail backwards to the origin, dropping a beeper at each turn

You are free to use either method to implement the solution.

Note that a few utiltiy blocks such as “Beeper in front?” and “Move Karel backward” are included. After each attempt, you can use these set of blocks to clear the field and put Karel back to the lower-left corner.

Testing your block: The project file contains three different trails for you to test your program (as shown below), lay them out using the blocks called “Lay short trail” (recommended for debugging), “Lay beeper trail” and “Lay a long trail” – as shown below.

After executing your block for the “long trail” on the right, the stage would look like this:

Submission: You need to export and submit the blocks called “compute combinations” and “Follow trail and come back”, along with any other blocks you created that are used by these blocks. Follow the submission instructions for file naming and block testing.

Image credits: