See the grading guidelines for information about grading policies and turn-in procedures.
NOTE: there are two types of homeworks - assignments, which will be frequent and not graded but discussed in class, and projects, which will (mostly or entirely) be done as group work and will be graded. Projects will be clearly identified below, and will be described in individual project pages linked to this one.
Whether assignments or projects, late homeworks will not be accepted.
What operating system runs on the laptop computer you will use for coursework in CAAM 420? What is its relation to Unix?
One page (or less) should be sufficient; don't worry too much about formatting, but make sure it's readable. Name the file "hw1.txt" and Upload to your repository by the due date.
Structure your file as follows:
The hw_2 directory should contain both the source, as hw1.tex, and the pdflatex output, as hw1.pdf.
submit a directory named hw_3 under your main repo directory, with your solution of the problem as its contents (hw_3/hw3.c).
The 2-vector function (cos t, sin t) obeys the system of differential equations
d/dt (cos t) = -sin t,
d/dt (sin t) = cos t
with initial conditions cos 0 = 1, sin 0 = 0.
Euler's method to approximate the solution of this system on the interval [0,pi] goes like this: choose a positive integer N, and divide the interval [0, pi] into subintervals of length pi/N, with N+1 endpoints t0, t1, ... tn: the ith endpoint is ti = i(pi/N). Compute approximate values (c[i], s[i]) for cos ti, sin ti, i=0,...,N, by following this rule:
c[0]=1, s[0]=0
for i = 1,...N,
c[i] = c[i-1] - s[i-1](pi/N)
s[i] = s[i-1] + c[i-1](pi/N)
Write a program implementing Euler's method. Store (c[i], s[i], i=0,...N) in C arrays of length N+1. Write a "for" loop to implement the recursive rule above. Print the value of c[i] for each i.
Choosing N: Note that cos pi = -1. Try N=2, N=3, ..., until you find an N for which c[N] is a 1-digit approximation to -1, i.e. c[N] is between -1.1 and -0.9.
Submit your work in a directory hw_4 under your repository root, containing your code as hw4.c. The submitted version should have N set to a value satisfying the 1-digit criterion stated in the last paragraph. If you use cstd.h, include it in your hw_4 directory.
The IEEE standard decrees that floats should consist of 32 bits, as follows:
Having worked this out, write a program which prints
double dpi = 4.0*atan(1.0);
Then assign dpi to a float fpi, and print them both with 15 significant digits (conversion %20.15e in printf). At which digit do they start to differ? This tells you roughly how many digits a float represents.
Condition: You may consult with the instructor and TAs, who may provide relevant advice, but will not directly assist you in doing the assignment. You may not discuss the assignment with your fellow students prior to turnin.
Lab: TAs will be available in Sewall 305 on Friday 27 Sep during the usual class hour to provide advice.
Objective: write a program printing the binary representation of a float, in the following format:
SIGN=... MANTISSA=... EXPSIGN=... EXPONENT=...
The sign (SIGN) and exponent sign (EXPSIGN) should be printed as 0 or 1, meaning positive or negative. The mantissa should be printed as a string of 23 characters, each either '0' or '1'. The most significan bit, i.e. the coefficient of the highest power of 2, should come first (this may not be the way the bits are stored in the machine, but it is the natural way they would be presented in text). The exponent should be printed as a string of seven characters, each either 0 or 1.
Your program file should be called float2bin.c. It should generate a command (say a.out) which is called as follows:
./a.out [real number in floating point notation]
and print the binary representation in the format described above.
Hints:
float x;
...
unsigned int * u = (unsigned int *)&x;
An unsigned int is just a pile of bits, so now *u has your 0's and 1's.
Turnin: Submit a directory hw_5 to your repository, containing float2bin.c, and any other files (for example cstd.h, if you use it) necessary to run the program. It should be possible to type "gcc float2bin.c" in your directory and obtain the command (as a.out) performing the task described above.
Grading: I will test your program by running it on several examples, to be revealed later.
Condition: This assignment is NOT pledged. You may work with other students, and consult the TAs and Instructor for advice. HOWEVER, all text, including code, in your turnin directory must be your own. If you've worked with others on this assignment, include the names of the group members in a README file in the turnin directory.
Lab: TAs will be available in Sewall 305 on Wed 9 Oct during the usual class hour to provide advice.
Objectives: Enhance the cvector package from the class examples to include file i/o, matrices, and matrix-vector multiplication. Provide files containing the necessary function definitions, and program files (containing appropriate "main" functions) to write, read and display vectors, matrices, and matrix-vector products. Build the project with make.
Specifically,
for example. Use the stdio file functions (fprintf, fscanf) to implement functions for reading and writing VECTOR data in this form, with these signatures:
int vec_fprint(VECTOR, char *);
int vec_fscan(VECTOR *, char *);
vec_fprint should write the contents of its VECTOR to the file named in the "char *" argument: i.e.
vec_fprint(v, "foo.vec");
should write v to foo.vec in the format described above. Conversely,
vec_fscan(&w, "foo.vec");
should read the contents of the file foo.vec into the VECTOR w.
Use the suffix ".vec" on all of your VECTOR files - that way, it's obvious which they are, without looking into them.
VERY IMPORTANT: "trap" all errors you can anticipate. In the event of an error condition occurring in one of your functions, print an informative error message and return from the function immediately - for vec_fprint and vec_fscan, the return value should be non-zero in the event of an error, zero for normal return. specifically, trap these errors:
float * vdata = ... (allocate nrows*ncols floats)
float ** data = ... (allocate nrows float *'s)
... data[i] = &(vdata[i*ncols]) ...
A question: you will need to allocate the float * vdata, in order to guarantee (this is worth it!) that the matrix data occupies a single contiguous block of memory. Will you need to keep vdata as one of the data members of the MATRIX struct?
Write a set of functions precisely analogous to the functions in cvector.c, stored in a file cmatrix.c. For the file storage, use a similar format to the VECTOR storage mode: nrows on first line, ncols on the second line, then the vector data, row by row, starting with the first row, one float per line (so your file will have 2 + nrows*ncols lines). Be very careful to trap all errors that you can anticipate.
Finally, add to cmatrix.c a definition of matrix multiplication, implemented in a function with signature
int matvec(MATRIX a, VECTOR x, VECTOR b);
Calling this function should store the product of a matrix (first arg) and vector (second arg) in another vector (third arg). Trap all errors - especially, check that the dimensions are compatible. Note that the guts of this function are already available in ex16_multid_array.c.
testvec.x 10
vecreader.x test.vec
testmat.x 11 21
matmult.x a.mat x.vec b.vec
Turnin: Create a project directory named hw_6. Upload it to your repository DIRECTLY UNDER THE REPOSITORY ROOT DIRECTORY, i.e. it should appear in the directory listing as
CAAM420_[yournetid]/hw_6
In hw_6, include the following:
Grading:
matmult.x test.mat test.vec outp.vec
produces the correct matrix-vector product of length 8, recorded in outp.vec.
Condition: This assignment is NOT pledged. You may work with other students, and consult the TAs and Instructor for advice. HOWEVER, all text, including code, in your turnin directory must be your own. If you've worked with others on this assignment, include the names of the group members in a README file in the turnin directory.
Objective: An exercise in debugging: use various debugging techniques to fix Prof. Warburton's REALLY bad code
Details:
really_bad_code.c exhibits a wide variety of bugs. Some are fatal (i.e. cause the resulting program to crash), some are not. The non-fatal bugs are in some cases harder to catch: they correspond to a failure of intention, that is, the program "works" but does not do what the programmer (obviously) intended it to do.
Tools: you may use
Turnin: Create a project directory named hw_7. Upload it to your repository DIRECTLY UNDER THE REPOSITORY ROOT DIRECTORY, i.e. it should appear in the directory listing as
CAAM420_[yournetid]/hw_7
In hw_7, include the following:
Grading:
Condition: This assignment is pledged. You must carry out the work yourself, without assistance from other students. You may consult the instructor and TAs who may give you general advice or information about C/C++ programming, Unix, Make, etc. but may not answer specific questions about the assignment. You may use the course website and other text and web resources. You must cite all resources used - title, author(s), publisher, date for books, URL for web sites. Your README text file turned in with the rest of the assignment should contain the standard Rice pledge.
Objective: Create classes in C++ expressing the vector and matrix functions you developed in project 2 as class methods. Add the capability to read/write vector data to/from files. Secondary objectives: learn to manage a typical project directory structure using a tree of Makefiles.
Details:
VecPPDense(const char * filename) {...}
In the body of the constructor function, you will open the file with name filename (there is no intent to change the contents of filename, so pass a const char * rather than a char *), read the length from the first line into the len data member, allocate the double array, and read the doubles (if you use scanf, remember that you need to use the "l" prefix, to get full length, for example %le) into the array. Trap all likely errors, eg. not having enough lines in the file.
Note the big advantage to putting the read-from-file initialization in a constructor: since you will construct the vector precisely tailored to the contents of the file, there is no need to check eg. that the len data member is equal to the int on the first line of the file!
Add a save method, with signature
void save(const char * filename) const {...}
whose function is analogous to vec_fprint from VECTOR - writes the vector data out to the file filename in the by-now familiar form.
Note that neither of these methods (construct-from-file, save-to-file) appears in the base class VecPPBase as it exists in the course src directory - these will be your innovations.
Also note that you will keep the constructor already present in VecPPDense, with the int argument = vector length. This function will construct vector workspace in some of the examples to come, whereas the constructor that reads from a file will construct vectors based on archival vector data.
In addition, provide a virtual method named apply with the signature
virtual void apply(VecPPBase const & x, VecPPBase & y) const {...}
Use the element access methods of VecPPBase and MatPPBase to implement this method, which has the same function as matmult in your Project 2. It is virtual (so could be replaced or overridden in a subclass) but implemented in the base class - subclasses can (but don't need to) use the base class implementation, as is the case with axpy in VecPPBase. Your implementation should use the access functions to define the loops to multiply the input vector x by the matrix represented by the MatPPBase object on which you call apply, and store the result in the output vector y.
As for VecPPDense, implement a constructor that reads the dimensions and data of the matrix from a file, as your mat_fscan function did in Project 2. Also write a save method - you can figure out its signature - with the same function as mat_fprint.
Be careful about trapping all the errors you can anticipate - not being able to open the file, not having the right number of lines, not being able to translate the file data into doubles, etc. etc.
Important Note: The class examples VecPPBase and VecPPDense are written entirely in header files (xxx.hh). This choice is fairly common in C++ programming, probably because one of two important modes of abstraction (generic programming, implemented by class templates) demands it. The function definisions in these classes, and yours, could be moved to definition files (xxx.cc), and there are advantages to doing so when it's possible. However I advise you to follow my example for the time being and write all of your code in header files, which you #include in your main program files.
Turnin: Submit the code you have written in this project in the form of a typical Unix package, after the pattern of cvectorpkg in the course src directory. Call the package hw_8, and place it just below your main repository directory (i.e. CAAM420_xxx/hw_8). In the directory, include directories named include (header files) and main (main program files). You will not need a lib directory for this example (if you keep all of your code in header files, as I advise). Use Makefiles lightly modified from the makefiles in cvectorpkg to organize your directory.
The header files VecPPBase.hh, VecPPDense.hh, MatPPBase.hh, and MatPPDense.hh should reside in include, the main program file matmult.cc (and any other test code) should reside in main. You will need makefiles at the top level and in main.
Grading:
Condition: This assignment is NOT pledged. You may work with other students, and consult the TAs and Instructor for advice. HOWEVER, all text, including code, in your turnin directory must be your own. If you've worked with others on this assignment, include the names of the group members in a README file in the turnin directory.
Objectives: 1. Explore recursive data structure and class templates by creating a doubly linked list class. 2. Use the doubly linked list as a container for command line arguments, implement associative array behaviour (access by keyword).
Details: This project has two parts.
In the first part, you will modify the linked list class template "slist < T >" from the lecture (src directory) to be create a doubly linked list class template "dlist < T >", based on a double link "dlink < T >". What this means: each dlink will refer to the previous link, as well as to the next one - slinks only referred to "next". Your class will include all of the methods of "slist" in "dlist", along with
void operator--() const;
void prepend(T const &);
Applying operator-- will make the "finger" point at the previous link in "dlist", just as operator++ in "slist" makes it point at the next one. The function "prepend" is supposed to add a dlink to the front of the list, just as "append" added a slink to the back of the "slist" list.
Just as for "slist", your doubly linked list "dlist" will be a class template - a doubly linked list of "anything".
The second part of this assignment uses the doubly linked list data structure to implement an associative array - like an array, but with strings instead of integers as indices. This is a standard and familiar data structure - any sort of directory, eg. a telephone directory, works this way. You will use your associative array specifically to store command line arguments of the form "key=value", and will provide access to the values by key.
Specifically, define a class (can be a struct, i.e. class with public data members) StringPair of pairs of C++ strings. The names of the two data members in the struct should be "key" and "value".
Then define a class ParList, with the following properties:
HINT: It's not obvious how to build a default constructor with a dlist object as private data, because a dlist has to be initialized with some object of its template type (a string pair, in this case). Can be done - you could choose some kind of standard starting pair, and ignore it in all subsequent operations. However that's icky. A much easier way to proceed: instead of a dlist < StringPair > member, give ParList a dlist < StringPair > * data member, initialize it to NULL on construction of the ParList. Then in the addFirst and addLast methods, check to see if dlist is NULL, and construct it if necessary via operator new. Then use as usual. This is effectively post-construction initialization. If you go this route, you will need to be careful in the definitions of operator++, write(), etc. that you handle correctly the case when your dlist data member has not been allocated - but you will know, because the value of the dlist * will be NULL!!
bool addFirst(const char *);
which (i) picks apart the character array, assumed to have the form "key=value", into the two subarrays on either side of the "=" signe, stores these as strings "key" and "value", then (ii) prepends the string pair (key,value) to the front of the dlist data member and returns true, or (iii) returns false if it can't accomplish this goal (for example because the char * arg does not have the form "key=value")
bool addLast(const char *);
similar to addFirst, which appends a StringPair to the back of the dlist [Note: you may want to write a function that converts a "key=value" string to the StringPair ("key","value"), and use it in each of the add... methods - to avoid having to write the same code twice!]
void write(ostream & str) const;
which writes out the keys and values stored in the dlist in a nice readable form.
Finally, you will need to define several standalone function (not class members) of the form
bool findFirst(ParList const & par, string key, T & val);
bool findLast(ParList const & par, string key, T & val);
which assign to the variable of type T a value obtained by looking up the first, resp. last, occurrence of a pair (key, something) in the ParList par, then converting (something) to type T. So for example if a ParList par contains StringPairs {...,(foo,1),...,(foo,2),...}, then
string key="foo";
int v1=0;
int v2=0;
findFirst(par,key,v1);
findLast(par,key,v2);
will return v1=1, v2=2.
Define these functions for the cases
NOTE: these functions are not (should not be) implemented as templates - just as overloaded functions of the same name. That is,
bool findFirst(ParList const & par, string key, int & val);
bool findFirst(ParList const & par, string key, float & val);
...
This works because C++ identifies functions not just by their name but by their signature - function name and number and type of argument. Thus the C++ compiler views the two lines above as declaring different functions, which can be provided different implementations. When the functions are called, the compiler resolves which code to insert by the name, and if the names are the same by the argument types.
NOTE: Overloading functions of the same name this way is a C++ feature - C does not allow you to declare functions of the same name but different arguments in the same program (try it, see what happens!) You can fake it in C using the variable argument list mechanism (such as is used to allow printf to accept any number of arguments of any type), but that's fairly complicated and error prone.
Because you will have a different function for each type, you can implement the functions returning numerical types (int, float, double) by using sscanf - look up the value (string) associated to the key argument in the ParList, use the string method c_str() to extract the C string (const char *) from the value (C++) string, and pass that as the first arg of sscanf, with the second being an appropriate conversion string and the third being a pointer to the variable being updated.
Turnin: Submit the code you have written in this project in the form of a typical Unix package, after the pattern of cvectorpkg in the course src directory. Call the package hw_9, and place it just below your main repository directory (i.e. CAAM420_xxx/hw_9). In the directory, include directories named include (header files), lib (source or implementation files) and main (main program files). Use Makefiles lightly modified from the makefiles in cvectorpkg to organize your directory.
The include directory should contain a header files named "dlist.hh" "parlist.hh", that is, your implementation of dlist - since dlist is a class template, it must be included in every source file that uses it - and declarations for ParList. You can also include all of the implementations for ParList in the header file, if you like (simpler than breaking them out in a separate source file).
Write a single source (implementation) file, called "parfun.cc", for the findFirst and findLast functions and include these in lib; create a library (archive file) named libpar.a, following the pattern of the cvectorpkg, to hold the object file parfun.o.
The main directory may be empty, or contain your test files.
Create makefiles at the top level and in lib and main, as in cvectorpkg, so that typing "make" in the top level builds all components of the project.
Grading:
Project will be graded by using your code with our "main"s:
#include "cppstd.hh"
#include "dlist.hh"
int main() {
    dlist < int > lint;
    dlist < float > lfloat;
    dlist < string > lstring;
    /* ... a bunch of instructions that exercise the dlist
    methods, per above */
}
We will check that the list behaves as expected by periodically printing its contents.
#include "cppstd.hh" #include "parlist.hh"
void partest(ParList const & par) {
    /* code using findFirst and findLast to extract values
    by key from the ParList argument, testing int, float,
    and string versions, also nonexistent keys and cases where
    the same key appears twice (so that findFirst and findLast
    will return different values)
    */
}
int main(int argc, char ** argv) {
    ParList par;
    for (int i=1;i < argc;i++) {
        if (par.addLast(argv[i]))
            cout << "add " << argv[i] << "\n";
        else
            cout <<"failed to add " << argv[i] << "\n";
    }
    // check that command line args read correctly
    partest.write(cout);
    // add some more key=value pairs using addFirst and
addLast, check again
    // then run test function, produce more output
    partest(par);
}
A typical command line for this test might look something like
./a.out fruit=apple quantity=10 weight=12.4 fruitcake
which would result in a ParList with three entries:
key=fruit value=apple
key=quantity value=10
key=weight value=12.4
and one failure to parse a command line arg (fruitcake). The partest function could be built to extract the three values using string, int, and float versions of findFirst, respectively. It will also test for correct behaviour when a key is not found, etc.
Point distribution:
Condition: This assignment is NOT pledged. You may work with other students, and consult the TAs and Instructor for advice. HOWEVER, all text, including code, in your turnin directory must be your own. If you've worked with others on this assignment, include the names of the group members in a README file in the turnin directory.
Objectives: 1. More experience in use of class templates and exceptions via creation of matrix class template. 2. Coupling C with C++: use CLAPACK to solve linear systems, use template specialization to select float vs. double data representation.
Details:
www.cplusplus.com/reference
It's also possible to solve this problem with C techniques (scanf, printf), but harder, as somehow you must determine the type and then choose format conversion strings based on that info.
We will test only float and double cases, so if you do something that works in these cases that's fine. We will not test any other template parameter cases.
void solve(VecTDense < T > const & b, VecTDense < T > & x) const;
This will solve the linear system Ax=b, where the matrix object on which you call the method stores A. Note that we might as well not bother adding this method to the base class, as you will explicitly use the CLAPACK functions which require access to arrays of values. That is, this method is an additional attribute of the derived class MatTDense, unlike "apply" which is a virtual method implemented in the base class MatTBase (and which could be overridden in the derived class, though such an override is not a required part of this assignment).
See the example lapacktest.c in the course example directory for the usage of CLAPACK to solve linear systems.
The "solve" method will need to be implemented with template specialization, because only double and float cases make sense. There are two ways to go: (1) specialize the entire class, or (2) delegate the CLAPACK interface to an external function, much as was done in the course example vectlapack.hh. I recommend the second method. Note that the general template case MUST throw an exception, as we have no implementation of the solve that works for general types.
Turnin: Submit the code you have written in this project in the form of a typical Unix package, after the pattern of cvectorpkg in the course src directory. Call the package hw_10, and place it just below your main repository directory (i.e. CAAM420_xxx/hw_10). In the directory, include directories named include (header files) and main (main program files). You will not need a lib directory for this example (if you keep all of your code in header files, which is more or less necessary as templates cannot be compiled). You may also leave off the main directory in this case, or use it as the location for your test codes (in which case your job will be easier if you use a makefile).
The header files vectbase.hh, vectdense.hh, mattbase.hh, and mattdense.hh should reside in include.
Grading: We will supply the main program, incorporating your header files, and solve several linear systems, printing out matrices and vectors and testing for accurate solution of a problem with invertible matrix, and for reasonable exception handling when the "solve" method encounters a singular matrix.
Additional note 20 Nov 2013: We will supply a test directory with makefile very similar to src/cppvectorpkg/main/Makefile. The test program, double case, will closely resemble the following code, (a similar program will test the float case):
#include "mattdense.hh"
int main(int argv, char ** argv) {
    try {
        MatTDense< double > m("matrix.txt");
        VecTDense< double > b("rhsvec.txt");
        cout<<"\nmatrix:\n";
        m.write(cout);
        cout<<"\nright-hand side vector\n";
        b.write(cout);
        VecTDense< double > x(m.getNCols());
        m.solve(b,x);
        cout<<"\nsolution:\n";
        x.write(cout);
        exit(0);
    }
    catch (CAAM420Exception & e) {
        e.write(cerr);
        exit(1);
    }
}
Important: note that your matrix class needs a getNCols() function that returns the number of columns. If I were writing it, I'd also implement a getNRows() function that returns the number of rows, but the number of columns is all you need here.
Word to the wise: it might be a good idea to make sure that you can implement this or something very similar and get it to work properly!
Condition: This assignment is pledged. You must carry out the work yourself, without assistance from other students. You may consult the instructor and TAs who may give you general advice or information about C/C++ programming, Unix, Make, etc. but may not answer specific questions about the assignment. You may use the course website and other text and web resources. You must cite all resources used - title, author(s), publisher, date for books, URL for web sites. Your README text file turned in with the rest of the assignment should contain the standard Rice pledge.
Remark: It may be (or maybe not) that Brooks' law will make you feel better about a pledged project. Look it up.
Objectives: 1. Synthesis of a complete application using classes, templates, exceptions, and other C++ techniques, also coupling to an external library, to solve a prototype scientific programming problem. 2. Present results in a report, including graphics, using LaTeX.
References on Least Squares: The CAAM 335 notes, available online, are excellent in general and in particular have a very nice chapter (6) on least squares. Wikipedia (google "least squares") is not bad, and has an excellent historical review. Note that we are dealing only with linear least squares, so called, and are using what they call Tikhonov regularization.
Details:
minimize (Ax-b)^T (Ax-b).
instead of the linear system Ax=b. Use the LAPACK subroutines dgels (double) and sgels (float). Read the documentation (at the top of the files in CLAPACK-3.2.1/SRC, or you can find it online) carefully to understand how to use these functions. You can also consult my sample code src/ls.c. An interesting feature, which the *gesv functions do not have: you can specify whether the matrix or its transpose is to be used in formulating the problem. Surprise consequence: you do not have to transpose the stored matrix from row-major (C style) to column-major (Fortran style, used by LAPACK) to use these functions.
Another surprise consequence: now your solve(...) method will work for any shape of matrix, i.e. any positive nrows, ncols. The meaning of the solution is different in different cases, however, as explained in the documentation. One special case: if A is square and invertible, the least squares solution is the same as the linear system solution, except for possible loss of precision in the last few digits.
void apply(VecTBase < T > const & x, VecTBase < T > y, bool transp=false);
If transp=false (the default value), the apply method should multiply x by the matrix and store the result in y, as before. If trasp=true, it should multiply x by the transpose of the matrix. Note that this is very easy to implement: instead of (sum over j) a_ij x_j, the ith component of the output should be (sum over j) a_ji x_j. Of course the "sanity" test for vector lengths changes in an appropriate way in the transp=true case.
This method has an obvious role in manipulating least squares problems - you need the transp=true case to compute the gradient of the least squares function.
Construct solutions for five values of the regularization parameter lam = 10^p, with integer p ranging from -2 to 2. For each choice of lam, use matplotlib and the reader.py module to plot the solution and save a pdf of the plot (see below for instructions). Also record the mean-square residual, i.e. (Ax-b)^T(Ax-b) for each choice of lam. [If you read the documentation carefully, you will find that use of the LAPACK least squares solver has already computed Ax-b for you - you do not need to compute it again, just calculate the sum of squares!]
Ordinarily, a report of this type would also include a literature review section and a final conclusion section, however these do not seem appropriate to this assignment.
Plotting with MatPlotLib:
ipython --pylab
import reader
d = reader.readvec('proj7.vec')
plot(d)
will display the data vector d, assuming that it has been loaded from a file using readvec.
Both ipython and matplotlib have excellent online manuals - I recommend them.
Turnin:as usual
Grading: