### Graduate Studies and Postdoctoral Affairs (GSPA)

Needles Hall, second floor, room 2201

For more detailed course information, click on a course title below.

Course ID: 012175

Elementary counting, bijections. Sets, weights, decompositions. The ordinary generating series, sum, product, composition and differentiation lemmas; formal use in combinatorial identities. The algebra of formal power series. Strings on a finite alphabet. Unique factorization of strings. Pattern and noncommutative methods. The Maximal Decomposition Theorem. Rational and algebraic generating series, linear recurrence equations. Integer partitions. Functional equation. Ferrers graph, geometric decompositions, Euler's Pentagonal Number Theorem. Vector spaces over GF(q), linear transformations, finite forms of partition theorems, Gaussian coefficients. Inversions in permutations. The exponential generating series, rule of sum and product, composition and differentiation lemmas. Disjoint cycles and permutations, functions, set partitions, graphs. Lagrange's Implicit Function Theorem. Lattice paths, Wiener-Hopf Factorization. Lattice polygons, polyominos, trees and functions. Formal use in combinatorial identities. Enumeration under group action, Orbit-Stabilizer Theorem, Burnside's Lemma, Polya's Theorem. Necklaces, abstract trees and trees embedded in the plane.

Course ID: 012176

Linear optimization: Farkas' Lemma, duality, Simplex method, geometry of polyhedra. Combinatorial optimization: integrality of polyhedra, total unimodularity, flow problems, weighted bipartite matching. Continuous optimization: convex sets, Separation Theorem, convex functions, analytic characterizations of convexity, Karush-Kuhn-Tucker Theorem.

Course ID: 000232

The algebra of formal Laurent series. Multivariate ordinary generating functions and exponential generating functions. The Lagrange Implicit Function Theorem, the MacMahon Master Theorem. Enumeration of planar triangulations. The Transfer Matrix method. Sieve methods, Inclusion/Exclusion, Möbius inversion. Pólya Enumeration, Enumeration of Trees. Basic hypergeometric series, q-analogues, Rogers-Ramanujan identities. Asymptotic methods.

Course ID: 014211

The ring of symmetric functions, standard bases, the Hall inner project. Young tableaux. The Robinson-Schensted-Knuth correspondence, the hood-length formula, the Jacobi-Trudi formula, the Pieri rule, the Littlewood-Richardson rule. Representation theory of the symmetric groups. Enumeration of plane partitions. Enumeration of maps on surfaces. Other topics.

Course ID: 000233

Pairwise orthogonal latin squares. Transversal designs and finite planes. Balanced incomplete block designs, group divisible designs and pairwise balanced designs. Symmetric designs and Hadamard matrices. Recursive constructions. Wilson's fundamental construction.

Course ID: 000245

Colouring: Brooks' Theorem and Vizing's Theorem. Flows: integer and group-valued flows, the flow polynomial, the 6-flow theorem. Extremal graph theory; Ramsey's theorem, Turan's theorem, Mader's theorem on graphs with no n-clique-minor. Probabilistic methods: Lower bounds for Ramsey numbers, graphs with large girth and chromatic number.

Course ID: 000246

Automorphisms. Cayley graphs and their properties. Arc and distance transitive graphs. Generalised polygons. homomorphisms and covers. Adjacency and incidence matrices. Eigenvectors of graphs. Quotients. Interlacing. Strongly regular graphs. Line graphs and graphs with least eigenvalue -2. Expanders. Shannon capacity.

Course ID: 013351

This is an introductory course on matroid theory, with particular emphasis on graphic matroids and on topics that are applicable to graph theory. The topics include: matroid intersection and partition, graphic matroids, matroid connectivity, regular matroids, and representable matroids. Applications include: matching, disjoint spanning trees, the 8-flow theorem for graphs, planarity testing, and recognizing totally unimodular matrices.

Course ID: 000247

Characterizations of optimalsolutions and efficient algorithms for optimization problems over discrete structures. Topics include network flows, optimal matchings, T-joins and postman tours, matroid optimization.

Course ID: 000248

Formulation of problems as integer linear programs. Solution by branch-and-bound and cutting plane algorithms. Introduction to the theory of valid inequalities and polyhedral combinatorics.

Course ID: 000250

An introduction to the modern theory of convex programming, its extensions and applications. Structure of convex sets, separation and support, subgradient calculus for convex functions, Fenchel conjugacy and duality, Lagrange multipliers. Ellipsoid method for convex optimization.

Course ID: 000251

A course on theory and solution algorithms for the minimization of a convex quadratic function subject to linear constraints. Karush-Kuhn-Tucker conditions, duality theory. Active set solution algorithms and their parametric extensions. Quadratic programmes as linear complementarity problems. Applications in portfolio optimization and structural analysis.

