MATH 168A (Spring Quarter 2019).
Topics in Applied Mathematics and Computer Science

Instructor: David A. MEYER
Email: dmeyer "at" math "dot" ucsd "dot" edu
Office hours (Spring Quarter): AP&M 7256 F 1:00pm- 2:00pm, or by appointment
Lectures: Center Hall 109, MWF 12:00pm-12:50pm

Teaching Assistant: Sameeksha KHILLAN
Office hours: Mayer Hall 5722, TuTh 9:30am-11:30am, or by appointment
Section A01: Center 217A, M 6:00pm-6:50pm; section will not meet M Apr 1
Section A02: Center 217A, M 7:00pm-7:50pm; section will not meet M Apr 1
Email: skhillan "at" eng "dot" ucsd "dot" edu

Teaching Assistant: Daniel COPELAND
Office hours: AP&M 5768, W 3:30pm-5:30pm, or by appointment
Section A03: AP&M 2402, M 5:00pm-5:50pm; section will not meet M Apr 1
Email: drcopela "at" ucsd "dot" edu

Course description

The topic for this course is random walk algorithms, which I have chosen because (1) there are several practically important random walk algorithms, including, for example, PageRank and MCMC sampling; (2) there is a conceptually important connection with physics, specifically the heat equation; and (3) they provide a convenient entryway to quantum algorithms.

After providing some background information I will introduce random walks, explain the connection with physics, and describe several random walk algorithms in detail. This will take the first 6-7 weeks of the course. In the last few weeks I plan to introduce quantum walks, explain their connection to physics, and work through at least one quantum walk algorithm in detail.

The prerequisites are first year calculus through the level of Math 20C and linear algebra (Math 18 or Math 31AH). Since this is partly a computer science course, I will expect students to be able to write and run their own computer code, at least in Matlab (since that is used in Math 18). There will be programming assignments, to complete which students will be free to use any language they like. Some familiarity with probability (e.g., Math 180AB) and differential equations (e.g., Math 110AB) will make the course easier, but since these are not prerequisites, I plan to explain the necessary concepts in lecture. Finally, there will be proofs, both in lecture and in homework assignments, so Math 109 will be helpful. Since almost all the students are junior or senior math or CS majors, I do not expect this to be an obstacle.

There is no textbook. I will point to online resources, i.e., mathematics or computer science papers, for some of the material.

Grading: There will be weekly homework assignments, which will constitute 40% of the course grade. Students must write up their own homework solutions; multiple identical solutions will receive no credit. Homework will be submitted online, to Gradescope. Information on student computer accounts is available on TritonLink; locations of computer labs are listed at ETS; as is available software. There will be a midterm exam (20%) and a final exam (40%).

Related events

May 10, 2019 Undergraduate Mathematics Honors Thesis presentations
Clara Woods, Quantum walks
AP&M, room 6402, 10:20am-10:40am
Spring 2019 Art of Problem Solving (AoPS) Summer Teaching Assistant job application

Syllabus (homework in green)

Apr 1, 2019
DM lecture
administrative details
overview/motivation
What is an algorithm?
         etymology, from Muhammad ibn Musa al-Khwarizmi
         example: completing the square [1]
         example: primality testing
                 pseudocode
                 running time
                 big-O notation
[notes 1]
Apr 3, 2019
DM lecture
digression on the primality of 1
         history [2]
         irreducibility and primality in integral domains
                 review of complex numbers and norms
probability review/introduction [3]
         sample space, events
         discrete probability distribution
         conditional probability
         independence
[notes 2]
Apr 5, 2019
DM lecture
         (real-valued) random variables
         expectation value and its properties
         variance and its properties
[notes 3]
Apr 8, 2019
DM lecture
         independence for sets of events and random variables
sequence of independent coin flips
         probability distribution for the number K of heads up
         expectation value and variance of K
         "step" random variable St which is 1 for head and -1 for tail
         Xt = S1 + ... + St
[notes 4]
HWK (due 5:00pm M Apr 15; submission instructions).
         Write code to simulate 100 steps of a random walk, with Pr(St = 1) = p.
         Plot the results for one run for each of p = 0.5, p = 0.4, and p = 0.6.
         Run this routine many times and plot the histogram of X100, for some fixed p.
         Compute the mean and the variance of your data.

