Pascal's Triangle

There is a mathematical structure known as Pascal's Triangle. It looks like this:

       1
      1 1
     1 2 1
    1 3 3 1
   1 4 6 4 1
    

Each value on the edge of the triangle is 1. Each interior value of the triangle is the sum of two values from the line above -- specifically, the one above and immediately to the left, and the one above and immediately to the right.

We can print this same triangle a bit differently:

  1
  1 1
  1 2 1
  1 3 3 1
  1 4 6 4 1
    

Here, each interior value is the sum of the number immediately above it, and the number immediately above it and one position to the left. If, at a given position in the triangle, one of these two values doesn't exist (that is, there is no value immediately above it, or there is no value above and to the left), then it is on the edge of the triangle and its value is 1.

Your assignment: Write a program named PascalTriangle that allows the user to specify the number of rows of Pascal's triangle that she wants to see. The program should then create a two-dimensional array of int that stores the triangle. Finally, it should print that two-dimensional array.

For example, using your program should look like this:

  (romulus)> java PascalTriangle 6

  1
  1 1
  1 2 1
  1 3 3 1
  1 4 6 4 1
  1 5 10 10 5 1
    

A few additional requirements: Not only should your program be named PascalTriangle, but the methods described above should also have specific names, parameter lists, and return types. Specifically, there must be two methods as follows:

• public static int[][] createTriangle (int height)

  Make a two-dimensional array of int that contains the first height rows of Pascal's Triangle.

• public static void print2DArray (int[][] array)

  Given a two-dimensional array of int, print it in row-major order. That is, print every element of the array at array[0] on one line, and then move to the next line. Then print every element of the array at array[1] on a single line, and so on.

Optional: Divide and conquer!

The following assignment is optional, but I strongly recommend it as practice/studying for the mid-term.

We have discussed, at length, the divide-and-conquer method for solving the lab-5 stock profit problem. I recommend that you try to program that solution.

How to do it: Make a copy of your lab-5 solution, and then rewrite the contents of your calculateMaxProfit method using the divide-and-conquer, recursive approach. To make a copy, follow these steps:

1. Change into your home directory.

   cd

2. Copy your lab-5 directory, making a new directory with the same contents.

   cp -r lab-5 new-lab-5

3. Change into the new, duplicate directory.

   cd new-lab-5

4. Open MyStockProfit.java with emacs. Delete the body of your old calculateMaxProfit method. Rewrite the body of that method using the divide-and-conquer approach.

Suggestion: You may find it helpful to write additional methods in MyStockProfit that support your calculateMaxProfit method. For example, for the task of finding the minimum value on the left half, or the maximum value on the right half, you may want to write separate methods for each and call them from calculateMaxProfit.

Submitting your work

Submit your work like this:

cs11-submit lab-6 PascalTriangle.java