Check on P573 prerequisites

I had to look up one of the summation formulae below, using an arcane, little-known wizard's tool, whose name rhymes with "google". I assume that anyone born after 1960 knows how to use a search engine, and will use one whenever it helps.

For programming, you must have the ability to code in C or C++ or Fortran. That means at least one of those, not all of them. It is not sufficient to use Java or a scripting language, although knowing such languages will help you in life in general. We need to use languages where we can directly manipulate memory, implement in-place algorithms, and link to high-performance libraries. For any of the languages, use modern standards. Fortran 77 may remind you of the olden time of yore, but it's been out of date for longer than most graduate students have been alive. Since all compilers available at IU support C99, C11, F2008, etc., use those - even if your undergrad professors still hark back to the glorious days of 1971, back when they had hair on top of their head, and not growing out of their ears, and when they were still able to get a date on a Saturday night ¹.

Mathematics

• what is the sum of k, for k = 1 to k = n?
• what is the sum of k², for k = 1 to k = n? [Why ask this: ²]
• What is the limit as n → ∞ of (2*n³ + 3*n² + n)/(6*n*(n+1)) ?
• For what real values of x is the function log(x) well-defined and takes on real values?
• On a desktop machine with G Gbytes of memory, I need to allocate 3 two-dimensional arrays of 8-byte double precision numbers. Each array is of size n x n. What's the largest value of n that will allow them to (maybe just barely) fit into that much memory? Here I'm assuming 1 Gbyte = 1024³ = 1073741824 bytes, and nothing else needs to fit into memory at the same time⁴.

Basic linear algebra

• Given (real-valued) matrices A and B, what restrictions on their sizes allows computing the product C = A*B?
• Denote the transpose of a matrix A as A^T. Let x and y be n x 1 column vectors. Which of the following products exist, and what are the dimensions of the resultant product?
  1. x*y
  2. x^T*y
  3. x*y^T
  4. x^T*y^T
• What is an "upper triangular matrix"?
• What is an "orthogonal matrix"?
• Suppose the n x 1 column vectors q₁, q₂, …, q_k are mutually orthogonal and each has norm 1. Set Q to be the n x k matrix whose i-th column is the vector q_i. What restriction does this impose on the possible values of k? Is Q an orthgonal matrix?
• A vector v is an eigenvector of a matrix A if A*v = λ*v, for some (possibly complex-valued) scalar λ. There's one other stipulation for v to be an eigenvector; what is it?

Coding

• How to open a file, read from or write to it, and close the file
• How to allocate memory in a program
• How to write to a specified interface in one of C, C++, or Fortran
• How to define and use arrays

Coding self-test

1. open a file named "sizes", read in a single integer n, close the file
2. allocate double precision 1-dimensional arrays x and y, each of length n
3. Set x to be all 1.0s: x = [1.0, 1.0, 1.0, 1.0, ..., -1.0]
4. Set y to be the increasing positive integers: y = [1.0, 2.0, ..., n]
5. compute the dotproduct alpha of x and y: alpha = x(1)*y(1) + x(2)*y(2) + … + x(n)*y(n)
6. compute the dotproduct beta of y and itself: beta = y(1)*y(1) + y(2)*y(2) + … + y(n)*y(n)
7. write a message to standard output indicating which (if any) of the two numbers alpha and beta are correct

This should take at most one hour in C or C++, and less in Fortran (if you use Fortran's array statements, which you should). This assumes that you don't bother checking to make sure opening the input file actually succeeded, or that the memory allocation did not fail, or put in lots of comments, explanations, and progress and debugging messages. Although you'll want (actually, be required) to add those features in any other code, the intent here is to make sure you can do the necessary basic manipulations required ³.

The dotproducts are defined above using matrix/vector notation, which has indices that start at 1 and end at n. For C you will need to shift the indices of the arrays to start at 0 and end at n-1, since C requires all arrays to be indexed starting at 0. Fortran allows the indices to start with any integer value: 0, 1, 12, -15, whatever, but it's probably easiest to take the default and start at 1. It took me 20 minutes to write and test a Fortran version, most of that using a text editor just to type the file.

As for writing a message indicating if the numbers are correct, note that the correct values for alpha and beta are given by the summation formulas above.

Footnotes:

^{1. You don't need to be too obsessive about the latest coding methodologies, but do use language standards no more than 20 years old. For example, I am not adamant about using uint32_t or uint64_t (or even int32_t or int64_t ) for loop variables in preference to int , but whatever type you use, be aware of its range and limits. In Fortran the same thing applies to integer(selected_int_kind(9)) (or integer(selected_int_kind(18))) versus integer. ↵}

^{2. Counting the number of floating point operations in a nest of loops requires evaluating summation formulae. ↵}

^{3. An actual assignment requires documenting the code (and not just putting in dumb filler like "int n; // n is an integer""), checking the input to make sure the file "sizes" exists and can be opened and read, verifying that the file actually contains an integer, verifying that the integer is positive and that it will fit into the default size for integers in the code, checking that memory was successfully allocated, using a tolerance in the correctness tests (for cases where the arrays don't have all integer values like the x and y above do), and freeing up all allocated memory and closing any open files before stopping. ↵}

^{4. In reality, you'd want to use at most 75% of the available memory on a non-shared machine. After all, the OS has to have some room to play around in. ↵}