Course Descriptions - Undergraduate Calendar 2019-2020

 C O M B I N A T O R I C S   A N D   O P T I M I Z A T I O N

Notes

Fourth-year courses which require an 80% average as a prerequisite are held with corresponding graduate courses. Students with averages below 80% may enrol in these courses with the permission of the instructor.

CO 200s

 CO 227 LEC 0.50 Course ID: 003887 Introduction to Optimization (Non-Specialist Level) A broad introduction to the field of optimization, discussing applications, and solution techniques. Mathematical models for real life applications; algorithms: simplex, cutting plane, and branch & bound; linear programming duality. [Offered: F,W] Prereq: One of MATH 106, 114, 115, 136, 146. Antireq: CO 250/350, 352, 255/355

 CO 250 LEC 0.50 Course ID: 003895 Introduction to Optimization A broad introduction to the field of optimization, discussing applications and solution techniques. Mathematical models for real life applications; algorithms; aspects of computational complexity; geometry; linear programming duality, focusing on the development of algorithms. [Offered: F,W,S] Prereq: One of MATH 106 with a grade of at least 70%, MATH 115, 136, 146; Cumulative overall average of at least 60%. Antireq: CO 227, 352, 255/355 Also offered Online

 CO 255 LEC 0.50 Course ID: 003897 Introduction to Optimization (Advanced Level) Linear optimization: feasibility theorems, duality, the simplex algorithm. Discrete optimization: integer linear programming, cutting planes, network flows. Continuous optimization: local and global optima, feasible directions, convexity, necessary optimality conditions. [Note: CO 255 may be substituted for CO 250/350 whenever the latter is a requirement in an Honours plan. Offered: W] Prereq: MATH 235 or 245, 237 or 247. Antireq: CO 227, CO 250, CO 350, 352, 355

CO 300s

 CO 327 LEC 0.50 Course ID: 003890 Deterministic OR Models (Non-Specialist Level) An applications-oriented course that illustrates how various mathematical models and methods of optimization can be used to solve problems arising in business, industry, and science. [Offered: W,S] Prereq: One of CO 227, 250/350, 352, 255/355. Antireq: CO 370

 CO 330 LEC 0.50 Course ID: 003891 Combinatorial Enumeration The algebra of formal power series. The combinatorics of the ordinary and exponential generating series. Lagrange's implicit function theorem, applications to the enumeration of permutations, functions, trees and graphs. Integer partitions, geometric methods, enumerating linear transformations. Introduction to the pattern algebra, applications to the enumeration of strings. Lattice paths, Wiener-Hopf factorization. Enumeration under symmetries. [Offered: F] Prereq: MATH 239 or 249

 CO 331 LEC 0.50 Course ID: 003892 Coding Theory A first course in error-correcting codes. Linear block codes, Hamming-Golay codes, and multiple error-correcting BCH codes are studied. Various encoding and decoding schemes are considered. [Offered: W] Prereq: MATH 225 or 235 or 245

 CO 342 LEC 0.50 Course ID: 003893 Introduction to Graph Theory An introduction to some of the key topics in graph theory: connectivity, planarity, and matchings. Connectivity: Menger's theorem, 3-connected graphs. Planarity: Kuratowski's theorem, uniqueness of planar embeddings. Matchings: Review of Konig's theorem, Tutte's theorem. [Offered: F,S] Prereq: MATH 239 or 249

 CO 351 LEC 0.50 Course ID: 003896 Network Flow Theory Review of linear programming. Shortest path problems. The max-flow min-cut theorem and applications. Minimum cost flow problems. Network simplex and primal-dual algorithms. Applications to problems of transportation, distribution, job assignments, and critical-path planning. [Offered: F,S] Prereq: One of CO 250/350 or 352 or 255/355.

 CO 353 LAB,LEC 0.50 Course ID: 011442 Computational Discrete Optimization Formulations of combinatorial optimization problems, greedy algorithms, dynamic programming, branch-and-bound, cutting plane algorithms, decomposition techniques in integer programming, approximation algorithms. Prereq: One of CO 250/350 or 352 or 255/355.

 CO 367 LAB,LEC 0.50 Course ID: 003898 Nonlinear Optimization A course on the fundamentals of nonlinear optimization, including both the mathematical and the computational aspects. Necessary and sufficient optimality conditions for unconstrained and constrained problems. Convexity and its applications. Computational techniques and their analysis. [Offered: F] Prereq: (One of CO 250/350, 352, 255/355) and MATH 128 with a grade of at least 70% or MATH 138 or 148

 CO 370 LAB,LEC 0.50 Course ID: 003899 Deterministic OR Models An applications-oriented course that illustrates how various mathematical models and methods of optimization can be used to solve problems arising in business, industry, and science. [Offered: F,W] Prereq: CO 250/350 or 352 or 255/355. Antireq: CO 327

 CO 372 LAB,LEC 0.50 Course ID: 011736 Portfolio Optimization Models Computational optimization methodologies underlying portfolio problems in finance. Computational linear algebra, determining derivatives, quadratic, and nonlinear optimization. The efficient frontier problem. Applications of optimization in finance such as volatility surface determination and global minimization for value-at-risk. [Offered: F,W] Prereq: (AFM 272/ACTSC 291 or ACTSC 371 or BUS 393W or ECON 371) and (CO 250/350 or CO 227 with a grade of at least 70% or CO 352 or CO 255/355). Antireq: CO 370 taken prior to Winter 2004

 CO 380 LEC 0.50 Course ID: 003901 Mathematical Discovery and Invention A course in problem solving. 100 problems are studied. Problems are taken mainly from the elementary parts of algebra, geometry, number theory, combinatorics, and probability. [Note: Offered in the spring term of even years.] Prereq: MATH 135 or 145, MATH 106 or 136 or 146, MATH 138 or 148; Level at least 3A

