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.