CAS CS 132
Geometric Algorithms

Table of Contents

CS132 is an introduction to linear algebra with an emphasis on applications in computer science. It's based heavily on (and depends on the material for) the version of the course taught by Mark Crovella.

Links

Schedule (Compact)

Date Topic Notes  
09-03 Solving Linear Systems Read course manual, A1 out  
09-07 No Lab Labor Day  
09-08 Echelon Forms    
09-10 Gaussian Elimination A2 out, A1 due  
09-14 Lab 1: Introduction to NumPy    
09-15 Vector Equations    
09-16   Last day to add or change to audit  
09-17 Matrix-Vector Equations (Workshop) A3 out, A2 due  
09-21 Quiz 1    
09-22 Linear Independence    
09-24 Linear Transformations A4 out, A3 due  
09-28 Lab 2: Computer-Solving Equations (I)    
09-29 Matrix Transformations    
10-01 Matrix Algebra (Workshop) A5 out, A4 due  
10-05 Quiz 2    
10-06 Matrix Inverses    
10-07   Last day to drop w/o a "W"  
10-08 LU Factorization A5 due  
10-12 No Lab Indigenous People's Day  
10-13 Midterm Review Substitute Monday  
10-15 Midterm 1 A6 out  
10-19 Lab 3: Computer-Solving Equations (II)    
10-20 Markov Chains    
10-22 Computer Graphics A7 out, A6 due  
10-26 Quiz 3    
10-27 Subspaces    
10-29 Dimension and Rank (Workshop) A8 out, A7 due  
11-02 Lab 4: Graphics    
11-03 Eigenvalues and Eigenvectors    
11-05 The Characteristic Equation A8 due  
11-06   Last day to drop w/ "W" or designate P/F  
11-09 Midterm Review    
11-10 Midterm 2    
11-12 Diagonalization A9 out  
11-16 Quiz 4    
11-17 Orthogonality    
11-19 Orthogonal Projection (Workshop) A10 out, A9 due  
11-23 Lab 5: Matrix Decompositions    
11-24 Least Squares    
11-26 No Lecture Thanksgiving Recess  
11-30 Quiz 5    
12-01 Linear Models    
12-03 Quadratic Forms (Workshop) A11 out, A10 due  
12-07 Final Exam Review    
12-08 Singular Value Decomposition    
12-10 Applications of SVD A11 due  
12-15 Final Exam 12:00PM-2:00PM  

Calendar

Course Staff

Do not contact course staff directly except in extenuating circumstances. If you have course-related questions/concerns, post on Piazza.

Schedule (Full)

09-03 THU (Lecture)

  • Week: 1
  • Title: Solving Linear Systems
  • Reading:
  • Topics:
    • systems of linear equations
    • solution sets and consistency
    • augmented and coefficient matrices
    • forward elimination and back substitution
    • row operations and row equivalence
  • Learning/Teaching Objectives:
    • Recall the process of solving simultaneous linear equations. You should be able to solve a linear system in 2-4 variables by hand
    • Begin the formal study of linear systems, both geometrically (as collections of hyperplanes) and algebraically (as matrices that can be operated on)
  • Notes:
    • Assignment 1 released

09-08 TUE (Lecture)

  • Week: 2
  • Title: Echelon Forms
  • Reading:
  • Topics:
    • echelon forms and RREFs
    • pivot columns and positions
    • free and basic variables
    • general form solutions
  • Learning/Teaching Objectives:
    • Understand how many solutions a linear system can have, and why
    • Understand how the solutions of a linear system "look"
    • See how to represent solutions of a linear system
    • Learn how to "read off" solutions from an RREF

09-10 THU (Lecture)

  • Week: 2
  • Title: Gaussian Elimination
  • Reading:
  • Topics:
    • forward elimination and back substitution (revisited)
    • floating point numbers and IEEE-754
  • Learning/Teaching Objectives:
    • Make forward elimination and backwards substitution algorithmic
    • Get a sense of the errors that can occur when working with floating-point numbers
  • Notes:
    • Assignment 2 released
    • Assignment 1 due

09-14 MON (Lab 1)

  • Week: 3
  • Title: Introduction to NumPy

09-15 TUE (Lecture)

  • Week: 3
  • Title: Vector Equations
  • Reading:
  • Topics:
    • vectors
    • vector operations and their algebraic properties
    • linear combinations and vector equations
    • spans
  • Learning/Teaching Objectives:
    • Connect the algebraic notion of linear systems to the geometric notation of vectors
    • See how the geometric properties of vectors reduce to solving systems of linear equations

09-17 THU (Workshop)

  • Week: 3
  • Title: Matrix-Vector Equations
  • Reading:
  • Topics:
    • matrix-vector multiplication
    • row-column rule
    • the matrix equation Ax = b
    • inner-products
  • Learning/Teaching Objectives:
    • Define matrix-vector multiplication and use it to represent linear systems
    • Introduce the algebra of matrices and vectors
  • Notes:
    • Assignment 3 released
    • Assignment 2 due

