CS560 Alpha and Equational Programming: getting started

Introduction

The purpose of this exercise is for you to learn how to write polyhedral equational programs in Alpha, how to use the AlphaZ systems and run such programs.

Problem 1

Start with the program for Pascal's triangle that was developed in class (or with the one in the Pascal directory when you check out AlphaZ) and complete it. Extend the definition of the program so that it returns the binomial coefficients for n, and also the first n Fibonacci numbers. In order to do this, you will need to understand how to write reductions in Alpha, and the LU Decomposition tutorial off the AlphaZ wiki will be useful to do this. Don't worry if you don't get it right away (it will be explained in class on Tuesday) but continue with the rest of the assignment.

Problem 2

In this problem you will understand the relation between the number of points in a polyhedron (it's "volume") and the asymptotic computational complexity of equational programs.

Write an Alpha program to compute the n-th Fibonacci number using the standard definition. It should have no input variable, and should return a single scalar (i.e., a zero-dimensional variable). Change the data-type of the variables to float or double in order to avoid integer overflow. Now determine the execution times of the two programs for reasonably large values of N, plot this on a log-log scale and determine the asymptotic complexity of the two programs.

Modify the C code generated by AlphaZ for the second (standard) Fibonacci program as follows. Replace the evaluation function called by the wrapper by the following simple recursive definition.

```float fib(int n){
if (0<=n && n<= 1) return 1.;
else return fib(n-1) + fib(n-2);
```
Experimentally determine the complexity of this program and report it.

Problem 3

Redo Problem 1, but now using Blaise Pascal's original description of the table: the domain of the variable T should be {i,j | 0 <= (i,j) <= i+j <= N}. The trick now is to determine the correct way to describe the reduction. For this, you may find it useful to draw out the triangle on a paper, and draw the lines connecting the points be accumulated to produce the answer. The equation for this line should give you an idea about how to write the reduction.

You will turn in only a tarball of your code including the generated files (using the same structure as in AlphaZ (a set of directories for the different Alpha programs, and one (under test-out) for the generated (and modified) C code. Separately, you will also turn in a pdf report documenting your experiments and results.