Revised March 17, 2014

CS 370: Numerical Computation

Watch a video introduction to the course on YouTube.

General description

This course introduces students to the basic algorithms, software environments, and applications of scientific computing. Simple but realistic examples are used to motivate the study of numerical methods.

Logistics

Audience

• CS major students and students pursuing a CS minor
• Students interested in a career in computational support of engineering or scientific applications, such as CAD/CAM, graphics, or finance

Normally available

• Fall, Winter, and Spring

Related courses

• Predecessors: (One of MATH 118, 119, 128, 138, 148), (One of MATH 114, 115, 106/125, 136, 146), (One of CS 234, 241, 246); Not open to General Mathematics students
• Successors: CS 475, 476
• Anti-requisites: AMATH 242/341/CM 271/CS 371, CS 335, 337, ECE 204, 304

For official details, see the UW calendar.

Software/hardware used

• MATLAB

Typical reference(s)

• Numerical Computing with MATLAB, Cleve Moler, SIAM, 2004
• 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
• Perform basic mathematical computations and have knowledge of
  • limits and derivatives, Taylor series, curves, and other basic concepts encountered in calculus
  • matrix operations, inverse, products, Gaussian elimination
  • complex arithmetic and trigonometric functions

Learning objectives

At the end of the course, students should be able to

• 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 simple numerical problems
• Use MATLAB built-in functions and graphing capabilities of 1D and 2D data
• Implement efficient code using vectorization
• Compute polynomial and spline interpolants and apply splines to curve drawing in two and three dimensions
• Use numerical algorithms to solve ordinary differential equations and understand and apply methods to analyze the stability and efficiency of these methods
• Design simple procedures using FFT based algorithms for applications, such as signal and image processing and data compression
• Solve linear equations in a floating point environment taking into consideration error propagation and measures of conditioning
• Give examples of the issues involved in a large scale linear algebra computation (e.g., Google Page Rank)

Typical syllabus

Floating point numbers (3 hours)

• Floating point numbers, propagation of round off, stability of recursions

Interpolation (6 hours)

• Interpolation: Vandermonde matrix, Lagrange interpolation, cubic splines, B splines
• Example application: scalable fonts

Ordinary differential equations (9 hours)

• Forward, backward, modified Euler, local truncation error, stability, global error
• Example application: pursuit problems, SIR disease propagation model

Discrete Fourier analysis (9 hours)

• Fourier series, FFT algorithm (butterfly)
• Example application: JPEG, image and signal processing, MP-3

Numerical linear algebra (9 hours)

• LU decomposition, pivoting, condition number, QR decomposition
• Example application: Google Page Rank