09-21 MON (Quiz 1)

  • Week: 4
  • Topics:

09-22 TUE (Lecture)

  • Week: 4
  • Title: Linear Independence
  • Reading:
  • Topics:
    • homogeneous linear systems
    • linear independence and dependence
    • increasing span criterion
  • Learning/Teaching Objectives:
    • Introduce notion of linear independence as a way to understand if the span of a set of vectors is "as large as possible"
    • Examine the relationship between linear independence and systems of linear equations (in particular, look at what the shape of a matrix says about the linear dependence of its columns)

09-24 THU (Lecture)

  • Week: 4
  • Title: Linear Transformations
  • Reading:
  • Topics:
    • general transformations
    • domains, codomains, images, ranges
    • matrix transformation
    • linearity
  • Learning/Teaching Objectives:
    • Introduce linearity as a way of describing "well-behaved" functions on vectors
    • See examples and non-examples of linear transformations (in particular, look at matrix-vector multiplication as the canonical example of a linear transformation)
  • Notes:
    • Assignment 4 released
    • Assignment 3 due

09-28 MON (Lab 2)

  • Week: 5
  • Title: Computer-Solving Equations (I)
  • Topics:

09-29 TUE (Lecture)

10-01 THU (Workshop)

  • Week: 5
  • Title: Matrix Algebra
  • Reading:
  • Topics:
    • one-to-one and onto transformations
    • matrix multiplication
    • row-column rule
    • algebraic properties of matrix operations
  • Learning/Teaching Objectives:
    • Define matrix multiplication and look at how it interacts with other matrix operations like addition and scalar multiplication
    • Connect matrix multiplication with the composition of linear transformations
  • Notes:
    • Assignment 5 released
    • Assignment 4 due

10-05 MON (Quiz 2)

  • Week: 6
  • Topics:

10-06 TUE (Lecture)

  • Week: 6
  • Title: Matrix Inverses
  • Reading:
  • Topics:
    • inverse of a matrix
    • invertible matrix theorem
  • Learning/Teaching Objectives:
    • Show how to "divide" by a matrix as a way of solving systems of linear equations (when possible)
    • Examine how matrix inversion interacts with other matrix operations
    • See how matrix inversion can be understood in terms of linear transformations

10-08 THU (Lecture)

  • Week: 6
  • Title: LU Factorization
  • Reading:
  • Topics:
    • elementary matrices
    • matrix factorizations
  • Learning/Teaching Objectives:
    • Discuss matrix factorization in general as a way to "get more information" about a matrix
    • Look at the LU factorization as a faster way of solving multiple matrix equations (over the same matrix)
  • Notes:
    • Assignment 5 due

10-13 TUE (Midterm Review)

  • Week: 7

10-15 THU (Midterm 1)

  • Week: 7
  • Notes:
    • Assignment 6 released

10-19 MON (Lab 3)

  • Week: 8
  • Title: Computer-Solving Equations (II)

10-20 TUE (Lecture)

  • Week: 8
  • Title: Markov Chains
  • Reading:
  • Topics:
    • linear dynamical systems and linear difference equations
    • stochastic matrices and Markov chains
    • steady-state vectors
  • Learning/Teaching Objectives:
    • Introduce Markov chains as an application of the topics we've covered
    • Use Markov chains to reason about the long-term behavior of linear dynamical systems

10-22 THU (Lecture)

  • Week: 8
  • Title: Computer Graphics
  • Reading:
  • Topics:
    • wireframe objects
    • homogeneous coordinates
    • perspective projections
  • Learning/Teaching Objectives:
    • Discuss the relationship between linear algebra and computer graphics, in particular the use of linear transformations and perspective transformations for rendering images of 3D objects on a 2D screen
    • Have a bit of fun with linear algebra
  • Notes:
    • Assignment 7 released

10-26 MON (Quiz 3)

  • Week: 9
  • Topics:

10-27 TUE (Lecture)

  • Week: 9
  • Title: Subspaces
  • Reading:
  • Topics:
    • subspaces
    • column space and null space
    • bases
  • Learning/Teaching Objectives:
    • Introduce subspaces and bases as a way to think more generally about space
    • Extend our intuitions about planes in \(\mathbb R^3\) to subspaces in \(\mathbb R^n\)
    • Connect subspaces to matrices and solving systems of linear equations

10-29 THU (Workshop)

  • Week: 9
  • Title: Dimension and Rank
  • Reading:
  • Topics:
    • coordinate systems and change of bases
    • dimension and rank
    • rank-nullity theorem
  • Learning/Teaching Objectives:
    • Introduce dimension as a way of quantifying how "large" a span is
    • Learn techniques for finding bases for the column space and the null space of a matrix
    • Relate the dimension of the column space and the null space of a matrix
  • Notes:
    • Assignment 8 released
    • Assignment 7 due

