CPSC 536J Homepage, Spring 2019

This page concerns CPSC 536J--Topics in Algorithms and Complexity: Linear Algebra Problems--Section 201.

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

News This article has a write up of some problems assigned in class.
CPSC 536J will meet from 8:50-9:40am in ICCS room 246.
Diversity news: Black History Month began in Canada on Friday, Feb 1; for example, anyone connected to the UBC wifi can watch (free of charge) I Am Not Your Negro (James Baldwin, posthumously), courtesy of Kanopy.
Overview This is a topics course on the application of linear algebra to algorithms and complexity theory; the typical application is to take a locally specified graph (network, Markov chain, simplicial complex, object-feature matrix, etc.) and to derive some global information that is not apparent from the local structure. Here is a list of possible topics to be covered; part of my choice of topics will depend on the interests of the students.
Prerequisites I will assume some exposure to linear algebra and sufficient "mathematical maturity." When we discuss Betti numbers, it will be helpful to have seen some point-set topology.
Homework and Grades Grades will be based on homework problems and/or an expository essay, and have the following meaning.
Tentative Class Content The first few weeks will likely give many examples what we can and cannot say about large systems when we know the "first few" eigenvalues of an associated matrix; the applications include:
  • Edge and vertex expansion in graphs.
  • Markov chain convergence and mixing, including PageRank and reversible Markov chains.
  • Shannon capacity.
  • Matrices of the form XT X, i.e., positive semidefinite matrices, arising in (0) projection, curve fitting or regression (you may have seen this in a linear algebra class); (1) PCA (principal component analysis) and SVD (singular value decomposition); (2) variance-covariance matrices; (3) Laplacians of graphs, of reversible Markov chains, of Hodge theory, of PDE's (partial differential equations), etc.; (4,5,...) etc.
All of these applications are unified by eigenvalues of matrices, although the goals are typically very different and eigenvalues give limited information regarding these goals.
Boards Scans, Etc. Scan of boards for: 01_02 to 01_23 (Introduction and Introduction to Eigenvalues and Expansion). 01_25 to present (Reversible Markov Chains).
Schedule CPSC 536J will meet from 8:50-9:40am in ICCS room 246. Classes begin: Jan 2; classes end: April 4; midterm break Feb 18-22 (Family Day is Feb 18).
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 Center, and well as the Computer Science Department's various programs described on its Women 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.

UBC Math Home| Joel Friedman Home| Course Materials