_The course syllabus and schedule may be revised during the semester. The latest version is always online here,
at_ http://www.cim.mcgill.ca/~derek/ecse343.html
Requirements
================================================================================
We outline some high-level requirements and expectations, below.
Prerequisites
-----------------------------------------------
* [*ECSE 205*: Probability and Statistics for Engineers](https://www.mcgill.ca/study/2019-2020/courses/ecse-205) and
* [*COMP 250*: Introduction to Computer Science](https://www.mcgill.ca/study/2019-2020/courses/comp-250)
* [*MATH 263*: Ordinary Differential Equations for Engineers](https://www.mcgill.ca/study/2019-2020/courses/math-263)
We expect you to be comfortable with __multivariate calculus__, __probability__ (discrete and continuous) and __linear algebra__: much of the theory we present in the course will focus on _re-framing_ mathematical constructs through an algorithmic and computational lens.
Furthermore, you'll be expected to code your own assignment solutions during this course, and so comfort with data structures and algorithms will be valuable; coding solutions will not require large software engineered solutions, but will rather focus on implementing and testing the core algorithms and numerical methods. This course will afford you the opportunity to become comfortable with vectorized numerical computation using `Python` and `numpy`.
Textbook
---------------------------------------------------
When appropriate, supplemental recommended readings will be provided during lecture across the following textbooks.
!!! Tip
You don't __need__ to buy any of these texts to be successful in the course, but some of you may find it helpful. Leveraging *lecture* and *tutorial* time (i.e., consistent attendance, taking notes and asking questions) is much more important for building an understanding and retaining the knowledge you gain.
*Scientific Computing: An Introductory Survey* (_Revised 2nd ed._)

by Michael T. Heath
![Recommended Text I](https://my.siam.org/Store/ProductImages/CL80large.jpg width="25%")
This text focuses on the core ideas behind fundamental algorithms, rather than a detailed numerical analysis. Problems in mathematical & computational modeling, data analysis, and hands-on engineering examples are presented in a clear and concise style. Readers are guided through the processes of properly formulating any specific problem, carefully choosing an appropriate numerical algorithm to resolve the problem, and interpreting the results of the algorithm. Our course will rely heavily on the exposition and examples provided in _Scientific Computing: An Introductory Survey (Revised Second Edition)_.
*Numerical Algorithms:* Methods for Computer Vision, Machine Learning, and Graphics

by Justin Solomon
![Recommended Text II](https://people.csail.mit.edu/jsolomon/assets/bookcover.jpg width="25%")The core concepts in numerical methods for linear and non-linear problems are presented from a similar perspective, with insightful geometric interpretations and diagrams. What most differentiates this book is a bit more of a focus on methods employed in current practice, presenting a more hands-on approach to numerical analysis for modern computer scientists and engineers. Examples vary across many computational tasks, from data processing, computational photography, and physics-based animation. The text does a good job guiding the reader from theoretical insights to numerical modeling and algorithmic design. As with any modern text on the subject, this one covers topics from numerical linear algebra to optimization and differential equations. The text targets an advanced undergraduate and graduate audience, assuming strong foundations in calculus and linear algebra.
![Recommended Text III](https://my.siam.org/Store/ProductImages/CS07large.jpg width="25%")
*A First Course in Numerical Methods*

by Uri M. Ascher and Chen Greif
This text also balances theoretical concepts with practical knowledge, doing a good job of highlighting the importance of moving from a mathematical formulation of a problem to a computational one. I particularly like the way this text presents the importance of parallelization, cache coherence, and other systems-level details that must be treated by a _designer_ of efficient numerical methods. That being said, those with less experience in advanced undergraduate linear algebra might have a harder time working through some of the more mathematical concepts presented early on the book; that being said, in taking the time to build this background, one becomes much better equipped to work through the rest of the "standard set" of numerical methods presented throughout the book. This text also does a very good job of helping the reader understand the many reasons behind the success and failure of numerical software. MATLAB is treated as a first class citizen in this text, and the transition from MATLAB- to Python-based numerical method development is not a large one. The target audience, as with the Solomon text, is senior undergraduate and beginning graduate level.
Equipment
---------------------------------------------------
IT has configured lab machines in Trottier with an ECSE 343 development stack. The [first assignment](#Assignments) provides multi-platform instructions for setting up a local development environment, for completing work on a personal machine.
Time
---------------------------------------------------
Attendance is *strongly encouraged*. Plan to invest *9 hours of work per week*, on average, including lecture and tutorial time.
For assignments, start early and schedule appropriately. Attending tutorials with your prepared questions is a good way to skirt avoidable difficulties.
Evaluation
=====================================================================
Your evaluation is based on Python coding [assignments](#assignments) and a final [group project](#project).

- Setup your Python 3.7 environment - Floating point, `numpy` and vectorization -

- Forward and backward substitution - Normal equations and polynomial fitting - Image deconvolution -

- Polynomial regression - MLE, MAP, LLS - Expectation-maximization - Gaussian mixture models -

- 2D image (de)convolution - Explicit regularization - Singular value decomposition -

- 1D and 2D Discrete Fourier Transform - Convolution and Deconvolution in the Frequency Domain - Frequency-space Regularization -

: 0 -- Administration & Floating Point
- Course administration
- Course outline and schedule
- Grading policies
- Overview of floating point number systems
- IEEE floating point
- Rounding and discretization error
- Forward vs. backward error
- Conditioning: forward vs. backward error
- Absolute vs. relative error
: 0 -- Floating Point
- _Continuation of previous lecture topics_
: 1a -- Linear Algebra: Review
- Review
- Vectors
- Vector spaces
- Measures: norms and inner products
- Basis and Span
- Canonical linear basis
- Orthonormal basis
- Matrices as linear bases
: 1a -- Linear Algebra: Review

**(A0 out)**
- Review
- Linear maps
- Transformations
- Inverse transforms
- Methodological case study: 2D rotation
- Linear transformation zoo
- Linear transform composition
- Revisiting the determinant
- Translation: motivating homogenous coordinates
- Affine maps
- Composition
- From 2D to 3D to $n$-D
: 1b -- Solving simple linear systems
- Review of linear systems of equations
- Algebraic solution (in 2D)
- Geometric solution (in 2D)
- Matrix solution (in 2D)
- Existence conditions for inversion
: 1b -- LU Factorization

**(A0 due)**
- Gaussian elimination
- forward/backward substitution
- numerical issues
- Elementary matrix operations and their inverses
- Pivoting (partial vs. full)
- LU performance
- Solving systems with LU
- Example #1: polynomial regression
- Example #2: image deconvolution
: 2a -- Linear Systems: Conditioning

**(A1 out)**
- Induced matrix norms
- Solving perturbed linear systems
- Condition number
- Conditioning of simple problems
: 2b -- Least Squares & Variants
- Overdetermined systems
- Least-squares and the normal equations
- Weighted least squares
: 2c -- QR Decomposition & Regularization
- Total least squares
- Conditioning of the normal equations
- QR Factorization
- Tikhonov regularization
- applied to normal equations
- applied to QR decompositions
: 3a -- Probability
- Review
- Experiment, sample space, event
- Discrete random variables
- Probability mass function
- Conditional probability
- Total probability
- Bayes' theorem
- Continuous domain
- Probability density function
: 3b -- Maximum Likelihood Estimation
- Explicit model of noise
- Relationship between MLE and Least-squares
- Non-zero mean
: 3c -- Maximum A Posteriori Estimation

**(A1 due)** & **(A2 out)**
- Prior distributions on model parameters
- Data- vs. Model-dependence
: 3d -- Maximum A Posteriori Estimation
- Relationship between LLS, MLE and MAP
: 3d -- Expectation Maximization
- Fitting several models
: 4a -- Eigendecomposition
- Eigenvectors and eigenvalues
- Eigendecomposition
- general case and symmetric matrices
- Computing eigendecompositions
- Power method
- Limitations
: 4b -- Eigendecomposition Applications
- Total least squares
: 4c -- Eigendecomposition Applications
- Principal components analysis
- Solving systems of ODEs
: 4c -- Singular Value Decomposition

**(A2 due)** & **(A3 out)**
: 4c -- Singular Value Decomposition
: 4d -- SVD Applications
(): Reading Week

(no class) (): Reading Week

(no class) : 5a -- Root Finding - Non-linear systems of equations - Bisection search - Convergence analysis : 5b -- Taylor Series & Convolution Review - Standard Series Expansions - Maclaurin series expansion - Taylor series expansion - Convolutions : 5b -- Advanced Root Finding - Linearizing problems - Higher-order root finding - Newton's method : 5b -- Advanced Root Finding - Higher-order root finding - Evaluating gradients - Secant method - Multivariable root finding - Vector calculus & Multivariable Taylor - Newton's method - Quasi-Newton methods : 5c -- 1D Optimization

**(A3 due)** & **(A4 out)**
- Root-finding vs. optimization
- Convex (and concave) functions
- Unimodular functions
- Golden section search
- Newton's method for 1D optimization
: 5d -- Multivariate Optimization
- Newton's method for multivariable optimization
- Line search
- Approximating Hessians
- BFGS
: 6a -- Fourier
- Fourier Series
- Fourier Transforms
: 6b -- Discrete Fourier Transform
- Discrete Fourier Transform
- Computing the DFT
: 6c -- FFT
- Fast Fourier Transform
: 7a -- Better Polynomials
- Gram Schmidt Orthogonalization
- Polynomial Error/Accuracy
- Chebyshev nodes
: 7a -- Beyond Polynomials
- Splines
- Radial Basis Functions
: 7b -- Numerical Integration
- Quadrature rules
: Project Options Presentation

**(A4 due)** & **(Project out)**
- We will review the various group project choices
: 7b -- Numerical Integration
- Monte Carlo Integration
- Variance Reduction
- Importance Sampling
: 8 -- Gradient Descent
- Basic gradient descent
- Step size and count
- Line search
- Solving linear systems with gradient descent
- Deriving the optimal step size
- Steepest Descent
: 8 -- Gradient Descent
- Conjugate Gradient
(): End

**(Project due)**
- TBD

Collaboration & Plagiarism
=====================================================================
*Plagiarism* is an academic offense of misrepresenting authorship. This can result in penalties up to expulsion. It is also possible to plagiarise _your own work_, e.g., by submitting work from another course without proper attribution. **When in doubt, attribute!**
We expect you to submit your own work. Assignments are individual tasks. That said, we want to promote an environment where you are comfortable discussing ideas together. **A good rule to follow**: fully understand every solution you submit and only submit code that was written by you.
McGill values academic integrity and students should take the time to fully understand the meaning and consequences of cheating, plagiarism and other academic offenses (as defined in the Code of Student Conduct and Disciplinary Procedures -- see [these](www.mcgill.ca/integrity) [two](www.mcgill.ca/students/srr/honest) links).
!!! warning:
Computational plagiarism detection tools are employed as part of the evaluation procedure in ECSE 343.
In accordance with article 15 of the Charter of Students' Rights, students may submit any written or programming components in either French or English.
If you have a disability, please advise the [Office for Students with Disabilities](www.mcgill.ca/osd) (514-398-6009) as early in the semester as possible. In the event of circumstances beyond our control, the evaluation scheme as set out above may require modification.
Additional policies governing academic issues which affect students can be found in the Handbook on Student Rights and Responsibilities.
(no class) (): Reading Week

(no class) : 5a -- Root Finding - Non-linear systems of equations - Bisection search - Convergence analysis : 5b -- Taylor Series & Convolution Review - Standard Series Expansions - Maclaurin series expansion - Taylor series expansion - Convolutions : 5b -- Advanced Root Finding - Linearizing problems - Higher-order root finding - Newton's method : 5b -- Advanced Root Finding - Higher-order root finding - Evaluating gradients - Secant method - Multivariable root finding - Vector calculus & Multivariable Taylor - Newton's method - Quasi-Newton methods : 5c -- 1D Optimization