Apr 10, 2019
DM lecture
         random walk on Z is {Xt}
definition of stochastic process
         definition of Markov process
                 states and transition probabilities
random walks on Z and Z/lZ as Markov processes
[notes 5]
Apr 12, 2019
DM lecture
         diagrams of random walks on Z and Z/lZ
         probability distribution of Xt is given by Ptu0
         x + t (mod 2) is a conserved quantity on Z and Z/lZ for even l
defining a new Markov process from two steps of a random walk
[notes 6]
Apr 15, 2019
DM lecture
         a system of difference equations for the probabilities at each state at each time
         review of limit definition of first and second derivatives
         continuum limit of random walk difference equation is heat equation with drift
         solution of the the drift (advection) equation
[notes 7]
HWK (due 5:00pm M Apr 22)
         1. Let P be a stochastic NxN matrix, i.e., Pij ≥ 0, ∑i Pij = 1, for all j.
         Prove that if vRN has ∑j vj = c, then PvRN has ∑j(Pv)j = c.
         2. Modify, or rewrite, your code for a random walk with p = 1/2 on Z to implement a random walk on Z/6Z.
         Run this routine many times and plot the histogram of X100.

Apr 17, 2019
DM lecture
         solving the heat equation by analogy with the random walk probability distribution
                 Stirling's approximation for n!
                 Laplace's derivation of the normal approximation to a binomial distribution
[notes 8]
Apr 19, 2019
DM lecture
         the heat kernel
                 limit of the heat kernel as t goes to 0
                 definition of distribution and Dirac delta "function"
[notes 9]
Apr 22, 2019
DM lecture
         initial condition for solution to heat equation
         analogy with evolution of random walk from initial probability distribution
         solution of heat equation by convolution of initial condition with heat kernel
[notes 10]
HWK (due 5:00pm M Apr 29; submission instructions)
         Homework 3 [pdf] [TeX]

Apr 24, 2019
DM lecture
numerical algorithm for simulating the heat equation
physical intuition for relation between random walk and heat/diffusion equation
two particles randomly walking without interaction in 1D
one particle randomly walking in 2D
         simulation of the heat equation in 2D
[notes 11]
Apr 26, 2019
DM lecture
         Gaussian blurring
is blurring invertible?
         element in nullspace of B on Z/2kZ
         nontrivial kernel of B implies not invertible
computing the nullspace
         diagonalizing X diagonalizes B
[notes 12]
Apr 29, 2019
DM lecture
         eigenvalues of X are Nth roots of 1
         computing the corresponding eigenvectors
         the discrete Fourier transform
         eigenvalues of B
[notes 13]
HWK (due 11:59pm W May 8)
         Homework 4 [pdf] [TeX]
May 1, 2019
DM lecture
         dimensions and real basis vectors for the eigenspaces of B
         initial probability distribution in this Fourier basis
         evolution in the Fourier basis
         limiting distribution and rate of approach to it
         inverting the evolution and unblurring
[notes 14]
May 1, 2019
DM lecture
Midterm review; Peterson 103; 7:00pm-8:30pm
         overview of course and main ideas
         [practice exam problems] [solutions]
May 3, 2019 Midterm
Please bring bluebooks and your student ID. You may bring a page of handwritten notes, but nothing else.
[seat assignments]
[exam] [solutions] [results]
May 6, 2019
DM lecture
properties of general stochastic matrix P
         P has at least one eigenvalue 1
         definition of stationary distribution as eigenvector of P with eigenvalue 1
         every eigenvalue of P has norm less than or equal to 1
May 8, 2019
DM lecture
properties of real symmetric matrix M
         M has only real eigenvalues
         the eigenvectors of M can be chosen to be real
         the eigenvectors of M with different eigenvalues are orthogonal
         M can be diagonalized by an orthogonal matrix
HWK (due 11:59pm W May 15)
         Homework 5 [pdf] [TeX]
May 10, 2019
DM lecture
Google PageRank algorithm
         model user behavior by random walk
         modify model to have symmetric transition probability matrix
         compute PageRank from stationary state