Course ID: 000252

Numerical algorithms for nonlinear optimization. Newton, variable-metric, quasi-Newton and conjugate gradient methods. Obtaining derivatives. Convexity. Trust region methods. Constrained optimization including optimality conditions, sequential quadratic programming, interior point and active set strategies.

Course ID: 011371

Optimization over convex sets described as the intersections of the set of symmetric, positive semidefinite matrices with affine spaces. Formulations of problems from combinatorial optimization, graph theory, number theory, probability and statistics, engineering design and control theory. Theoretical and practical consequences of these formulations. Duality theory and algorithms.

Course ID: 015821

Techniques for formulating data science models as optimization problems. Algorithms for solving data science problems with an emphasis on scalability, efficiency and parallelizability including gradient-descent based algorithms, derivative-free algorithms, and randomized algorithms. Theoretical analyses of algorithms and approaches for recognizing the most suitable algorithm for solving a particular problem.

Course ID: 011589

Review of basics of quantum information and computational complexity; Simple quantum algorithms; Quantum Fourier transform and Shor factoring algorithm: Amplitude amplification, Grover search algorithm and its optimality; Completely positive trace-preserving maps and Kraus representation; Non-locality and communication complexity; Physical realizations of quantum computation: requirements and examples; Quantum error-correction, including CSS codes, and elements of fault-tolerant computation; Quantum cryptography; Security proofs of quantum key distribution protocols; Quantum proof systems. Familiarity with theoretical computer science or quantum mechanics will also be an asset, though most students will not be familiar with both.

Course ID: 010331

An in-depth study of public-key cryptography, including: number-theoretic problems - prime generation, integer factorization, discrete logarithms; public-key encryption; digital signatures; key establishment; secret sharing; and security definitions and proofs.

Course ID: 010471

A broad introduction to cryptography, highlighting the major developments of the past twenty years, including symmetric ciphers, hash functions and data integrity, public-key encryption and digital signatures, key establishment, and key management. Applications to internet security, computer security, communications security, and electronic commerce will be studied.

Course ID: 000269

Methods of obtaining asymptotic estimates for sums arising in enumeration. Application to Bell numbers, the distribution of balls into cells, and random graphs. Methods for obtaining asymptotic estimates for the coefficients of generating functions. Application to random planar graph problems and to unimodality problems.

Course ID: 011796

The probabilitistic method proves the existence of a combinatorial structure by showing a random element in an appropriate probability space has the desired properties with positive probability. The course will introduce the basic techniques and give applications in graph theory, combinatorics, discrete optimization, theoretical CS. In particular, some of the following will be considered: linearity of expectation; alterations; the second moment method; bounding of large deviations; the local lemma; correlation inequalities; martingales and tight concentration; discrepancy; derandomization.

Course ID: 000297

An introduction to the concepts of directed graphs, problems about directed circuits and directed cuts, and minimax equalities relating these and other graphical objects.

Course ID: 010474

A general study of algorithms for the solutions of problems in graph theory. Included are algorithms for graph isomorphism, planarity, connectedness, chromatic number, spanning trees, circuits and many others.

Course ID: 000304

Course ID: 011797

The course studies some of the successful paradigms for designing approximation algorithms and for proving approximation guaranteees, such as the greedy method, formulating and solving linear programming relaxations, the primal-dual method, randomized rounding, semidefinite programming relaxations, approximation of metrics. Also, the PCP theorem, and its application to the hardness of approximating specific problems, e.g., set covering and shortest lattice vector.

Course ID: 000317

Course ID: 011622

Basic optimization: quadratic minimization subject to leanear equality constraints. Effecient portfolios: the efficient frontier, the capital market line, Sharpe ratios and threshold returns. Practical portfolio optimization: short sales restrictions target portfolios, transactions costs. Quadratic programming theory. Special purpose quadratic programming algorithms for portfolio optimization: today's large investment firms expect to solve problems with at least 1000 assets, transactions costs and various side constraints in just a few minutes of computation time. This requires very specialized QP algorithms. An overview of such algorithms will be presented with computational results from commercial problems. The efficient frontier, the capital market line, Sharpe ratios and threshold returns in practice.

Course ID: 011299

Fundamental problems of elementary and algebraic number theory from an algorithmic and computational complexity point of view with emphasis placed on analysis of algorithms. Topics include basic arithmetic algorithms; computation over finite fields; primality testing; algorithms for integer factorization; algorithms in number fields.

Course ID: 010481

Needles Hall, second floor, room 2201

University of Waterloo

University of Waterloo

43.471468

-80.544205

200 University Avenue West

Waterloo,
ON,
Canada
N2L 3G1