COS 323 - Computing for the Physical and Social Sciences

Fall 2012

Exam 1 Study Guide

Thursday, Oct. 25

The exam will be held in class on the 25th. If you absolutely cannot make it, a make-up exam will be held on the evening of Oct. 24 - please contact Prof. Rusinkiewicz to arrange to take the make-up exam.

No books, notes, or electronic devices may be used during the exam.

Topics covered:

Number representation, accuracy, precision

• Understand floating-point representation
• Understand relative vs. absolute accuracy

Heath review questions for Ch. 1

For each of bisection, secant, false position, Newton-Raphson:

• When can you (attempt to) use it?
• When is it guaranteed to converge?
• How quickly does error decrease?
• Be able to trace through 1 or 2 iterations by hand (in 1D)

Heath review questions 5.1-5.6, 5.10-5.16, 5.23-5.29, 5.36-5.37

For each of Golden Section Search, Newton, Steepest Descent, Conjugate Gradient, Nelder-Mead Simplex, Simulated Annealing:

• When can you (attempt to) use it?
• When is it guaranteed to converge?
• Which methods are preferred under which circumstances?
• Be able to trace through 1 or 2 iterations of GSS and Newton by hand (in 1D)

Heath review questions 6.1-6.10, 6.14, 6.20-6.22

Describe the main idea behind Dantzig's Simplex Method - when is it used and what are the basic steps it takes?

For each of Gaussian Elimination, LU, Cholesky, forward/backsubstitution, and tridiagonal solvers:

• What is the running time? (Big-O notation)
• When can you use it and when will it work?
• Which methods are preferred under which circumstances?

Heath review questions for Ch. 2

Describe partial and full pivoting, and why they are necessary

Sparse matrix representation (lecture 6)

• Be able to explain the compressed representation
• Be able to work through a matrix/vector multiply by hand
• Explain how to use conjugate gradients to solve sparse linear systems

Least squares

• Why is least-squares fitting used? Why might it be a bad idea to use it?
• Understand (and be able to derive) normal equations
• Describe benefits and drawbacks of Cholesky vs QR vs SVD for linear least squares

Heath review questions 3.1-3.6, 3.9-3.15, 3.40-3.46

Gauss-Newton and Levenberg-Marquardt:

• When can/should they be used?
• Describe why Levenberg-Marquardt might be more stable than Gauss-Newton

Heath review questions 6.36-6.38

Robust regression:

• Explain why outliers are a problem for least squares
• Describe M-Estimation, Iteratively Reweighted Least Squares, RANSAC

SVD:

• Understand dimensions and roles of U, W ($\Sigma$ in the book), and V in SVD
• Explain how to detect underconstrained least-squares problems with SVD
• Explain how to use SVD for dimensionality reduction