CMPU-145, Spring 2013 Lab 9 Monday, April 22, 2013 1. Computing Pascal's Triangle. Recall that Pascal's Triangle looks like this: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 etc. Notice that each "interior" entry (i.e., each entry that is not a 1) is equal to the sum of its diagonally adjacent parents from the previous row. You can use this fact to compute successive rows of Pascal's Triangle as follows. Well, consider an example: Let LISTY be a list containing one row: (1 4 6 4 1) Next, CONS a 0 onto the front of LISTY: (0 1 4 6 4 1) Next, consider the REVERSE of that list: (1 4 6 4 1 0) Finally, add the corresponding elements of the last two lists to get: (1 5 10 10 5 1) Hey! That's the next row!! Define a function, called PAIRWISE-ADD, that takes two lists of numbers as its only inputs. It should form a new list of the same length whose entries are formed by summing the correspnoding numbers from the input lists. (This is what we did in the last step above.) So, for example: > (pairwise-add '(1 2 3 4) '(10 20 30 40)) (11 22 33 44) Next, define a function, called GET-PASCAL-ROW, that takes a non-negative integer, N, as its only input. It should return as its output a list containing the entries from the Nth row of Pascal's Triangle, as illustrated below: > (get-pascal-row 0) (1) > (get-pascal-row 1) (1 1) > (get-pascal-row 2) (1 2 1) > (get-pascal-row 3) (1 3 3 1) Finally, define a function, called PRINT-PASCAL, that takes a non-negative integer, N, as its only input. It should *NOT* generate any output value. Instead, it should have the SIDE EFFECT of printing out the first N rows of Pascal's Triangle in the interactions window, as illustrated below: > (print-pascal 3) (1) (1 1) (1 2 1) > (print-pascal 5) (1) (1 1) (1 2 1) (1 3 3 1) (1 4 6 4 1) 2. Recall that a powerball TICKET contains: (1) a list of five numbers, chosen from {1,2,...,59} where order doesn't matter and repetitions are not allowed; and (2) a single number from {1,2,...,35}. Here's an example: (3,8,9,12,18; 15). In this case, the first five numbers belong to the set {1,2,...,59} and the last number (the "powerball") belongs to the set {1,2,...,35}. Here's another example, which illustrates that the powerball can also appear among the first five numbers: (3,8,9,12,18; 12). After all tickets have been purchased, the drawing is held. It consists of five numbers being chosen from {1,2,...,59}; and one number being chosen from {1,2,...,35}. For convenience, we shall refer to these six numbers as the DRAW TICKET. The winnings (if any) for a given ticket are determined by how many of the first five numbers on the ticket match the first five numbers from the DRAW TICKET; and whether or not the powerball on the ticket matches the powerball on the DRAW TICKET. For example, if the draw ticket is (1,2,3,4,5; 20) and your ticket is (2,4,16,18,20; 24), then your first five numbers contain 2 matches with the first five numbers on the winning ticket (i.e., 2 and 4); and you do not match the powerball. Thus, we say that your ticket has 2 matches but no powerball. PART A. Define a global variable, named *num-powerball-tix*, whose value is the number of distinct powerball tickets. (This is a big number!) Pretend that the DRAW TICKET is known in advance to be (1,2,3,4,5; 20). Define another variable, named *num-ways-match-2-w-pb*, whose value is the number of distinct powerball tickets whose first five numbers have exactly TWO matches with the first five numbers of the DRAW TICKET *and* whose powerball matches the powerball of the DRAW TICKET. Define yet another variable, named *prob-match-2-w-pb*, whose value is the probability that a randomly generated powerball ticket will match exactly TWO numbers from the DRAW TICKET while also matching its powerball. Again, assume the DRAW TICKET is known in advance to be (1,2,3,4,5; 20). Display the values of these three variables in the interactions window using the TESTER function. PART B. Use GEN-AND-TEST to estimate the probability computed above. First, you will need a function, called GEN-RAND-PB-TICKET, that takes NO inputs. It should generate as its output a list of the form, (A1 A2 A3 A4 A5 A6), where the first five numbers are drawn from {1,2,3,...,59} such that order doesn't matter, and repetition is not allowed (i.e., O-R-); and the sixth number is chosen at random from {1,2,...,35}. HINT: Define a global variable, named *pb-nums-59*, whose value is a list of the integers from 1 to 59, inclusive. HINT: Use RAND-CHOOSE-K, defined in asmt5-helper.txt, to pick 5 numbers from the set {1,2,...,59}; and use RANDOM to pick a number from {1,2,...,35}. (But be careful! The powerball must be the SIXTH number in the randomly generated ticket!) Next, define a function, called MATCHES-2-W-PB?, that takes as its only input a powerball ticket (i.e., a list of 6 numbers as described above). It should return #t if (1) the first five numbers on that ticket contain exactly TWO matches among the first five numbers on the DRAW TICKET (1,2,3,4,5; 20); and (2) the sixth number on that ticket matches the powerball on the DRAW TICKET (1,2,3,4,5; 20). HINT: You may wish to define a helper function, NUM-MATCHES, that takes two lists as its inputs. It should return the number of matches among the two lists (i.e., the number of elements in the intersection of the two lists). WARNING: Only apply this function to the first five numbers from each ticket (i.e., not including the powerball). Run GEN-AND-TEST using a large number of trials (e.g., one million) to estimate the probability of a randomly generated ticket having the desired matches with the DRAW TICKET. Your answer should roughly match the answer you got in problem one, especially if you use a large number of trials. ------------ When you are done, be sure to ask me or one of the coaches to come over to look at your work. Then submit as usual using submit145.