Exam 1 Study Guide/Practice Aid

Rules and General Format

  • No notes, books, slides, electronic devices, crib sheets, or other aids are allowed.

  • No cheating.

  • Read every problem carefully.

  • There are 9 problems on the exam: 8 multiple-choice or short-answer ones (worth one point each), and one coding question at the end (worth two points).

    As a result, there are 10 points theoretically achievable on the exam. A score of 9 points will amount to a grade of 100. 100 is the maximum attainable grade. This means that you may, for example, miss one of the multiple-choice questions without an impact on your grade.

  • The first four questions are ones we think of as 'easy', then three 'medium', one 'somewhat harder', and then finally the code question.

  • The exam is 50 minutes long.

  • Pace yourself. Assuming an even pace, you have about 5 minutes for each of the 8 multiple-choice/short-answer questions, and about 10 minutes for the code question.

  • Make sure to put in an answer on all problems, even if you are guessing some of them. We won't deduct points for wrong answers, so guessing can only work in your favor!

  • For each question, provide the best and most precise answer.

    For example, if in a multiple choice question, option (A) implies option (B), and the stronger option (A) is true, you must choose (A).

    Or, if you are asked to provide an upper bound of something, provide the smallest valid upper bound.

  • For questions that ask for a number, you may use the answer box like a (Python-based) calculator. That is, you may enter 2*5 as equivalent to 10. Your answer will be evaluated in double-precision floating point.

  • If you encounter a technical issue during the exam, please make sure that the proctor is aware and can confirm your claims, ideally in writing. Without that, we have no way of verifying your story and will likely be unable to accommodate you.

  • If you encounter an issue with one of the questions, answer according to your best guess and leave a comment in the "Evidence" box on the last page of the exam with your concern. Make sure to explain the reasoning behind the answer you give. The purpose of this is for you to document that you knew the material, and consequently to make it easier for us to accommodate you if there turns out to be an issue.

    Beyond that, just keep working, and we will sort out any issues later.

  • On multiple-choice and short answer questions, you have one attempt.

  • On the code question, you are allowed as many attempts as you like (within time limits of course) without penalty.

  • Note that unlike for quizzes and in-class activities, you will not receive feedback on the correctness of your work during or immediately after the exam (except on the coding questions).

  • You will have access to the following pieces of documentation:

    • Python documentation
    • Numpy documentation
    • Scipy documentation
    • The book "Dive into Python 3"

  • You will have access to a Jupyterlab environment similar to https://relate.cs.illinois.edu/lab; the only difference is that it is not prepopulated with our course demos.

    It may be a good strategy to open this in a separate window (using the right-click menu, perhaps) and put it side-by-side with the exam. A separate tab may also work.

Content

The exam covers content from lectures 1 through 4. Roughly in terms of subsections, that is

  • Absolute and relative error
  • Vector norms
  • Equivalence of vector norms
  • Norms and errors
  • Forward and backward error
  • Condition number
  • Stability and accuracy
  • Floating point: Intro
  • Floating point: subnormals
  • Floating point: rounding
  • Linear systems: setup
  • Matrix norms
  • Matrix condition number
  • Residuals in linear systems
  • Linear systems: matrix perturbation
  • Preconditioning

Some questions to ask yourself

Basics

  • For a given problem, can I tell whether it's well-posed?
  • Can I identify rounding and truncation error?
  • Can I figure absolute and relative error?
  • Can I compute 1, 2, $\infty$ norms?
  • Can I identify whether a given function satisfies the norm criteria?
  • Can I interpret a unit ball?
  • Can I determine norm equivalence constants for given vector norms?
  • Given an exact calculation (input and output) and an approximate output $\hat y$, can I figure backward error? Also in the vectorial case? Also if multiple inputs $\hat x$ map to $\hat y$?
  • Can I use condition numbers to bound output perturbations? (both absolute and relative)
  • Do I know the definition of a condition number?
  • Can I tell when I've only found a lower bound for a condition number (vs. the actual thing)?
  • Can I use/rederive the derivative-based lower-bound for the conditioning of function evaluation?
  • Do I know how backward error and conditioning combine to help characterize stability?
  • What is the difference between stability and conditioning?

Floating point

  • Can I convert a given number to floating point?
  • Can I determine an upper bound on rounding error given the magnitude of the result?
  • What are trade-offs of floating point vs. fixed point?
  • What is the significand? exponent? of a sign bit?
  • What is normalization? what is a subnormal number? how is zero represented? What is gradual underflow?
  • Can I find a correctly rounded floating point result, under round-to-nearest? round-to-zero? round-to-$\pm\infty$? Can I correctly apply tie breaking ('round-to-even') in round-to-nearest?
  • What is machine epsilon? What is UFL? How do they differ?
  • What is catastrophic cancellation? Given two numbers, can I predict its effect in quantitative terms? (How many significant digits will remain?)

Linear Systems

  • What is an induced matrix norm?
  • Can I figure 1, 2, $\infty$ norms of diagonal matrices?
  • Can I figure 1, $\infty$ norms of any matrix?
  • Can I apply submultiplicativity?
  • Given a matrix, can I figure the matrix condition number? Can I reconstruct the proof of the upper bound?

  • Can I use the matrix condition number to find conditioning of

    • Linear system solving
    • Matrix-vector multiplication

  • How do residual, error, and the condition number relate to one another?

  • Can I bound the solution perturbation when the matrix in a linear solve when the matrix is approximate?
  • Can I distinguish and apply left and right preconditioning?