CO 400s

 CO 430 LEC 0.50 Course ID: 003902 Algebraic Enumeration The algebra of Laurent series and Lagrange's Implicit function theorem, enumerative theory of planar embeddings (maps). The ring of symmetric functions: Schur functions, orthogonal bases, inner product, Young tableaux, and plane partitions. Non-intersecting paths, sieve methods, partially ordered sets, and Mobius inversion, strings with forbidden substrings, the Cartier-Foata commutation monoid. Introduction to the group algebra of the symmetric group, enumerative applications of sl(2). [Offered: W] Prereq: CO 330; Cumulative overall average of at least 80%

 CO 434 LEC 0.50 Course ID: 003903 Combinatorial Designs 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. Prereq: PMATH 336 or 346 or 347; Cumulative overall average of at least 80%

 CO 439 LEC 0.50 Course ID: 003906 Topics in Combinatorics An undergraduate seminar in combinatorics. The primary objective is to study current work in specific areas of combinatorics. Course content may vary from term to term. Instructor Consent Required

 CO 440 LEC 0.50 Course ID: 003907 Topics in Graph Theory An in-depth study of one or two topics in graph theory. Course content may vary from term to term. Topics may include planar graphs, extremal graph theory, directed graphs, enumeration, algebraic graph theory, probabilistic graph theory, connectivity, graph embedding, colouring problems. Prereq: CO 342

 CO 442 LEC 0.50 Course ID: 003908 Graph Theory Connectivity (Menger's theorem, ear decomposition, and Tutte's wheels theorem) and matchings (Hall's theorem and Tutte's theorem). Flows: integer and group-valued flows, the flow polynomial, the 6-flow theorem. Ramsey theory: upper and lower bounds, explicit constructions. External graph theory: Turan's theorem, the Erdos-Gallai theorem. Probabilistic methods. [Offered: F] Prereq: CO 342, MATH 235 or 245; Cumulative overall average of at least 80%

 CO 444 LEC 0.50 Course ID: 003909 Algebraic Graph Theory An introduction to the methods of and some interesting current topics in algebraic graph theory. Topics covered will include vertex-transitive graphs, eigenvalue methods, strongly regular graphs and may include graph homomorphisms, Laplacians or knot and link invariants. Prereq: MATH 239 or 249, PMATH 336 or 346 or 347; Cumulative overall average of at least 80%

 CO 446 LEC 0.50 Course ID: 013337 Matroid Theory 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 paths, disjoint spanning trees, the 8-flow theorem for graphs, planarity testing, and recognizing totally unimodular matrices. [Offered: S] Prereq: CO 342; Cumulative overall average of at least 80%

 CO 450 LEC 0.50 Course ID: 003910 Combinatorial Optimization Characterizations of optimal solutions and efficient algorithms for optimization problems over discrete structures. Topics include network flows, optimal matchings, T-joins and postman tours, matroid optimization. [Offered: F] Prereq: CO 351 or 255/355; Cumulative overall average of at least 80%

 CO 452 LEC 0.50 Course ID: 003911 Integer Programming 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. Prereq: CO 351 or 255/355; Cumulative overall average of at least 80%

 CO 453 LEC 0.50 Course ID: 003912 Network Design Network design under constraints on cost, capacity, distance, and reliability. Approximation algorithms. The set covering problem. Tree solutions: spanning trees, Steiner trees, Gomory-Hu trees, optimum communication spanning trees. Connectivity, survivability, and reliability. Network design with concentrators: the terminal layout problem. Location problems on networks. Prereq: MATH 229 or 239 or 249 and (one of CO 227, 250/350, 255/355, CO 352)

 CO 454 LEC 0.50 Course ID: 003913 Scheduling An overview of practical optimization problems that can be posed as scheduling problems. Characterizations of optimal schedules. Simple and efficient combinatorial algorithms for easy problems. A brief overview of computational complexity, definition of P, NP, NP-complete and NP-hard. Integer programming formulations, the traveling salesman problem, heuristics, dynamic programming, and branch-and-bound approaches. Polynomial-time approximation algorithms. [Offered: S] Prereq: MATH 229 or 239 or 249 and (one of CO 227, 250/350, 255/355, CO 352)

 CO 456 LEC 0.50 Course ID: 003914 Introduction to Game Theory A broad introduction to game theory and its applications to the modeling of competition and cooperation in business, economics, and society. Two-person games in strategic form and Nash equilibria. Extensive form games, including multi-stage games. Coalition games and the core. Bayesian games, mechanism design, and auctions. Prereq: MATH 229 or 239 or 249 and (one of CO 227, 250/350, 255/355, CO 352)

 CO 459 SEM 0.50 Course ID: 010046 Topics in Optimization An undergraduate seminar in optimization. The primary objective is to study recent work in specific areas of optimization. Course content may vary from term to term. Instructor Consent Required

 CO 463 LEC 0.50 Course ID: 010047 Convex Optimization and Analysis 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. [Offered: W] Prereq: (CO 255/355 or 367), (AMATH/PMATH 331 or PMATH 351); Cumulative overall average of at least 80%

 CO 466 LEC 0.50 Course ID: 003917 Continuous Optimization 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. Prereq: (CO 367 and one of CO 250/350, 352) or CO 255/355; Cumulative overall average of at least 80%

 CO 471 LEC 0.50 Course ID: 011364 Semidefinite Optimization Optimization over convex sets described as the intersection 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. Prereq: MATH 239 or 249, AMATH/PMATH 331 or PMATH 351, CO 255/355; Cumulative overall average of at least 80%

 CO 480 LEC 0.50 Course ID: 003918 History of Mathematics An in-depth examination of the origins of mathematics, beginning with examples of Babylonian mathematics. Topics may include Pythagorean triples, solution of equations, estimation of pi, duplication of the cube, trisection of an angle, the Fibonacci sequence, the origins of calculus. [Note: Offered in the spring term of odd years.] Prereq: MATH 135 or 145, MATH 106 or 136 or 146, MATH 138 or 148; Level at least 3A

 CO 481 LEC,TST 0.50 Course ID: 011497 Introduction to Quantum Information Processing Basics of computational complexity; basics of quantum information; quantum phenomena; quantum circuits and universality; relationship between quantum and classical complexity classes; simple quantum algorithms; quantum Fourier transform; Shor factoring algorithm; Grover search algorithm; physical realization of quantum computation; error-correction and fault-tolerance; quantum key distribution. [Offered: W] Prereq: One of MATH 114, 115, 235, 245; Level at least 4A (Cross-listed with CS 467, PHYS 467)

 CO 485 LEC 0.50 Course ID: 010137 The Mathematics of Public-Key Cryptography An in-depth study of public-key cryptography. Number-theoretic problems: prime generation, integer factorization, discrete logarithms. Public-key encryption, digital signatures, key establishment, secret sharing. Proofs of security. [Offered: F] Prereq: One of PMATH 334, 336, 345, 346, 347; Cumulative overall average of at least 80%

 CO 487 LEC 0.50 Course ID: 010136 Applied Cryptography A broad introduction to cryptography, highlighting the major developments of the past twenty years. Symmetric ciphers, hash functions and data integrity, public-key encryption and digital signatures, key establishment, key management. Applications to Internet security, computer security, communications security, and electronic commerce. [Offered: W] Prereq: MATH 135 or 145, STAT 206 or 220 or 230 or 240; Level at least 3A

 CO 499 RDG 0.50 Course ID: 003920 Reading in Combinatorics and Optimization Reading course as announced by the department. Department Consent Required