Monash University > School of Computer Science and Software Engineering > CSE1303 > Part B > Pracs > Prac B5
This prac covers material from lectures B01 to B13.
The formula nCr(n,r) returns the number of different possible ways of selecting r items from n items, when order doesn't matter. It can be computed with the following formula:
n! nCr(n,r) = --------------- (n-r)! * r!
where "!" is the factorial function.
The marks for Preparation will be awarded only if the preparation is completed before the start of the class.
Even if you do not get the marks for preparation, you will need to complete it before going on with the regular questions, because they will refer to its answers.
| from this many balls | pick this many | chances of winning |
|---|---|---|
| 20 | 5 | 1 in nCr(20,5) = 15504 |
| 20 | 6 | |
| 20 | 14 | |
| 39 | 6 | |
| 45 | 5 | |
| 45 | 6 |
(n)*(n-1)*(n-2)*...*(n-r+1) nCr(n,r) = --------------------------- (r)*(r-1)*(r-2)*...*1
Write an algorithm that computes nCr(n,r) using this formula.
Write a C program which reads two non-negative integers (n and r) from the user, and prints nCr(n,r).
When your C program works, translate it into MIPS assembly language and test it with SPIM.
Be aware of overflow. Combinatorial numbers get very large very quickly. If you use the mulou (multiply unsigned with overflow) instruction, you will receive a warning when a multiplication causes overflow, so you can at least know if the answer you produce is wrong. Unfortunately, this instruction is available in MIPS only, not C.
Try out both your C and MIPS programs to compute the chances of winning the lotteries listed in the Preparation above.
Another way of calculating nCr is through a construct called Pascal's Triangle. Each row has one more element than the last one, and the first and last elements of each row are always 1. All other elements in the triangle are formed by adding the two elements above (to the left and right). The first few rows of Pascal's Triangle look like this:
| 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 |
| ... ... ... ... ... |
nCr(n,r) can be read from the table as the rth element of the nth row (counting from zero in both cases). For example, nCr(6,3) = 20.
Write a C program that prints out rows 0 through n of Pascal's Triangle. You can assume that n is no bigger than 20.
Note that each row depends on the previous row, and only the previous row; this means that one-dimensional arrays will be required in your solution. It is not necessary to have the entire triangle in memory at one time; you can generate it one row at a time, and print what you've got before moving on.
Some sample output (with a skewed triangle; you don't have to worry about fancy centring or alignment):
How many rows? 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1
Translate your C program into MIPS. Try to keep your solution as faithful to the original C code as possible.
This program is possibly the first large-scale program you've written in MIPS. If you tackle the code a piece at a time, it won't seem so daunting. Here are some hints for making the job easier.
- Work on making your C code simpler before you start. A less convoluted C program will translate to a less convoluted MIPS program.
- Take your original C code, and insert a "#" character at the start of every line. (If you're using a sophisticated editor like vi, your demonstrator will know a quick way of doing this.) Now you have a MIPS program made entirely of comments which look like the C code you're trying to translate. Fill in the missing MIPS code around the comments. This will help you keep track of where you are up to, and it will stop your demonstrator hounding you for writing uncommented code!
- Don't translate more than about three statements of C without testing your program on SPIM. If you do too much at once, you won't be able to pinpoint when a bug was introduced.
- If it's a loop or if-statement that you're translating, do it on its own, and then make sure that it works. Put print statements (system calls) in to check the values of loop counters and other important variables.
- Work from the outside in, or the inside out, whichever works best for you. This program has at least two nested loops. Don't even begin to work on the inner loop until the outer one looks like it's working right. (Swap "inner" and "outer" if that's how you prefer to work.)
- Work on getting the printing code done first. You'll need it in the final program, and the sooner you see your program producing some output, the more you'll want to finish it.
- Be faithful, to the letter of the law, when it comes to translating C statements into MIPS. The more shortcuts you take, the more likely you are going to introduce a subtle bug that will take you (and your demonstrator) hours to locate. Take no shortcuts at all, and you won't risk this happening.
- When you come to writing functions, translate them one at a time, and test each before moving on.
Modify your MIPS program from Question 2 so that it prints only the last requested row of Pascal's triangle. For instance, with an input of 5, the program will print 1 5 10 10 5 1.
Now change your MIPS program so that, for each number, it instead prints a row of asterisks equal to the number, on its own line. For instance, with an input of 5, you would see:
* ***** ********** ********** ***** *
This simple graph is a sideways rendition of a function known as the binomial distribution. It is an approximation of the normal distribution; for larger values of n, the approximation gets ever closer.
As n gets larger, the rows of asterisks become unmanageably long. Change your MIPS program so that it scales the printed rows such that the longest rows contain no more than 70 asterisks.
Modify your answer to Question 1 so that it performs division in preference to multiplication (when doing so would not produce any remainder), to keep the partial result as small as possible.
Enter a number: 20
*
***
***
***
***
***
*****
*****
*****
*****
*****
*******
*******
*******
*******
*********
*********
*********
***********
*********************
Last modified 2002-01-29