11-02 MON (Lab 4)

  • Week: 10
  • Title: Graphics

11-03 TUE (Lecture)

  • Week: 10
  • Title: Eigenvalues and Eigenvectors
  • Reading:
  • Topics:
    • eigenvalues and eigenvectors
    • eigenspaces and eigenbases
    • linear dynamical systems and closed form solutions
  • Learning/Teaching Objectives:
    • Introduce eigenvectors as as way of thinking about vectors which are "just stretched" by a matrix
    • Learn how to verify eigenvectors and eigenvalues of a matrix
    • Use eigenvectors to reason about linear dynamical systems

11-05 THU (Lecture)

  • Week: 10
  • Title: The Characteristic Equation
  • Reading:
  • Topics:
    • determinants
    • the characteristic polynomial
    • triangular matrices
    • algebraic and geometric multiplicity
  • Learning/Teaching Objectives:
    • Look briefly at the notion of the determinant of a matrix
    • Learn how to find eigenvalues (not just verify them)
    • Connect eigenvalues to polynomials
  • Notes:
    • Assignment 8 due

11-09 MON (Midterm Review)

  • Week: 11
  • Title:

11-10 TUE (Midterm 2)

  • Week: 11
  • Topics:

11-12 THU (Lecture)

  • Week: 11
  • Title: Diagonalization
  • Reading:
  • Topics:
    • similar matrices
    • diagonalizable matrices
    • change of bases and eigenbases
  • Learning/Teaching Objectives:
    • Examine another matrix factorization related to basis changes
    • Walk through how to diagonalize a matrix
  • Notes:
    • Assignment 9 released

11-16 MON (Quiz 4)

  • Week: 12
  • Topics:

11-17 TUE (Lecture)

11-19 THU (Workshop)

  • Week: 12
  • Title: Orthogonal Projection
  • Reading:
  • Topics:
    • orthogonal projections and orthogonal components
    • orthogonal matrices
  • Learning/Teaching Objectives:
    • Introduce orthogonal projection as a way of finding the "shadow" of a vector in a subspace
    • Connect orthogonality to matrices and linear transformations
  • Notes:
    • Assignment 10 released
    • Assignment 9 due

11-23 MON (Lab 5)

  • Week: 13
  • Title: Matrix Decompositions

11-24 TUE (Lecture)

  • Week: 13
  • Title: Least Squares
  • Reading:
    • Required:
    • Optional:
      • ILA 6.5: The Method of Least Squares
      • LAA 6.5: Least-Squares Problems
      • Samuel Beckett: Waiting for Godot (act II)
  • Topics:
    • approximate solutions to inconsistent linear solutions
    • least-squares error and Euclidean norms
    • least-squares solutions
  • Learning/Teaching Objectives:
    • Introduce the least squares method as a way of giving "approximate" solutions to systems of linear equations
    • Demonstrate the relationship between orthogonal projection and least squares solutions

11-30 MON (Quiz 5)

  • Week: 14
  • Topics:

12-01 TUE (Lecture)

  • Week: 14
  • Title: Linear Models
  • Reading:
  • Topics:
    • best fit hyperplane
    • multiple regression
    • model parameters
    • model fitting
    • design matrices
  • Learning/Teaching Objectives:
    • Look at applications of linear algebra in machine learning
    • In particular, show how to fit models of a particular kind to labeled data

12-03 THU (Workshop)

  • Week: 14
  • Title: Quadratic Forms
  • Reading:
  • Topics:
    • symmetric matrices
    • orthogonal diagonalizability
    • quadratic forms
    • definiteness
    • constrained optimization
  • Learning/Teaching Objectives:
    • Look at the special properties of the eigenvectors and eigenvalues of symmetric matrices
    • Connect this to solving constrained optimization problems over quadratic forms
  • Notes:
    • Assignment 11 released
    • Assignment 10 due

12-07 MON (Final Exam Review)

  • Week: 15
  • Topics:

12-08 TUE (Lecture)

  • Week: 15
  • Title: Singular Value Decomposition
  • Reading:
  • Topics:
    • singular values
    • singular value decomposition
    • pseudo-inverses
  • Learning/Teaching Objectives:
    • Look at SVD as a general decomposition for matrices
    • See an application to least squares solutions via pseudo-inverses

12-10 THU (Lecture)

  • Week: 15
  • Title: Applications of SVD
  • Reading:
  • Topics:
    • matrix norms
    • low-rank approximation
    • image compression
  • Learning/Teaching Objectives:
    • See how the SVD of a matrix can be used to expose the "important parts" of the matrix
  • Notes:
    • Assignment 11 due

12-15 TUE (Final Exam)

  • Topics: