CPSC 303 Page, Spring 2024

This page concerns CPSC 303 Section 201.

This page has the most up-to-date information on the course(s) and supersedes any other document.

Materials below may have errors! Errors will be corrected either here or in class. If you are not attending my classes: use these materials at your own risk!

News April 17: A second (and last) final exam practice problem set, with solutions, now appears on the Final Exam Study Guide.
April 16: First final exam practice problem set now has some edits in red, and solutions. A second practice set may appear. See the section below.
Office hours for April 16-19: usual office hours, but Thursday 2-3:30pm office hours in X530. Additional office hours Friday, April 19, 10:30am-12:30pm, in ICCS 304; the are last office hours before the exam.
April 9: Final exam study materials are in preparation; see the section below.
March 28: Typo corrected in Homework 8, Problem 2.
March 27: Midterms returned; see midterm solutions and scaling below.
March 12 and 13: Minor changes and clarifications to some practice midterm problems; here are some brief solutions.
March 11: Some corrections to some practice midterm problems (really changes to make them more like the homework) appear in red.
March 8: Here are some practice midterm problems.

March 7: Typo in code for HW 7, Q3(h) -- the code has the number 2 in a number of places where there should be a 10.

March 5: We will only grade Problems 1-4 on Homework 7, and we might not grade all parts of Problems 2-4. However, the material of Problems 5 and 6 (including their solutions) is examinable on the midterm. Also, typo corrected on Homework 7, Q3(b), in red.

Feb 28: Correction to Homework 6, equation in Problem 5(a), indicated in red.

Feb 23: Our final exam will be on Sunday, Apr 21, 12:00 pm.

Feb 15 (5:32pm): Recent correction to the hint on Homework 5, Problem 5(c).

Feb 13: 5 sign typos corrected on Homework 5, indicated in red: the Energy formulas (Problems 2f and 3) should have a + between the main terms, not a -. Problem 5c has three sign errors in the motivation of the exercise, but not in the actual exercise itself.

Feb 6: Typo corrected on Homework 4, Problem 2(b): the fraction 1/(2N) should be 1/(2N^2).

Feb 5: Chnage in the hint to Homework 4, Problem (5,e,iv). [Note: there is no issue if you solved this problem without the hint.]

Feb 1: Diversity news: February is Black History Month in Canada. For example, currently within Canada you can watch I Am Not Your Negro (based on a manuscript of James Baldwin) free of charge, courtesy of tvo (TV Ontario) Today.

Jan 31: Major revision of draft of CPSC 303: Introduction to ODE's (and Review of Calculus for Numerical Methods); likely more material will be added soon.

Jan 6: Please sign up for gradescope using UBC's Canvas system; the link from Canvas to gradescope should be ready within a few days.

Jan 5: Welcome, and Happy 2024! Make sure you have a way to access MATLAB and the course textbook (see below). If you've used UBC's MATLAB license before, you may have to ugrade to MATLAB_R2023b.
Overview This is an introductory course in numerical approximation and discretization, focusing on differential equations and interpolation (and splines). The material corresponds to parts of Chapters 10-12 and 14-16 of the course textbook by Ascher and Greif (see below for details).
Policy This policy webpage describes the course policy, including the prerequisites and grading scheme.
References The required course textbook is A First Course in Numerical Methods by Uri Ascher and Chen Greif, available online for free to anyone wth a UBC CWL. You may need to follow this link to get to UBC's online version.
Our course will cover some of Chapters 10-16 of the textbook; we remark that the textbook has some very difficult and specialized material that we will omit (see the Syllabus below).
Aside from the textbook, we will use some material--notes and articles--which I will supply:

