CS 2213/2211 -- Recitation 8

CS 2213/2211
Advanced Programming
Spring 2005
Recitation 8: Pascal's Triangle
    Week 8: Mar 8-10
Due (on time): 2005-03-22  23:59:59
Due (late):        2005-03-27  23:59:59

Recitation 8 should be submitted following directions at: submissions with deadlines

2005-03-22 23:59:59 (that's Tuesday, 22 March 2005, 11:59:59 pm) for full credit.
2005-03-27 23:59:59 (that's Sunday, 27 March 2005, 11:59:59 pm) for 75% credit.

Introduction: This recitation works on areas:

2-dimensional arrays of both types.
Preprocessor functions, also known as macros.
Simulating a 2-dimensional array in a 1-dimensional one.

Pascal's Triangle: Pascal's triangle is a triangular array of numbers that extends indefinitely far. Here are the first 8 rows:


                        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

It starts with 1's at the beginning and end of each row. All other entries are the sum of the two entries above. Pascal's tringle gives useful numbers. For example, the coefficients of (x + y)ⁿ are the numbers in the nth row, where the initial row (with just one element) is the 0th row:

(x + y)⁵ = 1 x⁵ + 5 x⁴ + 10 x³ y² + 10 x² y³ + 5 x y⁴ + 1 y⁵

As another example,since (1 + 1)ⁿ = 2ⁿ, the sum of the entries in the nth row is 2ⁿ.

Display of Pascal's Triangle: We will usually display Pascal's Triangle with the rows lined up at the right, as follows:


Pascal's Triangle of Size 8:

Cols   |   0   1   2   3   4   5   6   7
-------+--------------------------------
Row  0 |   1
Row  1 |   1   1
Row  2 |   1   2   1
Row  3 |   1   3   3   1
Row  4 |   1   4   6   4   1
Row  5 |   1   5  10  10   5   1
Row  6 |   1   6  15  20  15   6   1
Row  7 |   1   7  21  35  35  21   7   1

Thus Pascal's Triangle of size 8 will fit into the lower left corner of an 8-by-8 2-dimensional array, where we don't use the upper right triangle (off the diagonal).

A. Construct Pascal's Triangle: Here are the requirements for this part:

Requirements for Part A

Requirements for Part A
Use a constant, such as `#define N 8` for the size of the triangle. Use an array declaration (inside `main`) such as `int a[N][N];`. Use a loop to initialize the entries `a[i][0]` and `a[i][i]` of row `i` to `1`. Use a double loop to fill in all the other entries. (Leave array entries `a[i][j]` for `i < j` uninitialized.) Print the triangle, without printing the uninitialized entries. Use a separate function to do the printing, and pass the array as a parameter. Your printout should look exactly the same as what is displayed above with size `8`, including the row and column numbers and the horizontal and vertical lines. [Hint: to output the numbers use a `"%4i"` format.] With size `12`, it should look like Pascal's Triangle of size 12

Use a constant, such as #define N 8 for the size of the triangle.
Use an array declaration (inside main) such as int a[N][N];.
Use a loop to initialize the entries a[i][0] and a[i][i] of row i to 1.
Use a double loop to fill in all the other entries. (Leave array entries a[i][j] for i < j uninitialized.)
Print the triangle, without printing the uninitialized entries.
Use a separate function to do the printing, and pass the array as a parameter.
Your printout should look exactly the same as what is displayed above with size 8, including the row and column numbers and the horizontal and vertical lines. [Hint: to output the numbers use a "%4i" format.]
With size 12, it should look like Pascal's Triangle of size 12

B. Use a preprocessor function for the array references: See the first part of Section 5.3, pages 105-108, in the Weiss text for preprocessor functions (called "macros" by Weiss). Here are the requirements:

Requirements for Part B

Requirements for Part B
Use a macro definition like: `#define A(x,y) a[(x)][(y)]`. (The parentheses around `x` and `y` are not needed here, but should in general always be added.) Replace each occurrence of a reference like `a[i][j]` with `A(i,j)`. If your source is called `pascal.c`, run the command % cc -E pascal.c or % cc -E pascal.c > pascal.pre to produce the preprocessor output. Run the program with sizes `8` and `12`, to see that you get the same output as before.

Use a macro definition like: #define A(x,y) a[(x)][(y)]. (The parentheses around x and y are not needed here, but should in general always be added.)
Replace each occurrence of a reference like a[i][j] with A(i,j).
If your source is called pascal.c, run the command
to produce the preprocessor output.
Run the program with sizes 8 and 12, to see that you get the same output as before.

C. Change the storage to an array of 1-dimensional arrays: Here are the requirements:

Requirements for Part C

Requirements for Part C
Use `malloc` for all storage allocation. Use `scanf` to read the size of Pascal's Triangle, call it `n`. Allocate an array of `n` pointers to `int`. The type of this array will be `int **`. For each of the above pointers to `int`, allocate an array of `int`. The `i`th pointer should have an array of size `i+1` allocated. Keep the rest of the program the same, and run it for size `8` just to check that it is working correctly. Don't include this with your submission. Replace the macro definition with another array element reference that has no square brackets in it. (The "natural" way to reference such an array of pointers to pointers.) This is the program code you should hand in. Run this program for sizes `8` and `12` and get the same output. These are the runs you should hand in.

Use malloc for all storage allocation.
Use scanf to read the size of Pascal's Triangle, call it n.
Allocate an array of n pointers to int. The type of this array will be int **.
For each of the above pointers to int, allocate an array of int. The ith pointer should have an array of size i+1 allocated.
Keep the rest of the program the same, and run it for size 8 just to check that it is working correctly. Don't include this with your submission.
Replace the macro definition with another array element reference that has no square brackets in it. (The "natural" way to reference such an array of pointers to pointers.) This is the program code you should hand in.
Run this program for sizes 8 and 12 and get the same output. These are the runs you should hand in.

D. Simulating a triangular array inside a 1-dimensional array: In the same way that a regular 2-dimensional array is implemented in C by simulating it inside a 1-dimensional array, one can simulate a triangular array inside a 1-dimensional array. The triangular array will be storage for Pascal's Triangle of a certain size n. In the 1-dimensional array, you lay out the row number 0 of length 1, then the row number 1 of length 2, then the row number 2 of length 3, and so on until row number n-1 of length n. Looked at horizontally, here is the picture:


Array contents: a[0][0] a[1][0] a[1][1] a[2][0] a[2][1] a[2][2] a[3][0]

Array index:       0       1       2       3       4       5       6

In order to implement this, all you need is a "magic" function that, given indexes i and j, will compute the proper index below them in the 1-dimensional array used for the actual storage. Thus we just need a function A(i,j) with the properties that:

A(0,0) = 0

A(1,0) = 1

A(1,1) = 2

A(2,0) = 3

A(2,1) = 4

A(2,2) = 5

A(3,0) = 6

A(3,1) = 7

There are at least three ways to construct this function:

To get to the location for A(i,j), start at the address of the 1-dimentional array. Then skip over i rows of lengths 1 + 2 + 3 + ... + i and then go j locations further.
Guess that the function A should have the form A(i,j) = a*i² + b*i + c*j + d for fixed constants a, b, c, and d. Use 4 known values for the function to get 4 equations in 4 unknowns, and solve for the constants a, b, c, and d.
Just fiddle around with formulas until you find the unique one that works.

Here are the requirements for this part:

Requirements for Part D

Requirements for Part D
Use `malloc` for all storage allocation. Use `scanf` to read the size of Pascal's Triangle, call it `n`. Allocate a 1-dimensional array of `int`s of exactly the correct size to hold all the numbers in Pascal's Triangle of size `n`. (This will just be `1 + 2 + 3 + ... + n` integer locations for the sequence of rows.) Replace the macro definition with another definition that uses the "magic" formula that you came up with above. The rest of your program can be the same as before. Run the program to produce Pascal's Triangles of sizes `8` and `12`. Please also print the array in which you simulate the triangle for size `8`, printing the index and array contents, for index from `0` to `35`. (I realize that I have added this late, so don't worry about it if you have completed the recitation.)

Use malloc for all storage allocation.
Use scanf to read the size of Pascal's Triangle, call it n.
Allocate a 1-dimensional array of ints of exactly the correct size to hold all the numbers in Pascal's Triangle of size n. (This will just be 1 + 2 + 3 + ... + n integer locations for the sequence of rows.)
Replace the macro definition with another definition that uses the "magic" formula that you came up with above.
The rest of your program can be the same as before.
Run the program to produce Pascal's Triangles of sizes 8 and 12.
Please also print the array in which you simulate the triangle for size 8, printing the index and array contents, for index from 0 to 35. (I realize that I have added this late, so don't worry about it if you have completed the recitation.)

E. Creating Pascal's Triangle in a Function: For this final part, you are to create Pascal's Triangle in a function, and get it back to the main function using an int *** parameter. First study the correct program at the link: Parameters, which shows how to pass the address of a pointer to an array of arrays to a function, create the array of arrays inside the function, and be able to access it after returning from the function.

Here are the requirements for this part:

Requirements for Part E

Requirements for Part E
Start work with the function `create_string` on the right in the link Parameters. (The side labeled "Correct Method".) Answer the question there: What is wrong with the program labeled "Incorrect Method"? Perhaps change the name of the `create_string` function (since it should create an array of arrays of `int`, not an array of strings), but include code so that it creates an instance of Pascal's Triangle as created in part C above. (You will have to change the parameter from `char *` to `int *`.) Inside `main` use `scanf` to read the size of Pascal's Triangle, call it `n`. Pass `n` to the function in the first item above. Run the program to produce Pascal's Triangle of size `8`.

Start work with the function create_string on the right in the link Parameters. (The side labeled "Correct Method".) Answer the question there: What is wrong with the program labeled "Incorrect Method"?
Perhaps change the name of the create_string function (since it should create an array of arrays of int, not an array of strings), but include code so that it creates an instance of Pascal's Triangle as created in part C above. (You will have to change the parameter from char *** to int ***.)
Inside main use scanf to read the size of Pascal's Triangle, call it n.
Pass n to the function in the first item above.
Run the program to produce Pascal's Triangle of size 8.

What you should submit: Refer to the submissions directions and to deadlines at the top of this page. The text file that you submit should first have Your Name, the Course Number, and the Recitation Number. The rest of the file should have the following in it, in the order below, and clearly labeled, including at the beginning the appropriate item letters: a, b, c, etc.

Contents of email submission for Recitation 8:
Last Name, First Name; Course Number; Recitation Number.
a. Give the C code for your program for part A and the results of runs of sizes 8 and 12.
b. Give the C code for your program for part B. Give the result of running the preprocessor on the program code. Then give the results of runs of sizes 8 and 12.
c. Give the C code for your program for part C (with the new storage allocation and the new macro). Give the result of running the preprocessor on the program code. Then give the results of runs of sizes 8 and 12.
d. Give the "magic" formula needed for part D above. Give the C code for your program for part D (with storage allocation for a single 1-dimensional array and the new macro based on the "magic" function). Give the result of running the preprocessor on the program code. Then give the results of runs of sizes 8 and 12. Also please print the array itself for size 8, for index from 0 to 35.
e. Give the C code for your program for part E. Then give the results of a run of size 8.

Revision date: 2005-03-09. (Please use ISO 8601, the International Standard.)