|
Pascal and More! |
In this lab you will learn a hodgepodge of things. The most important, however is how to play with Pascal's Triangle. You will learn the importance of caching or at least finding efficient algorithms to do work.
Before we can get into the good stuff, we need to take a look at searching methods. Where will you use this in playing with Pascal's Triangle? You probably won't which is why we'll only talk about them at a minimum. These searching methods come into play later on when you're asked to play around with mazes.
We're going to look at two types of searching through trees: depth first and breadth first. Just like the names of the searching algorithms suggest, one of them digs down into the tree first while the other concentrates on finding something closest to the root of the tree.
This is exactly as it sounds, you go all the way down the tree before you move over. This is kind of like a partial inorder traversal, but you stop when you find what you're looking for. Here's an illustration of depth first where we are searching for the dark node:
Notice that we had to look at six different nodes, and we did (in a way) eight steps. There's got to be a faster way, huh?
This is a little different. First, let me define a new term:
So basically breadth-first searching searches the tree by node-depth. All the nodes at depth 0 are searched (from left to right - inorder), then all the nodes at depth 1, then 2 and so on until a match is found.
- Node-Depth:
- the number of levels a node is below the root. If you were in a family tree, and you had a great-grandfather, then you would be at node-depth of 3 (father, grand, great). Check out the graph.
This time we only had to look at five nodes, much more convienient. Essentially, this one took four steps, assumming we remember the nodes where we were previously.
Alright, enough banter about searching trees, and now onto stuff that's more interesting: pascal's triangle!
"Pascal's triangle is an array of numbers that is constructed by beginning with a row of two ones: 1 1. Each new row after [that] starts and ends with a one, and the numbers are formed by adding the numbers above and on either side of them."For our sake, we'll say it starts with the zeroth row as a single 1. So Pascal's triangle with one row is just the number 1. Although the triangle is traditionally displayed as isosceles (with the top in the middle such as shown at the top of this page), my triangles are lazy and lean against an imaginary wall:
Definition taken from University of Colorado Boulder's Discrete Math website.
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1They're also easier to computer-generate that way. So that triangle was of size six, the last row is the fifth (remember it is zero-based) and it is easy to tell which row we're in given the second entry in a row.
That's all fine and dandy, but how do we come up with just one entry in the table? There are many ways, but lets attack the most straightforward recursive way.
Given a row and column (that four I've circled in red is in row 4 column 1) we can find an entry based on two entries in the previous row like this:
Maybe now it helps to have the triangles leaning against the wall. We can think of them as being in a table (hint, hint)!pascal(row, col) = pascal(row-1, col-1) + pascal(row-1, col)
But we know more about the triangle as a whole:
With a simple loop, we can make big, fun triangles!pascal(0, 0) = 1 pascal(row, 0) = 1 pascal(row, row) = 1 pascal(row, col) = pascal(row-1, col-1) + pascal(row-1, col)
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1 1 11 55 165 330 462 462 330 165 55 11 1 1 12 66 220 495 792 924 792 495 220 66 12 1 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1
I've written a simple little double-loop procedure that generates a triangle of any given length. It loops through the number of rows desired, and for each row it generates and prints out every single entry in the row. It isn't the most efficient, but it works. Here is the code:
(define pascal-printer
(lambda (pascal-proc n)
(let loop ([row 0])
(if (> row n)
(printf "Done ~%") ;end of triangle
(begin
(let loop2 ([col 0])
(if (> col row)
(printf "~%") ;end of row
(begin
(printf "~s " (pascal-proc row col))
(loop2 (add1 col)))))
(loop (add1 row)))))))
It prints "Done" when it is finished in case you're making a
HUGE triangle and want to know when it finishes.
There's one catch to that printer. If you look closely, you'll notce that it takes a pascal-proc argument. That means you have to write a procedure that will generate a single number in the triangle given a row and column. You get to do that later.
The idea of saving already calculated data was discussed in depth in the homework. Here's a quick run-down:
Well, think about what you need to know to calculate row 5 column 2 (I'll denote this as (5,2) from now on): You need to know (4,1) and (4,2).
I've circled (5,2) in red below, and the regions of all the numbers we have to calculate in order to get just (4,1) and (4,2) are in different colors. Don't forget, however that for each number in the sub-regions, we need to calculate other numbers! So in the case of (5,2), the number at (2,1) is calculated at least four times! As the number goes deeper, the number of times that each element is calculated grows at an obscene rate. If we cache each entry after calculating it once, all the overlap in the sub-regions goes away and we're left with calculating each entry in Pascal's triangle only once.
Yay! It's your weekly playtime! Exercise 1 deals with the first part of this lab (searches) and exercise 2 deals with the triangle.
For this whole exercise, refer to this figure:
Copy the figure into your lab book. Draw arrows (in the fashion I showed in previous figures) to show the steps on a depth-first search to the node marked 18
Again, copy the figure into your lab book. Draw arrows (in the fashion I showed in previous figures) to show the steps on a bredth-first search to the node marked 18
copy this table into your lab book and fill in the number of nodes (including the one you're searching for and the root) touched by each of the different searches to the different nodes. I've provided two for you.
Node: 36 53 15 65 8 Depth-First 6 Breadth-First 3
This exercise actually involves some coding and pascal's triangle. Feel free to use my pascal printer if you want (you don't have to write the code in your lab book). If you do use it, mention it in your write-up and when you use it write down how you used it (what you typed at the command-line) and what it printed out. If you print out a triangle with more than 10 rows, just write down the last row. Also, for the second part you may want to use a vector of vectors (such as a table).
Define pascal as a procedure that takes two arguments: row and col (in that order). Have it return a number that corresponds to the pascal triangle value in that row and column. Remember, the tip of the triangle is at row zero column zero. Here are a couple (but not all) test cases:
> (pascal 0 0) 1 > (pascal 100 0) 1 > (pascal 10 10) 1 > (pascal 15 10) 3003
Re-implement your pascal procedure to use caching. This means the following things: you will need to define your recursive procedure inside (using a named let or define) and also need to remember your cache. Here's some code to get you started:
(define pascal-cached
(lambda (row col)
(let ([cache ------])
(let loop ------))))
Fill in the first ------ with something to make a table for
the cache, and the second one with whatever you need to do the pascal
calculation (and be sure to check the cache before doing any recursive
calculations). When you've finished testing your code for this, time it
against your other implementation for different rows and columns.
Report how much faster the cached version is in each test.