May 13, 2019
DM lecture
Guess a number problem (SEARCH)
         very naive algorithm as random walk on possible answers {1,2,...,N}
                 number of guesses is O(N log(1/ε))
         less naive algorithm as random walk on possible answers {1,2,...,N}
                 number of guesses is still O(N log(1/ε))
         least naive algorithm as random walk on number of remaining possibilities {N,N-1,...,1}
                 number of guesses is still O(N)
May 15, 2019
DM lecture
Boolean expressions
         de Morgan's laws
         satisfying assignments
         disjunctive normal form (DNF)
         conjunctive normal form (CNF)
HWK (due 11:59pm W May 22)
         Homework 6 [pdf] [TeX]
May 17, 2019
DM lecture
basics of computational complexity: P, NP and NPC
2-SAT: satisfiability for 2-CNF expressions
         application to clustering
Papadimitriou's random walk algorithm for 2-SAT [5]
May 20, 2019
DM lecture
analysis of Papadimitriou's algorithm
         as random walk on Hamming distance from solution
         expected time to solution if one exists
         Markov inequality to bound probability using expectation value
failure of analogous random walk algorithm for 3-SAT
Bonus points (due 11:59pm M May 27)
         Problem [pdf] [TeX]
May 22, 2019
DM lecture
axiomatic introduction to quantum mechanics
         unitary matrix as transition amplitude matrix
HWK (due 11:59pm W May 29)
         Homework 7 [pdf] [TeX]
May 24, 2019
DM lecture
analogy between homogeneous Markov process and repeated multiplication by unitary matrix
eigenvalues and diagonalization of unitary matrices
         consquent non-convergence of "unitary process"
a quantum walk algorithm for guess a number (SEARCH)
         derivation of unitary matrix to represent transition to new guess
May 27, 2019
No lecture; Memorial day.
May 29, 2019
DM lecture
         including a "sink" at the answer would destroy unitarity
         so expand vector space to include flag for having found, or not, the solution
         quantum algorithm as product of unitary matrix for checking guess and unitary matrix for making new guess
         with clever initial state, reduce back down to N dimensional vector space
HWK (due 11:59pm W Jun 5)
         Homework 8 [pdf] [TeX]
May 31, 2019
No lecture.
Jun 3, 2019
DM lecture
         identification of unitary operations as relections
         geometrical analysis of algoritm to find O(N1/2) run time
         this is Grover's quantum SEARCH algorithm [6]
quantum walk on Z/NZ
         a X + b X-1 is only unitary if one of a and b is 0
Jun 5, 2019
DM lecture
         expand vector space to include direction as well as position
         general form of 2x2 unitary matrix
         impose left-right symmetry for "unbiased" quantum walk
Jun 7, 2019
DM lecture
         as with classical random walk, consider new process consisting of two timesteps
         a system of difference equations for the amplitudes at each state at each time
         continuum limit of quantum walk difference equation is Dirac equation
         analogously to classical case, can solve for amplitudes, derive solution to Dirac equation
Jun 10, 2019
DM lecture
Final review; AP&M B402A; 6:00pm-7:00pm
         overview of course and main ideas
         [practice exam problems] [solutions]
Jun 12, 2019 Final; Center 109; 11:30am-2:29pm
Please bring bluebooks and your student ID. You may bring a page of handwritten notes, but nothing else.
[seat assignments]
[exam] [solutions] [results]

Suggested reading

[1] P. Maher, "From al-jabr to algebra", Mathematics in School 27 (1998) 14—15.
[2] C. K. Caldwell and Y. Xiong, "What is the smallest prime?", Journal of Integer Sequences 15 (2012) Article 12.9.7.
[3] K. Baclawski and G.-C. Rota, Introduction to Probability and Random Processes (1979).
[4] G. F. Simmons, Differential Equations with Applications and Historical Notes, Third Edition (Boca Raton, FL: CRC Press 2017).
[5] C. H. Papadimitriou, "On selecting a satisfying truth assignment", in Proceedings 32nd Annual Symposium of Foundations of Computer Science (Los Alamitos, CA: IEEE 1991).
[5] L. K. Grover, "A fast quantum mechanical algorithm for database search", in Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing (New York, NY: ACM 1996) 212-219

Last modified: 19 June 2019.