Revised May 23, 2014
CS 371: Introduction to Computational Mathematics
Watch a video introduction to the course on YouTube.
General description
This course introduces computational mathematics through an in-depth study of the properties of numerical algorithms.
Logistics
Audience
- CS major students and students pursuing a CS minor
- Students interested in both mathematics and computer science and interested in the computational aspects that one would encounter when solving various mathematical or scientific problems
Normally available
- Winter and Spring
Related courses
- Predecessors: (One of CS 116, 134, 136, 138, 145 taken fall 2010 or earlier, CS 146), MATH 235 or 245, 237, or 247; Not open to General Mathematics students
- Successors: CS 473, 475, 476
- Anti-requisites: CS 335, 337, 370, ECE 204
- Conflicts: AMATH 242/341, CM 271
CS 371 may be substituted for CS 370 in any degree plan or for prerequisite purposes
For official details, see the UW calendar.
Software/hardware used
- MATLAB
Typical reference(s)
- Numerical Analysis, 9th ed., R. Burden and J. Faires, Brooks Cole
- Course notes
Required preparation
At the start of the course, students should be able to
- Program in a high-procedural programming language and use control instructions, such as loops and conditional statements, basic datatypes, and simple data structures, such as arrays
- Use limits and derivatives, Taylor series, curves, max/min of multivariate functions, partial derivatives, other basic concepts encountered in calculus, and multi-dimensional integration
- Use matrix operations, inverse, products, etc., Gaussian elimination, eigenvalues, and eigenvectors
Learning objectives
- Explain the principles of floating point number systems and the concepts of chopping, rounding, machine precision, and error of floating point arithmetic
- Analyze stability and conditioning of numerical problems
- Solve nonlinear equations using iterative methods and analyze convergence of various methods
- Use MATLAB built-in functions and graphing capabilities of 1D and 2D data
- Implement efficient code using vectorization
- Use the principles of polynomial interpolation to derive and apply splines
- Use numerical methods to integrate one dimensional functions and analyze the efficiency of these methods
- Give examples of the concept of data representation using different basis functions, Fourier basis, and the FFT algorithm
- Use alternate representations in applications, such as tomographic reconstruction and filtering
- Solve linear equations in a floating point environment taking into consideration error propagation and measures of conditioning
- Explain the computational and mathematical issues involved in a large scale linear algebra problem (e.g., sparse matrix solving)
Typical syllabus
Floating point number systems (3 hours)
- Floating point numbers, propagation of round off, stability of recursions
Polynomial interpolation (4 hours)
- Interpolation: Lagrange and cubic spline
Nonlinear equations (4 hours)
- Fixed point, Newton iteration Analysis of convergence, rate of convergence
Numerical linear algebra (11 hours)
- LU decomposition, pivoting, condition number, sparse matrices, iterative methods, analysis of convergence of iterative methods, power method for eigenvectors, Google Page Rank, analysis of convergence of the power method, sparse matrices and graphs
Discrete Fourier analysis (11 hours)
- DFT pair, sampling theorem, aliasing, FFT algorithm, slice theorem, Radon Transformation, filtered backprojection for CT image reconstruction
Numerical integration (3 hours)
- Midpoint, trapezoidal, Simpson's rule, error analysis, Gaussian quadrature, Monte Carlo