Schedule
Geometric Algorithms
Boston University
Fall 2023

09-05 Lecture 1

Topic: Linear Equations
Material:
- Reading:
  - Required:
    - Linear Algebra, Geometry, and Computation (LAGC): Linear Equations
  - Optional:
    - Linear Algebra and its Applications (LAA) 1.1: Systems of Linear Equations
    - Interactive Linear Algebra (ILL) 1.1: Systems of Linear Equations
- Slides:
  - keynote
  - pdf
- Administrivia:
  - keynote
  - pdf
Reminders:
- read course information and course policies
- install python + libraries
- get on piazza and gradscope
- no office hours this week

09-07 Lecture 2

Topic: Numerics
Material:
- Reading:
  - Required:
    - LAGC: Numerics
  - Optional:
    - Floating-Point Arithemtic: Issues and Limitations
- Slides:
  - keynote
  - pdf
- Code: numerics.py
- IEEE 754 Converter
- Homework 1:
  - pdf (worksheet)
  - tex
  - Starter Code: hw01prog.py
  - Solutions:
    - pdf
    - hw1progsol.py
Reminders:
- homework 1 assigned
- impromptu office hours: Friday (9/8) 1:30-3:30PM in CDS 801
Errata:
- I messed up the formula for calculating the value of an IEEE 75 floating point representation, the slides have the correct now
end of week 1 survey

09-11 Week 2 Discussion

No material

09-12 Lecture 3

Topic: Gaussian Elimination
Material:
- Reading:
  - Required:
    - LAGC: Gaussian Elimination
  - Optional:
    - LAA 1.2: Row Reductions and Echelon Forms
    - ILA 1.2: Row Reductions
- Slides:
  - keynote
  - pdf
Reminders:

09-14 Lecture 4

Topic: Vector Equations
Material:
- Reading:
  - Required:
    - LAGC: Vector Equations
    - Numpy: the absolute basics for beginners
  - Optional:
    - LAA 1.3: Vector Equations
    - ILA 2.1: Vectors
    - ILA 2.2: Vector Equations and Spans
- Slides:
  - keynote
  - pdf
- Code: 04-numpy-demo.py
- Homework 2:
  - pdf (worksheet)
  - tex
  - Starter Code: hw02prog.py
  - Solutions:
    - pdf
    - hw02progsol.py
Reminders:
- the deadline for homework 1 was pushed to Sunday 9/17 at 5PM
- homework 2 is released as usual, and will be due next Thursday as usual
end of week 2 survey

09-18 Week 3 Discussion

Material: discussion notes (pdf)

09-19 Lecture 5

Topic: Matrix-Vector Equations
Material:
- Reading:
  - Required:
    - LAGC: Ax = b
  - Optional:
    - LAA 1.4: The Matrix Equation Ax = b
    - ILA 2.3: Matrix Equations
- Slides:
  - keynote
  - pdf
Reminders:
- homework 2 is due on this Thursday

09-21 Lecture 6

Topic: Linear Independence
Material:
- Reading:
  - Required:
    - LAGC: Linear Independence
  - Optional:
    - LAA 1.7: Linear Independence
    - ILA 2.5: Linear Independence
- Slides:
  - keynote
  - pdf
- Homework 3:
  - pdf (worksheet)
  - tex
  - Starter Code:
    - hw03prog.py
    - gauss.py (v2 2023-09-27 7:10PM)
  - Solutions:
Reminders:
- Homework 2 is due at 11:59PM today

09-25 Week 4 Discussion

Material:
- pdf (worksheet)
- pdf (solution)

09-26 Lecture 7

Topic: Linear Transformations
Material:
- Reading:
  - Required:
    - LAGC: Linear Transformations
  - Optional:
    - LAA 1.8: Introduction to Linear Transformations
    - ILA 3.1: Matrix Transformations
    - ILA 3.3: Linear Transformations
- Slides:
Reminders:
- Homework 3 is due on Thursday
- Midterm Accommodations:
  
  If you require accommodations for the midterm and have not heard from me, please send me an email.

