CAAM 420: HW Assignments

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.

  1. Assigned 26 Aug, due 28 Aug.

  2. Assigned 28 Aug, due 30 Aug. Use the emacs editor to write a text file explaining your background in computing and what you hope to learn from the course. If inspection of the syllabus suggests that you already have some knowledge of the topics to be covered, please say so. If topics you'd like to see are missing, please say that too.

    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:

    1. first line: your name
    2. second line: your email address
    3. blank
    4. fourth line etc: text per instructions, one page max (with reasonable line width!!!

  3. Assigned 30 Aug, due 4 Sep. Format hw1.txt in LaTeX. Add at the bottom a single math display expressing a correct statement of some version of the Fundamental Theorem of Calculus (no need to include detailed statement of hypotheses, just a formula). MODIFIED 4 Sep: Submit your homework in a subdirectory hw_2 of your repository - after submission, "svn list https://svn.rice.edu/r/CAAM420_(YourNetID)" should return "... hw_2 ...", i.e. hw_2 should show up in the top level.

    The hw_2 directory should contain both the source, as hw1.tex, and the pdflatex output, as hw1.pdf.

  4. Assigned 4 Sep, due 6 Sep (that's a joke - nothing to turn in!). Read K&R sections 1.1 and 1.2. Find a history of the C language on the net, read it. The first two Google hits are good - an article by Ritchie, the "R" in "K&R", and the Wikipedia piece.

  5. Assigned 6 Sep, due 11 Sep (NOTE CHANGE!): read K&R section 1.2 very carefully for the use of the while control structure and variable assignment (I'll also discuss these in class). Then write a program to use the rand random number utility to produce repeatedly, and display (only) the first "random" number it generates that is more than 1/2 of the maximum value RAND_MAX. You can consult the notes for week 2 and the example program src/ex2.c for more information.

    submit a directory named hw_3 under your main repo directory, with your solution of the problem as its contents (hw_3/hw3.c).

  6. Assigned 11 Sep, due 16 Sep: Read Notes through section 11 - this assignment uses material through section 8.

    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.

  7. Assigned 13 Sept, due 16 Sept. An exercise which does not need to be turned in:

    The IEEE standard decrees that floats should consist of 32 bits, as follows:

    What is the largest decimal exponent of an IEEE float, in standard scientific notation: (plus or minus)(number between 1 and 10)(10 to exponent)? How many non-garbage decimal digits does the mantissa (the factor between 1 and 10) have?

    Having worked this out, write a program which prints

  8. Project 1. Assigned 20 Sep, [due 27 Sep] REVISION: DUE 30 Sep.

    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:

    1. A good first step is to get hold of the bits stored in the machine. To do that, the simplest trick is (1) declare a pointer to an unsigned int and assign it to the address of your float - you will need to cast the address of the float to an unsigned int address (i.e. pointer variable) to make the compiler treat the former as the latter, i.e.

      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.

    2. However, when you print *u, it will look like a decimal, so that doesn't help. You need to convert the int to its binary rep. So write a function to do that, and use it to get an array of ints, all either 0 or 1. You know what the length of the array should be (32), so you can declare it in the standard array fashion in your main program, and pass it to the function.
    3. Now you have to figure out which is the sign, which 23 bits are the mantissa, etc. I suggest an experimental approach: choose some floats for which you know the answers, and see what bit arrays the last step produces. Alternatively, you can dig into the literature on IEEE float representation.
    4. NOTE ADDED 24 Sep: a couple of other peculiar things about IEEE 754 floating point standard:
      1. The Shifted Exponent: The exponent is coded as a binary number in the range 1-254. The actual value of the exponent is the coded value - 127: thus the actual exponents range from -126 to 127. The reason for coding the exponent this way, rather than with a sign bit, is simple: with a sign bit (which I will write first, though it could be last) and 7 exponent bits, 0 could be represented as either 00000000 or 10000000, since -0=0. Which means that the coding represents one less exponent value than you might have thought. However with the exponent + 127 stored instead of the exponent, there is no duplicate coding: 10000000 represents 128-127=1, and 00000001 represents -126. The largest representable exponent is then 11111110 which represents 254-127=127.
      2. The Hidden Bit:: if a number is not too small (less than 2^(-126)) and not too large, then it can always be represented as +/-1.xxx...x times 2^p with p between -126 and 127. The leading digit (1....) is always there for these normalized floating point numbers, so there is no point in storing it. This is the hidden bit. For example, 1/16 is (binary) 1.000... times 2^-4, and stored in the machine as 000.....0000 (23 zeros) with exponent 127-4=123 = 01111011. 3/16 would be stored as 100...0000 (22 zeros) with exponent stored as 01111100. And so on.

    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.

  9. Project 2. Assigned 4 Oct, due 11 Oct.

    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,

    1. Add functions to cvector/cvector.c to read and write VECTOR data to/from files. For a VECTOR v, the file should record the integer length (v.len), and the data (v.data) on the subsequent lines, one per line. For example, a vector of length three would be recorded in a file looking like this:
      3
      1.0000000e+00
      2.0000000e+00
      3.0000000e+00

      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:

      • failure to open a file with the appropriate permission ("r" or "w")
      • failure to read the file length
      • failure to read a data value
      Note that fscanf may return either 0 or EOF if it fails to read a value.

    2. Define another struct (typdef struct mat {...} MATRIX) to hold the data of a matrix. Follow the pattern of VECTOR: the struct should contain (a) nrows = the number of rows and ncols = the number of columns, and (b) a float **, say data, so that data[i][j] contains the ith row, jth column entry in the matrix. ex16_multid_array.c uses this idea, and except for using malloc instead of stack-based arrays you will proceed in the same way: first allocate nrows*ncols floats, then an nrows float *'s which you initialize to point to the beginnings of each row. Something like this would work:


      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.

    3. Write main functions (each in a separate file) to produce these commands:
      1. testvec: reads vector length n from the command line, writes the vector with data 0,1,2...n-1 to the file test.vec
      2. vecreader: reads file name from command line, reads a vector from the file of that name, displays it.
      3. testmat: reads nrows and ncols from the command line, writes the matrix with data[i][j]=i+j to the file test.mat
      4. matmult: reads files names for matrix and two vectors from command line, multiplies the matrix and the first vector and stores the result in the second vector (file name).