COS 323 - Computing for the Physical and Social Sciences

Fall 2012

Exam 2 Study Guide

Thursday, Dec. 13

The exam will be held in class on the 13th. If you cannot make it, please contact Prof. Rusinkiewicz to make other arrangements.

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

Topics covered:

For each of trapezoidal rule, Simpson's rule, midpoint rule:

• Understand formulas for one segment and multiple segments
• Know local and global accuracy as a function of segment size h
• Explain the difference between open and closed methods
• Understand change of variables to accommodate limits at infinity

Heath review questions 8.1-8.3, 8.7-8.8, 8.15a, 8.17a, 8.27, 8.31

More complex numerical integration:

• Understand progressive quadrature
• Understand Richardson extrapolation

Heath review questions 8.24, 8.44

Monte Carlo integration:

• Explain what is meant by "curse of dimensionality"
• Explain approach of plain Monte Carlo integration
• Know how quickly variance / error is reduced with number of samples
• Understand stratified sampling and when it reduces variance
• Understand importance sampling and when it reduces variance

Heath review questions 8.32-8.34

Pseudorandom number generators:

• Define "pseudorandom number generator" and explain its advantages and disadvantages relative to true random numbers
• Know inversion and rejection methods for obtaining numbers distributed according to a specified distribution, given only uniform random numbers

Heath review questions 13.5, 13.9, 13.10

ODE solvers:

• Know how to transform arbitrary-order ODEs into systems of first-order ODEs
• Know formulas and convergence orders for explicit Euler and 4th-order RK
• Understand the concept of "stability" for ODE solvers
• Be able to explain bifurcation diagrams and chaos
• Be able to explain the shooting method for BVPs

Heath review questions 9.1-9.10, 9.14-9.16, 9.19, 9.22, 9.25, 10.1-10.3, 10.5

PDE solvers:

• Know formulas and orders of accuracy for foward-, backward-, and centered-difference approximations to the first derivative, and centered-difference approximation to the second derivative
• Understand the difference between ODEs and PDEs
• Be able to classify second-order PDEs as hyperbolic, parabolic, or elliptic
• Understand how to use discretization and finite-difference formulas to convert PDEs into systems of equations
• Understand how stability places a limit on how PDEs must be discretized, and the motivation for multigrid methods

Heath review questions 11.7-11.11

Simulation:

• Explain applicability and benefits/drawbacks of time-driven vs event-driven
• Understand role of event queue and event loop in event-driven simulations
• Understand how a Poisson process leads to exponential next-event distributions, and how to use the inversion method to transform uniform random numbers into exponentially distributed ones

Statistics:

• Understand population vs sample variance and mean

Signal processing:

• Understand continuous and discrete convolution
• Know how to use a Gaussian filter for blurring and a derivative-of-Gaussian filter for derivative estimation
• Understand sampling and aliasing
• Know formulas and running times for naive convolution vs using the convolution theorem and the FFT

Fourier analysis:

• Understand motivation for Fourier series (continuous periodic functions)
• Understand formula for the Discrete Fourier Transform
• Understand the Cooley-Tukey FFT
• Be able to recognize applications of convolution and the FFT

Heath review questions 12.1-12.3, 12.8, 12.11-12.12