CSC148H/A48H lab -- week 4

This document contains the instructions for the week 4 CSC148H/A48H lab. To earn your lab mark, you must actively participate in the lab. We mark you in order to ensure a serious attempt at learning, not to make careful critical judgments on your work.

This lab has you write several recursive algorithms. Remember your base cases!

Pair programming

Pick a navigator and driver. Expect to spend lots of time discussing the solutions; not all of them are obvious.

Palindromes

A palindrome is a word or phrase that reads the same forwards and backwards. Here are some examples:

Write a recursive function is_palindrome that takes a string as a parameter and returns True if its parameter is a palindrome, and False otherwise.

How many reachable cells?

Write a recursive function count_reachable that takes two parameters: (i) a 2D list (i.e., a list of lists), and (ii) a 2-element tuple. The list represents a region of cells, some of which are empty, and some of which are blocked (i.e., full). Each element of the 2D list is either 'E' (for empty), or 'B' (for blocked). The 2-element tuple indexes an element of the 2D list, and represents a starting position in the region of cells. More precisely, the first element of the tuple indexes a 1D list, and the second element indexes an element in the list indexed by the first tuple.

For example, the 2D list provided as a parameter might look like [['E','B'],['E','E']]. This represents the region of cells that looks like:

EB
EE

The tuple (0,0) indexes the upper left corner. The tuple (1,1) indexes the bottom right corner.

From any given empty cell you can move up, down, left, or right as long as the cell you move to is also empty.  count_reachable should return the number of cells that you can reach from the starting position, including the starting position itself.

For example, count_reachable( [['E','B'],['E','E']], (0,0)) should return 3.

The starting position will always be an empty cell, and you can also assume that a region of cells will be rectangular (in other words, each "row" in a region will have the same number of cells).

Hint: You may find it useful to modify the elements of the list as your function executes in order to mark where you've been.

After you've implemented the function, run the testcases in testcount.py. You need to first modify this file to bind the count_reachable name from your module's namespace to testcount's namespace (using from ... import ... ) .


Polynomials and Two-Level Functions

Consider the polynomial a_0x^n+a_1x^{n-1}+...+a_{n-1}x+a_n. If we try to evaluate this naively, we will first calculate x^n, then x^{n-1}, then x^{n-2} and so on. The problem is that we're doing a lot of extra work; consider that when we calculate x^n on the first iteration, we've also calculated x^{n-1} in the process, but on the next iteration we'll calculate x^{n-1} all over again. You can check badpoly.py for this inefficient evaluation method.

An alternative way to write the polynomial is (... (((a_0)x + a_1)x + a2) ... + a_{n-1})x + a_n. Now, on each iteration, all we have to do is multiply the previous result by x and add the next coefficient.

Write an iterative algorithm that implements this polynomial evaluation. Your function should take two parameters: an array containing the polynomial's coefficients, and a value for x. The coefficients represent the a_i values of each decreasing power of x in the polynomial. Here is a sample call.


>>> print polyIter ([2,3, 1], 4)
45

We can also write this function recursively. This will be your next exercise. Your recursive function should take three parameters: the coefficients array and x value as before, but also an n parameter that tells us where we are in the coefficient array. In a call of the function, n should equal one less than the length of the coefficient array. The above call on your iterative procedure would look like this for this recursive version:

print polyRec ([2,3, 1], 4, 2)

This is a clean recursive function, but now we've introduced a usability concern. Namely, the third argument passed to the function is just an artifact of our solution technique, not something the user should have to be concerned with. In addition, we can compute it from the first parameter using the length of the coefficient array. We would like to eliminate this parameter so that only the coefficients and x values are passed.

One way to do this is to create an inner function that takes one parameter n. The outer function (call it polyRec2) will take two parameters (coefficients and x), since this is the function the user will interact with. The body of polyRec2 consists of the definition of an inner function inner, which can access the parameters of polyRec2 by virtue of being nested within it. After defining inner, recPoly2 can start the execution of inner by supplying all three parameters (two of them received directly from the user; the third derived as one less than the length of the coefficient array). Implement this version of the algorithm.

This technique is called a two-level function: the outer function is what the user interacts with, and we should not require the user to supply (what he or she feels are meaningless) parameters. We instead create an inner function that uses the additional parameters, and call it from the outer function so that the actual computation can take place. Think about other advantages of this two-level approach (hint: are we doing less work when making a recursive call?). Discuss your ideas with your TA.

Now imagine a new function that we want to provide our users. The user is to supply two parameters A and B to the function, but we need to use a third parameter C to facilitate the recursion. We thus create an inner function again. However, unlike in the polynomial example, imagine that, in addition to C changing, one of the user's two parameters also changes on recursive calls. What would the definition of the inner function look like now? Discuss your answer with your TA.