Study guide for Examlet 1

Here is a non-exhaustive list of questions you should be able to answer as you prepare for the examlet.

Introduction

• What does $f(n)=O(g(n))$ mean?
• If $T(n)$ represents timing for a problem size $n$ and you know $T(n)=O(n^2)$ as well as the timing for $n=10$, what will the timing for $n=20$ be?
• What is the (asymptotic, i.e. big-O) cost of matrix-matrix multiplication?
• What types of quantities can be estimated using Big-O notation?

Linear Algebra Recap

• What is a vector space? What conditions do they satisify?
• What is a linear function? What conditions do they satisify?
• What does 'linearly independent' mean?
• What is a basis? What conditions does it satisify?
• Given a basis, how can a given vector be represented in coordinates?
• How do matrices represent linear functions?
• What does it mean for a matrix to be invertible?
• How does matrix-matrix (and matrix-vector) multiplication work, numerically?
• What is a permutation matrix?

Python

Note: You will have access to a set of documentation for Python and its numerical libraries.

• How do you express the following in Python: integer, real number, string, list, tuple?
• How do you assign a value to a variable in Python?
• How do you write a for loop in Python?
• How do you write an if conditional statement in Python?
• How do you write an while loop in Python?
• What happens when a Python value (e.g. a list) is modified in-place?
• How do you avoid in-place modification?
• How do you create a numpy array? from given data? filled with zeros? with equally spaced values?
• What is the shape of a numpy array?
• How do you extract the $n$th row/column of a numpy array?
• How many entries are there in a numpy array of shape (10, 20)?
• For a numpy array a of shape (10, 20, 30), what is the shape of a[:,3:5]?

Taylor Approximation

• Given a function $f$, find its Taylor expansion about an expansion center $c$ of a given order.
• Provide an estimate (in Big-O notation) of the truncation error of a Taylor expansion.
• Use the truncation error estimate to estimate the error $E(h)$ for one distance $h_2$ given the error for another distance $h_1$.
• Have a heuristic understanding of when Taylor expansions will not converge, as demonstrated in class.