These articles may be modified during the course:

  • We will likely provide some supplemental references or notes when we begin discussing ODE's. Here is: A revised draft of: CPSC 303: Introduction to ODE's (and Review of Calculus for Numerical Methods), last revised Feb 5, 12:57pm.
  • For a review of separable ODE's, we recommend Section 2.4 of UBC Math's Calculus Textbooks (all 4 calculus textbooks can be found here).
  • CPSC 303: Recurrence Relations and Finite Precision (2020).
  • CPSC 303: Normal and Subnormal Numbers in Double Precision (2020).
  • CPSC 303: What the Condition Number Does and Does Not Tell Us (2020).
  • CPSC 303: Remarks on Divided Differences (2024).
  • CPSC 303: Energy in Cubic Splines, Power Series as Algorithms, and the Initial Value Problem (2020).
  • CPSC 303: Adjacency Matrices, Splines, and the Heat Equation (2024).
  • CPSC 303: Summary of ODE Numerical Methods, Stiffness, and Central Force Problems (and Beyond) (2024).

    • Since the prerequisites for this course require only two terms of calculus, we will spend a class or two on examples of differential equations and what they mean.
    Software MATLAB will be used in class to perform some numerical computations, and will be required for numerical computations on the homework. MATLAB is available free of charge to all active UBC students; check your eligibility to use UBC's MATLAB agreement here; you will probably wind up at UBC's On the Hub website (search for MATLAB).
    (MATLAB syntax will not be examined on the midterm or the final exam; however, you will be responsible for knowing homework and class material illustrated by our MATLAB computations.)
    There are a number of good intros to MATLAB, on the Mathworks Documentation Homepage. For quick help within MATLAB, you can type "doc blah" for help on "blah" (e.g., "doc function" or "doc lists") in the command window there.
    Additional Resources There are many useful resources on Jessica Bosch's CPSC303 page from 2017-18. You can also see my CPSC303 page from 2019-20, which was rudely interrupted (and shortened) by the Covid pandemic after class on Friday, March 13, 2020.
    We remark that previous versions of CPSC 303 will differ in content and emphasis from this year's version. For example, this year's course will probably spend more time on ODE's and PDE's (both giving real-world examples and discussing numerical methods).
    Midterm Exam Here are solutions to the 2024 midterm notes on the midterm scaling (and how it was derived), explained in class on 03_27. If your raw midterm score is x, the scaling is s(x) given by: if x <= 6.5, then s(x) = (50%)x/(6.5), and if x >= 6.5, then s(x) = (100%)(x+10)/33.
    The midterm will be held during class hours on Friday, March 15, 2024, in the usual class room (ESB 1012). You may bring one two-sided 8" x 11.5" sheet of notes, written by hand or computer. You can't use calculators or computers.
    The midterm exam will cover class up to the end class on Wednesday, Feb 28, i.e., up to Lagrange interpolation (note that classes on March 1 and later do review some of this material).
    The midterm will be largely based on the homework, including some subtle points in the solutions. Here are some practice midterm problems; brief solutions will be given to some of these questions; solutions.
    Note that the above practice questions are meant to be representative rather than exhaustive.
    You will be seated either alphabetically by last name or by order of your student ID. Please remain outside the exam room until we invite everyone in.
    Final Exam Our Final Exam is on Sunday, April 21, at noon (12pm), in DMP (Hugh Dempster Pavilion), Room 110.
    You may bring two two-sided 8" x 11.5" sheet of notes, written by hand or computer. You can't use calculators or computers.
    A Final Exam Study Guide, which includes detailed list of skills needed for the final exam are in preperation; material will be added.
    You will be seated either alphabetically by last name or by order of your student ID. Please remain outside the exam room until we invite everyone in. Most likely we will give the exam in two parts, each 60-70 minutes long, with a 10-15 minute break in the middle.
    Syllabus, Readings, and Boards Scans [A&G] refers to the textbook by Ascher and Greif.
    • Roughly 2 weeks: Review of Calculus (mainly Taylor's Theorem) and Intro to Differential Equations. Section 16.1 and part of 16.2 of [A&G], plus parts of earlier chapters (esp. Chapters 1 and 14). I may post some supplemental notes. ODE examples (simple ODE's, exponential and logistic growth, n-body problem, gradient search and minimizing dynamics).
      Board scans: 01_08: course policy, relative versus absolute error, some common norms on R^n, Taylor's theorem (univariate).
      01_10: Order() notation in Taylor's theorem; notation C[a,b], C^k[a,b], C^omega(a,b), etc.; expansions of sin(x), e^x; being ODEs: y'=Ay, y(t_0)y_0.
      01_12: Summary of existence and uniqueness for y'=f(y). Isocline diagrams, y'=y^2, y'=|y|^(1/2).
      01_15: Three-point schemes for f' and relation to linear algebra and Vandermonde matrices. Solution of y'=Ay, y(t_0)=y_0 when y is m-dimensional and A is an m by m matrix. Harmonic oscillator x''=-x, and ODE for y = [ v x ] where v = x' and y' = Ay where A is the matrix [ 0 -1 ; 1 0 ] (using MATLAB notation, i.e., A is a 2 x 2 matrix)
      01_17: Euler's Method for ODE's. Exact solution of y'=Ay compared with Euler's Method, and limit of Euler's method equals the exact solution. Brief intro to MATLAB and part of Homework 2. THIS LECTURE HAS BEEN RECORDED AND IS AVAILABLE ON CANVAS, UNTIL JAN 31.
      01_19: Homework 2 involves some MATLAB. Intro to celestial mechanics: conservation of momentum. Matrix exponential (definition). Similarity of matrices, powers of similar matrices. Compositions of matrices with the same similarity relation (live demo). Inverse of ST (live demo). THIS LECTURE HAS BEEN RECORDED AND IS AVAILABLE ON CANVAS, UNTIL FEB 2.
      01_22: Similar matrices. Polynomials, power series, and functions of diagonal matrices. Diagonalization of [ a b ; b a ]. Polynomial interpolation, Vandermode matrices, and "Linear Algebra without Linear Algebra." THIS LECTURE HAS BEEN RECORDED AND IS AVAILABLE ON CANVAS, UNTIL FEB 5.
      01_24: We discussed some basic MATLAB operations, and saw that 1/0 yields Inf, -1/0 yields -Inf, and Inf - Inf yields NaN (Not A Number). Why creating derivative schemes yields Vandermonde matricies. Polynomials of degree n with n+1 distinct roots (must equal the 0 polynomial), and conclusion of "Linear Algebra without Linear Algebra." Formula for e^(At) when A = [ 0 -1 ; 1 0 ] and A = [ 0 1 ; 1 0] (derivation to be given on Jan 26).
      01_26: ODE topics to be covered toward the end of the course. Time reversal and non-reversibility of systems with, for example, friction (live demo with coffee travel mug). The (explicit) trapezoidal method for ODE's. Matrix norms and measure of size, convergence of series I+A+A^2/2+... to e^A. Evaluation of e^(At) for A = [ 0 1 ; 1 0] without diagonalization.

    • Roughly 1.5 Weeks: Recurrence Relations (and ODE Analog), Normal and Subnormal Numbers (in Finite Precision). Material from [A&G], Chapter 2, CPSC 303: Recurrence Relations and Finite Precision (2020), and CPSC 303: Normal and Subnormal Numbers in Double Precision (2020).
      Board scans: 01_29: Diagnoalizable matrices: definition and function of such matrices. Fibonacci numbers and other three term recurrences: an analog of a 2nd order ODE, 2 x 2 matrices, and special solutions of the form lambda^n.
      01_31: Recurrences versus ODE's: Fibonacci recurrence, the shift operator, general "recipe" to solve constant coefficient finite recurrences. The Fibonacci ODE analog: y''- y'- y=0; general recipe to solve constant coefficient ODE's; recurrences for Euler's method and the ODE limit. Inhomogeneous ODE example. Multiple roots in the ODE and recurrence relation "recipes."
      02_02: Existence and uniqueness in ODE's versus Recurrence Relations. Example: x_{n+2}-5x_{n+1}+6x_n=0: solutions x_n=r^n, r=2,3. Fitting initial conditions and Vandermonde matrices, Writing this equation as z_{n+1}=A z_n where z_n is two-dimensional. Eigenvalues of A: r=2,3, eigenvectors [r 1]. What about repeated roots: x_{n+2}-4x_{n+1}+4x_n=0, x_n=2^n and...what else?
      02_05: The delta operator (= sigma - 1), and why a three-term recurrence is analogous to a 2nd order ODE, Solution to x_{n+2}-4x_{n+1}+4x_n=0, computation of (sigma -2) applied to n 2^n. The limit of (sigma - 2)(sigma - 2 - epsilon)(x_n)=0 as epsilon -> 0. Recurrence x_{n+2}-4x_{n+1}+4x_n gives y_{n+1} = A y_n where A=[4,-4;1,0], and N = 2I-A is nilpotent.
      02_07: MATLAB experiments: (1/2)^1074, (1/2)^1075, 2^1023, 2^1024, x_{n+2}-(3/2)x_{n+1}+(1/2)x_n=0, x_1=1, x_2=1/2. (1/2)^1074 * 2^1074 versus ((1/2)^1074*2^900)*2^174. F_{n+2}=F_{n+1}+F_n, F_1=1, F_2={1-sqrt(5))/2. MATLAB: "format long" versus "format short". Normal and subnormal numbers in double precision.

    • Roughly 2.5 Weeks: Polynomial Interpolation. Material from [A&G], Chapter 10, CPSC 303: What the Condition Number Does and Does Not Tell Us (2020), and CPSC 303: Remarks on Divided Differences (2024).
      Board scans: 02_09: General remarks on polynomial interpolation: one theorem, 3 proofs/algorithms, each has advantages over the other two. Remarks on Homework 5: the central force problem, equations, conservation of energy. Demo of MATLAB program used on Homework 5. Monomial interpolation: Vandermonde matrices (once again...). Linear algebra w/o linear algebra (once again...).
      02_12: Remarks on general linear interpolation (with arbitrary functions). Example of p(x) = c_0+c_1 x^2; a bad case, and a good case. Case of interpolation at (x_0,y_0), (x_1,y_1), and x_0 near x_1. Sense in which the system is bad, but limit x_1 -> x_0 is the tangent line.
      02_14: Review norms. Matrix norm ||A||_p , definition. ||A||_2 (the largest singular value of A) is awkward, even for A being 2 x 2. ||A||_p for p=infinity and p=1 (much easier). ||A||_p versus largest absolute value of an entry of A. Relative error of Ax=b measured by condition number, ||A|| ||A^(-1)||: statement of theorem and example.
      02_16 (Chen Greif, co-author of [A&G], lectured on the blackboard): Condition number of 10^16 makes double precision lose all precision. Vandermonde demo in MATLAB (e.g., A = fliplr( vander(0:0.1:1)) , cond(A,Inf), etc.). Start 10.3, Lagrange interp.
      02_26: Proof of condition number as worst case relative error loss in solving Ax=b, and how to generate a worst case example.
      02_28: Example of when Lagrange interpolation will lose less precision than monomial interpolation (to be further illustrated on Homework 7).
      03_01: Adaptive interpolation and Newton's polynomial.
      03_04: The generalized mean-value theorem. Lagrange interpolation and a formula for the highest order coefficient.
      03_06: Triangular numbers and what happens when some values are missing. Newton divided differences.
      03_08: Remarks on midterm, including: alternate method to compute the energy of central force problem, and all matrix norms and condition numbers will be based on infinity norms. Remarks on f[x0,x1,x2] and inductive formula for divided differences.
      03_11: Divided differences and Lagrange interpolation take order n^2 flops, monomial roughly order n^3 flops. Upper/lower triangular change of basis for polynomials.
      03_13: Hermite Interpolation: example with two points: why the 4 x 4 system is more complicated than the 2 x 2 system (for one point, which gives the tangent line). Using linear algebra w/o linear algebra and divided differences. Some discussion of midterm practice problems.

    • Roughly 1.5 Weeks: Splines, a.k.a., Piecewise Polynomial Interpolation. Sections 11.1-11.3 of [A&G] (splines and related piecewise interpolation). Minimizing (of square of 2nd derivative) property of splines and related remarks from CPSC 303: Energy in Cubic Splines, Power Series as Algorithms, and the Initial Value Problem (2020).
      Board scans: 03_18: Splines: modelling of smooth surfaces with localized design. The calculus of variations and minimizers of the Dirichlet integral and length: piecewise linear functions. Start: minimizers of the square integral of the second derivative and cubic splines.
      03_20: Non-existence of C^1 spline Dirichlet integral minimizers, Sobolev spaces (brief remarks), and existence and uniqueness of C^2 squared second-derivative integrals (i.e., vanishing second derivative at the endpoints). Paramter count in piecing together degree three polynomials.
      03_22: Remark on the calculus of variations, and HW 8. Algebra regarding a_i,b_i,c_i,d_i and f values for natural cubic splines; Linear system for the c_i in terms of divided differences.
      03_25: Review: a_i,b_i,d_i are "local functions" of divided differences and the c_i. The matrix N_(rod,n) and the c_i. The inverse of I-A when ||A||_infty < 1. N_(rod,n)=S_(n,1)+S_(n,-1), S_(n,1) = Shift_(n,1), which is nilpotent. N_(rod,n) is tridiagonal. Consequence for N_(rod,n)^2.
      03_27: Review of the significance of N_(rod,n). Directed graphs (or "digraphs"), undirected graphs (or just "graphs"), and their adjacency matrix. Paths of length n. Interpretation of powers of the adjacency matrix. N_(rod,n) is the adjacency matrix of the path of length n. Implication for powers of N_(rod,n). Explanation of midterm scaling (see above notes on the midterm).
      04_03: More on N_{rod,n} and N_{ring,n} and adjacency matrices. Exact formula for powers of N_{ring,n} using cyclic shift matrices, relationship to powers of N_{rod,n} (and non-cyclic shift matrices).

    • Roughly 1.5 Weeks: Differential Equations. Chapter 16 of [A&G]. (ODE's; if time permits, Heat and Laplace Equations.) CPSC 303: Adjacency Matrices, Splines, and the Heat Equation (2024), and CPSC 303: Summary of ODE Numerical Methods, Stiffness, and Central Force Problems (and Beyond) (2024).
      Board scans: 04_05: The Heat Equation: partial derivatives, discrete approximation, and interpretation. Example of a solution sin(pi x)e^(-pi^2 c t). Its numerical solution effectively takes powers of (1-2 rho)I + rho N_{rod,m-1} . Instability due to finite precision when rho > 1/2, and (|1-2 rho|+2 rho)^(# interations) is roughly 2^{53}.
      04_08: Checking ODE's numerically: Method 1: test on y'=Ay or other ODE's for which we know the exact soltion. Method 2: look for invariants (conserved quantities), time reversability. Heat Equation analog of Method 1: test on sin(pi x)e^(-pi^2 t), yielding powers of 1+2 rho(cos(pi h)-1), i.e., powers of 1 - rho pi^2 h^2 + O(h^4).
      04_10: Stiff ODE's: basic examples, and remedy of backward Euler method.
      04_12: Review of numerical methods for ODE's (Sections 16.2 and 16.3 of [A&G]), order of accuracy of a method, stiff equations with negative. Stiffness for matrices with complex eigenvalues, without complex eigenvalues (and the harmonic oscillator, yet again...).
    Homework Homework will be assigned most weeks, typically due on gradescope at 11:59pm on Thursday. We may grade only some of the problems on the homework. Late homework will not be accepted; however, your three lowest scores will be dropped in the overall homework computation.

    See the policy webpage for homework policy on individual and group homework.

    Homework 1: No individual homework this week. Here is Group Homework 1. Group homework is due Thursday, Jan 18, 11:59pm, on Gradescope. Solutions to Homework 1.

    Homework TeX/LaTeX Snippets: To make it easier for you to write LaTeX, I'll release Some TeX/LaTeX Snippets from my homework. I can't guarantee that this file will compile bug-free on your particular LaTeX system.

    Homework 2: No individual homework this week. Here is Group Homework 2; this homework involves the files: apple.m, apple_bad.m, apple_worse.m, apple_quiet.m, chaotic_sqrt.m (these 5 anchors point to a .txt file, but should be each saved as a .m file to get them to run under MATLAB), exponential_of_a_matrix.txt, start_here.txt. Group homework is due Thursday, Jan 25, 11:59pm, on Gradescope. Solutions to Homework 2.

    Homework 3: No individual homework this week. Here is Group Homework 3. Group homework is due Thursday, Feb 1, 11:59pm, on Gradescope. Solutions to Homework 3.

    Homework 4: No individual homework this week. Here is Group Homework 4 (Problem 5(e) revised Feb 2, 8:10am). Group homework is due Thursday, Feb 8, 11:59pm, on Gradescope. Solutions to Homework 4.

    Homework 5: No individual homework this week. Here is Group Homework 5; you may find the file Euler_Central_Force.m helpful. Group homework is due Thursday, Feb 15, 11:59pm, on Gradescope. Here are some extra practice problems (which will neither be collected nor graded), Practice Homework 5, relating to recent topics. Some brief solutions will be posted. Solutions to Homework 5 and Solutions to Practice Homework 5.

    Homework 6: No individual homework this week. Here is Group Homework 6. Group homework is due Thursday, Feb 29, 11:59pm, on Gradescope. Solutions to Homework 6.

    Homework 7: No individual homework this week. Here is Group Homework 7. Group homework is due Thursday, March 7, 11:59pm, on Gradescope. Solutions to Homework 7. See this March 5 news item about how much of this homework will be graded.

    No homework due on March 14. Instead, study for the midterm: review the homework until now, and make sure you can do these practice midterm problems. solutions.

    Homework 8: No individual homework this week. Here is Group Homework 8. Group homework is due Thursday, March 28, 11:59pm, on Gradescope. Solutions to Homework 8.

    Homework 9: consists of Group Homework 9 and Individual Homework 9, due on Tuesday, April 9, 11:59pm, on Gradescope. This is the last homework that we will collect and grade this term. Solutions to Homework 9.

    Homework 10: Group Homework 10 will not be collected. Solutions to Homework 10.
    Piazza and Office Hours There will be an online discussion of this course on www.piazza.com; signing up to our course piazza site will likely involve UBC's Canvas system. Please post all questions related to the course material to our piazza site.
    Office hours, April 16-19:
    Tuesday: 3-5pm, Hao (TA): ICCS X835.
    Wednesday: 3:30-5pm, Gautam (TA): ICCS X835.
    Thursday: 2-3:30pm, Joel (Instructor): ICCS X530 (not the usual X561).
    Friday: 10:30am-12:30pm, Joel (Instructor): ICCS 304.
    Diversity and Equity UBC is trying in earnest to encourage diversity and alleviate biases and inequities to which some members of its community are subjected; this includes, for example, UBC's Indian Residential School History and Dialogue Centre, privileged to work with the Musqueam First Nation; this also includes the Computer Science Department's various programs described on its Diversity in CS webpage.
    I try to act reasonably free of bias; for example, I do not view sexual orientation or gender as set in stone from birth or as classified by some fixed, finite set of choices; I try to use language accordingly. I will undoubtedly goof upon occasion, and I welcome feedback on these and related matters.
    Calendar Class starts: Jan 8 (EOS building, Room 1012). Drop/Withdrawl without W: Jan 19. Family Day and Midterm Break: Feb 19-23. Midterm, during class hours: Friday, March 15. Good Fridy: March 29. Easter Monday: April 1. Classes end: April 12. Exam period: April 16-27. Our final exam: Sunday, Apr 21, 12:00 pm.

    UBC CS Home| Joel Friedman Home| Course Materials