09-28 Lecture 8

Topic: Matrices of Linear Transformations
Material:
- Reading:
  - Required:
    - LAGC: Matrix of a Linear Transformation
  - Optional:
    - LAA 1.9: The Matrix of a Linear Transformation
    - ILA 3.2: One-to-one and Onto Transformations
    - ILA 3.3: Linear Transformations
- Slides:
- Code: 08-2d-matrix-transforms.py
- Homework 4:
  - tex
  - pdf (worksheet)
  - Starter Code: hw04prog.py
  - Solutions:
Reminders:
- Homework 3 is due tonight by 11:59PM today
end of week 4 survey

10-02 Week 5 Discussion

Material:
- pdf (worksheet)
- pdf (solution)

10-03 Lecture 9

Topic: Matrix Algebra
Material:
- Reading:
  - Required:
    - LAGC: Matrix Algebra
  - Optional:
    - LAA 2.1: Matrix Operations
    - ILA 3.4: Matrix Multiplication
- Slides:
Reminders:
- Homework 4 is due this Thursday

10-05 Lecture 10

Topic: Matrix Inverse
Material:
- Reading:
  - Required:
    - LAGC: The Inverse of a Matrix
  - Optional:
    - LAA 2.2: The Inverse of a Matrix
    - LAA 2.3: Characterizations of Invertible Matrices
    - ILA 3.5: Matrix Inverses
    - ILA 3.6: The Invertible Matrix Theorem
- Slides:
- Code: 10-matrix-inverse.py
- Homework 5:
  - tex
  - pdf
  - Starter Code: hw05prog.py
  - Solutions:
Reminders:
- Homework 4 is due tonight at 11:59PM
end of week 5 survey

10-10 Week 6 Discussion

Material:
Reminders:
- Today is a Substitute Monday

10-12 Midterm

Time: During Lecture
Locations:
- A1:
  - CAS B12
  - CGS 129
- B1:
  - CAS B12
  - SHA 110
Reminders:
- See Piazza for which location you will be taking the midterm. You will not recieve credit for the midterm if you do not take it in the correct location.
- For additional information about the midterm, see Piazza.
end of week 6 survey

10-16 Week 7 Discussion

Material:
- pdf (worksheet)
- pdf (solution)

10-17 Lecture 11

Topic: Invertible Matrix Theorem
Material:
- Reading:
  - Required:
    - LAGC: The Inverse of a Matrix
  - Optional:
    - LAA 2.3: Characterizations of Invertible Matrices
    - ILA 3.6: The Invertible Matrix Theorem
  - Advanced:
    - Linear Algebra Done Right (LADR) 1.B: Definition of Vector Space
    - Exercises: 1.B.5, 1.B.6
- Slides:
- Code:
  - 11-matrix-inverse.py
  - 11-tricount.py
Reminders:
- Homework 5 is due on Thursday at 11:59PM

10-19 Lecture 12

Topic: Markov Chains
Material:
- Reading:
  - Required:
    - LAGC: Markov Chains
  - Optional:
    - LAA 4.9: Applications of Markov Chains
- Slides:
  - keynote
  - pdf
- Code:
  - 12-markov-demo-1.py
  - 12-markov-demo-2.py
- Homework 6:
  - tex (graph.png)
  - pdf
  - Starter Code:
    - hw06prog.py
    - sonnets.txt
  - Solutions:
end of week 7 survey

10-23 Week 8 Discussion

Material:
- pdf (worksheet)
- pdf (solution)

10-24 Lecture 13

Topic: Matrix Factorizations
Material:
- Reading:
  - Required:
    - LAGC: Matrix Factorizations
  - Optional:
    - LAA 2.5: Matrix Factorizations
- Slides:
- Code: 13-lu.py
Reminders:
- Homework 6 is due on Thursday at 11:59PM

10-26 Lecture 14

Topic: Computer Graphics
Material:
- Reading:
  - Required:
    - LAGC: Computer Graphics
  - Optional:
    - LAA 2.7: Applications to Computer Graphics
  - Advanced:
    - LADR 1.C: Subspaces
    - Exercises: 1.C.12, 1.C.19, 1.C.23
