_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/ecse443.html
Requirements
================================================================================
We outline some high-level requirements and expectations, below.
Prerequisites
-----------------------------------------------
* [*ECSE 202*: Introduction to Software Development](https://www.mcgill.ca/study/2019-2020/courses/ecse-202)
* [*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 coding quite a bit in this course, and so expertise with data structures, algorithms, and basic software engineering practices will be valuable.
Textbook
---------------------------------------------------
Supplemental recommended readings will be provided during lecture, across the following textbooks.
*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.
!!! Tip
You don't __need__ to buy any of these texts to be successful in the course, but it can help. Leveraging *lecture* and *tutorial* time (i.e., consistent attendance, taking notes and asking questions) correlates much more with success than exhaustively completing recommended readings.
Equipment
---------------------------------------------------
You don't need to buy any equipment. IT has configured lab machines in Trottier with an ECSE 443 development stack. The [first assignment](#Assignments) provides multi-platform instructions for setting up a local development environment, if you choose to work on a personal machine.
Time
---------------------------------------------------
We *strongly encourage* attending every lecture. 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 five (5) [assignments](#assignments) and in-lecture [micro-quizzes](#quizzes).

- Setup your Jupyter Notebook & Python environments - Explore floating point limitations on simple problems -

- Forward and backward substitution - Cholesky factorization - Normal equations and polynomial fitting - Regularized image denoising -

- Polynomial regression - MLE, MAP - Expectation-maximization - Gaussian mixture models - Image color segmentation -

- Spatially-varying image convolution - brute force - power iteration factorization - SVD for realistic kernels - Image deblurring with steepest descent -

- Discrete Fourier Transform - Brute force - Fast Fourier Transform - Analysing and Visualizing DFT Output -

: 0a -- Introduction & Administration
- Course administration
- Course outline and schedule
- Quiz, assignment and grading policies
: 0b -- Floating Point
- 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
: 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
: 1a -- Linear Algebra: Review
- Review
- 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)** & **(A1 out)**
- Gaussian elimination
- forward/backward substitution
- numerical issues
- Elementary matrix operations and their inverses
: 1b -- LU Factorization
- Pivoting (partial vs. full)
- LU performance
- Solving systems with LU
- Example #1: polynomial regression
- Example #2: image deconvolution
: 2a -- Linear Systems: Conditioning

**Quiz #1 -- Linear algebra**
- 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

**Quiz #2 -- LU & Cholesky**
- Review
- Experiment, sample space, event
- Discrete random variables
- Probability mass function
- Conditional probability
: 3a -- Probability
- Review
- Total probability
- Bayes' theorem
- Continuous domain
- Probability density function
: 3b -- Maximum Likelihood Estimation
- Explicit model of noise
: 3b -- Maximum Likelihood Estimation

**Quiz #3 -- Norms & Condition**
- 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

**Quiz #4 -- QR & Regularization**
- 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

**Quiz #5 -- MLE & MAP**
- Principal components analysis
- Solving systems of ODEs
: 4c -- Singular Value Decomposition
: 4c -- Singular Value Decomposition
: 4d -- SVD Applications

**Quiz #6 -- Eigendecomposition**
(): Reading Week

(no class)

**(A3 out)**
(): Reading Week

(no class) (): Reading Week

(no class) : 5a -- Root Finding

**(A2 due)**
- Non-linear systems of equations
- Bisection search
- Convergence analysis
: 5b -- Taylor Series & Convolution

**(A3 out)**
- 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

**Quiz #7 -- SVD**
- Higher-order root finding
- Evaluating gradients
- Secant method
- Multivariable root finding
- Vector calculus & Multivariable Taylor
- Newton's method
- Quasi-Newton methods
: 5c -- 1D Optimization

**Quiz #8 -- 1D Root-finding**
- 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
: 5e -- Gradient Descent

**Quiz #9 -- Optimization**
- Basic gradient descent
- Step size and count
- Line search
- Solving linear systems with gradient descent
- Deriving the optimal step size
- Motivating conjugate gradient
(): Good Friday

(no class) (): Easter

(no class) : 6 - Fast Fourier Transform

**Quiz #10 -- Gradient Descent**

**(A3 due)**
- Fourier Series & Transforms
- Computing the DFT
- Fast Fourier Transform
- Applications
: **(A4 due)**
():

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).
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)

(no class) (): Reading Week

(no class) : 5a -- Root Finding

(no class) (): Easter

(no class) : 6 - Fast Fourier Transform