CS 205A
Mathematical Methods for Computer Vision, Robotics, and Graphics (Fall 2008)

Course Announcements

DateContents

Summary

This course will focus on the continuous mathematics used in computer science (and EE) with a particular emphasis on the issues associated with designing, implementing and/or using numerical algorithms to solve equations. An underlying theme concerns the approximation issues associated with using floating-point numbers (as opposed to integers) in numerical algorithms.

Staff

Please refer all questions about course material and practices to the CAs before contacting Professor Fedkiw. If you have a question for the CAs, please make sure that it isn't answered on this webpage before contacting them. Also, please do not show up outside of scheduled office hours without first making an appointment. When emailing the CAs, make sure to include "CS205" somewhere in the subject of your message.

Meeting Times

Required Texts

Useful Texts

Please note that you may be able to take the course without owning the textbook but you are still required to be able to access a copy if needed. It is also an excellent resource (it was written by a Stanford graduate) and thus highly recommended.

Class Notes

Notes
Class

Discussion Session Notes

ClassDescription

Tentative Schedule

Topic Estimated Length
Sources and measure of numerical errors.
Accuracy and stability of numerical calculations
1 class
Linear Systems. Existence and uniqueness of a solution.
Gaussian elimination and LU factorization. Pivoting.
1 1/2 classes
Matrix norms and condition number 1/2 class
Cholesky factorization 1/2 class
Overconstrained systems. Normal Equations 1/2 class
QR factorization. Gram-Schmidt orthonormalization.
Householder transform
1 class
Eigenvalue problems. Characteristic Polynomial. Similarity transforms. Jordan forms. Power Method 1 1/2 classes
Singular Value Decomposition 1/2 classes
Nonlinear equations. Fixed point iteration. Newton, secant and bisection methods. Convergence rate. Systems of nonlinear equations. 1 1/2 classes
Unconstrained optimization. Golden section search. Newton iteration. Steepest descent method. 1 class
Conjugate Gradients Method 2 1/2 classes
Preconditioning 1/2 class
Constrained optimization. Lagrange multipliers 1/2 class
Function interpolation. Polynomial interpolants. Lagrange and Newton interpolation. Splines 1 class
Numerical quadrature. Newton-Cotes and Gaussian quadrature. 1/2 class
Initial value ODE problems. Stability and accuracy. 1/2 class
Forward and Backward Euler, Trapezoidal Rule. Runge-Kutta, TVD and multistep methods. 1 class
Newmark integrators. Staggered position/velocity grids. 1 class
Boundary value PDE problems. Discretization and solution of the Laplace Equation. The Heat Equation. CFL condition and stability. 1 class

Assignments

There will be a problem set assigned each week which will be posted on Thursday at 11:59 PM. The homework is due the following Thursday by 11:59 PM, and solutions will be posted promptly at that time. Homework is considered late if it is not in the box at the time the solutions are posted to the webpage, and late homework will receive no credit, with absolutely no exceptions.

Homework will be graded in coarse, half-point increments between 0 and 2 points. A sample midterm will be assigned in lieu of normal problems the week before each midterm and graded coarsely out of 3 points.

You may collaborate on homework assignments provided each student writes up his or her own solutions and clearly lists the names of all the students in the group.

Homework

Submission: Homework must be submitted physically in the bin outside Gates 210. If it is after hours and you cannot get onto the second floor of gates you can use your Student ID to get into the basement. There is a dropoff bin inside the Pup cluster. Please only use the bin in the pup cluster if it is after hours. You can also turn in homework the Thursday they are due in class.

No, we do not have a stapler that you can use. Don't even ask.

Homework is available for pickup in Gates 377 in the filing cabinet.

Examinations

There will be two in-class midterm examinations on October 21st (Class 9) and December 4th (Last Class). Additionally there will be an optional cumulative final on December 8th from 12:15-3:15pm. If you choose not to take the final, your final exam grade will be determined by averaging your two midterm scores. All exams are closed book and closed notes. The final exam will be held in Skilling 193 (the usual classroom). The part of the exam corresponding to the first midterm will run from 12:15-1:30pm, there will be a 15 minute break, and then the part corresponding to the second midterm will run from 1:45-3:00pm.

SVD: You are not required to know algorithms for finding the SVD of an arbitrarily complex matrix, but should be able to find the SVD for simple matrices such as those on the practice midterm. Keep in mind that the singular values of A are the square-roots of the eigenvalues of A^T A or A A^T. More generally, the columns of U and V are the eigenvectors of A A^T and A^T A, respectively.

Grading

SectionProportion
Homework20%
Midterm Exam 120%
Midterm Exam 220%
Final Exam40%