- Slides:
  - keynote
  - pdf
- Homework 7:
  - tex (demo-screenshot.png)
  - pdf
  - Starter Code: hw07prog.py
  - Additional Code: sparse.py
  - Solution:
Reminders:
- Run the starter code early to check your setup
end of week 8 survey

10-30 Week 9 Discussion

Material:
- pdf (worksheet)
- pdf (solution)

10-31 Lecture 15

Topic: Subspaces
Material:
- Reading:
  - Required:
    - LAGC: Subspaces
  - Optional:
    - LAA 2.8: Subspaces of Rⁿ
    - ILA 2.6: Subspaces
- Slides:
Reminders:
- Homework 7 is due on Thursday by 11:59PM

11-02 Lecture 16

Topic: Dimension and Rank
Material:
- Reading:
  - Required:
    - LAGC: Dimension and Rank
  - Optional:
    - LAA 4.5: The Dimension of a Vector Space
    - LAA 4.6: Rank
    - ILA 2.7: Basis and Dimension
    - ILA 2.9: The Rank Theorem
  - Advanced:
    - LADR 2.A: Span and Linear Independence
    - Exercises: 2.A.9, 2.A.11, 2.A.15
- Slides:
- Homework 8:
  - tex
  - pdf
  - Starter Code: hw08prog.py
  - Solution:
    - pdf
    - hw08progsol.py
Reminders:
- The deadline for homework 7 was extended to Friday at 7PM.
end of week 9 survey

11-06 Week 10 Discussion

Material:
- pdf (worksheet)
- pdf (solution)

11-07 Lecture 17

Topic: Eigenvalues and Eigenvectors
Material:
- Reading:
  - Required:
    - LAGC: Eigenvectors and Eigenvalues
  - Optional:
    - LAA 5.1: Eigenvectors and Eigenvalues
    - ILA 5.1: Eigenvectors and Eigenvalues
- Slides:
Reminders:

11-09 Lecture 18

Topic: The Characteristic Equation
Material:
- Reading:
  - Required:
    - LAGC: The Characteristic Equation
  - Optional:
    - LAA 5.2: The Characteristic Equation
    - ILA 5.2: The Characteristic Polynomial
  - Advanced:
    - LADR 2.B: Bases
    - Exercises: 2.B.6, 2.B.7, 2.B.8
- Slides:
- Homework 9:
  - tex
  - pdf
  - Solution: pdf
end of week 10 survey

11-13 Week 11 Discussion

Material:
- pdf (worksheet)
- pdf (solution)

11-14 Lecture 19

Topic: Diagonalization
Material:
- Reading:
  - Required:
    - LAGD: Diagonalization
  - Optional:
    - LAA 5.3: Diagonalization
    - ILA 5.4: Diagonalization
- Slides:

11-16 Lecture 20

Topic: PageRank
Material:
- Reading:
  - Required:
    - LAGC: PageRank
  - Optional:
    - The anatomy of a large-scale hypertextual Web search engine
  - Advanced:
    - LADR 2.C: Dimension
    - Exercises: 2.C.9, 2.C.13, 2.C.14
- Slides:
  - keynote
  - pdf
- Homework 10:
  - tex
  - deeper-pagerank-fig.jpg
  - pdf
  - Starter Code: hw10prog.py
  - Solution:
end of week 11 survey

11-20 Week 12 Discussion

Material:
- pdf (worksheet)
- pdf (solution)

11-21 Lecture 21

Topic: Orthogonality
Material:
- Reading:
  - Required:
    - LAGC: Analytic Geometry in Rⁿ
  - Optional:
    - LAA 6.1: Inner Product, Length, and Orthogonality
    - ILA 6.1: Dot Products and Orthogonality
- Slides:
Reminders:

11-23 Thanksgiving

No Material

11-27 Week 13 Discussion

Material:
- pdf (worksheet)
- pdf (solution)

11-28 Lecture 22

Topic: Orthogonal Sets and Projections
Material:
- Reading:
  - Required:
    - LAGC: Orthogonal Sets and Projections
  - Optional:
    - LAA 6.2: Orthogonal Sets
    - LAA 6.3: Orthogonal Projections
    - ILA 6.3: Orthogonal Projections
    - ILA 6.4: Orthogonal Sets
  - Advanced:
    - LADR 3.A: The Vector Space of Linear Maps
    - Exercises: 3.A.4, 3.A.12, 3.A.14
- Slides:

11-30 Lecture 23

Topic: Least Squares
Material:
- Reading:
  - Required:
    - LAGC: Least Squares
  - Optional:
    - LAA 6.5: Least Squares Problems
    - ILA 6.5: The Method of Least Squares
  - Advanced:
    - LADR 3.B: Null Spaces and Ranges
    - Exercises: 3.B.12, 3.B.17, 3.B.29
- Slides:
- Homework 11
  - tex
  - pdf
  - Solution:
    - pdf
    - hw11sol.py
Reminders:
- The deadline for homework 10 has been extended to Saturday 12/2 at 7PM
end of week 13 survey

12-04 Week 14 Discussion

Material:
- pdf (worksheet)
- pdf (solution)

12-05 Lecture 24

Topic: Linear Models
Material:
- Readings:
  - Required:
    - LAGC: Linear Models
  - Optional:
    - LAA 1.10: Linear Models in Business, Science, and Engineering
- Slides:

12-07 Lecture 25

Topic: Symmetric Matrices
Material:
- Reading:
  - Required:
    - LAGC: Symmetric Matrices
  - Optional:
    - LAA 7.1: Diagonalization of Symmetric Matrices
  - Advanced:
    - LADR 5.A: Eigenvalues, Eigenvectors, and Invariant Subspaces
    - Exercises: 5.A.10, 5.A.15, 5.A.21
- Slides:
- Homework 12:
  - tex
  - pdf
  - Starter Code: hw12prog.py
  - Solution:
    - hw12progsol.py
    - testsubmission.py
Reminders:
- Homework 12 will be out tomorrow morning and will be shorter than usual
- Please fill out an evaluation for this course (https://www.bu.edu/courseeval)
last weekly survey

12-11 Week 15 Discussion

Material:
- pdf (worksheet)
- pdf (solution)

12-12 Lecture 26

Topic: Singular Value Decomposition
Material:
- Reading:
  - Required:
    - LAGC: Singular Value Decomposition
  - Optional:
    - LAA 7.4: The Singular Value Decomposition
- Slides:
Reminders:
- Homework 12 is due today at 11:59PM

Schedule Geometric Algorithms Boston University Fall 2023

09-05 Lecture 1

09-07 Lecture 2

09-11 Week 2 Discussion

09-12 Lecture 3

09-14 Lecture 4

09-18 Week 3 Discussion

09-19 Lecture 5

09-21 Lecture 6

09-25 Week 4 Discussion

09-26 Lecture 7

09-28 Lecture 8

10-02 Week 5 Discussion

10-03 Lecture 9

10-05 Lecture 10

10-10 Week 6 Discussion

10-12 Midterm

10-16 Week 7 Discussion

10-17 Lecture 11

10-19 Lecture 12

10-23 Week 8 Discussion

10-24 Lecture 13

10-26 Lecture 14

10-30 Week 9 Discussion

10-31 Lecture 15

11-02 Lecture 16

11-06 Week 10 Discussion

11-07 Lecture 17

11-09 Lecture 18

11-13 Week 11 Discussion

11-14 Lecture 19

11-16 Lecture 20

11-20 Week 12 Discussion

11-21 Lecture 21

11-23 Thanksgiving

11-27 Week 13 Discussion

11-28 Lecture 22

11-30 Lecture 23

12-04 Week 14 Discussion

12-05 Lecture 24

12-07 Lecture 25

12-11 Week 15 Discussion

12-12 Lecture 26

Schedule
Geometric Algorithms
Boston University
Fall 2023