uwloo Timetable

Combinatorics and Optimization (CO)

36 courses in the 2023–24 Undergraduate Calendar. Original: ucalendar.uwaterloo.ca/2324/COURSE/course-CO.html

CO 227 Introduction to Optimization (Non-Specialist Level)0.50 units

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, 255, 352

LEC · Course ID 003887On ucalendarCO 227 today

CO 250 Introduction to Optimization0.50 units

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, MATH 114, MATH 115 with a grade of at least 70%) or MATH 136 or MATH 146; cumulative overall average of at least 60%.

Antireq: CO 227, 255

Also offered Online

LEC, TST, TUT · Course ID 003895On ucalendarCO 250 today

CO 255 Introduction to Optimization (Advanced Level)0.50 units

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 whenever the latter is a requirement in an Honours plan. Offered: W]

Prereq: MATH 235 or 245, 237 or 247.

Antireq: CO 227, 250, 352

LEC · Course ID 003897On ucalendarCO 255 today

CO 327 Deterministic OR Models (Non-Specialist Level)0.50 units

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, 255, 352.

Antireq: CO 370

LEC · Course ID 003890On ucalendarCO 327 today

CO 330 Combinatorial Enumeration0.50 units

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

LEC · Course ID 003891On ucalendarCO 330 today

CO 331 Coding Theory0.50 units

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

Only offered Online

LEC · Course ID 003892On ucalendarCO 331 today

CO 342 Introduction to Graph Theory0.50 units

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

LEC · Course ID 003893On ucalendarCO 342 today

CO 351 Network Flow Theory0.50 units

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 or 255 or 352

LEC · Course ID 003896On ucalendarCO 351 today

CO 353 Computational Discrete Optimization0.50 units

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 or 255 or 352

LAB, LEC · Course ID 011442On ucalendarCO 353 today

CO 367 Nonlinear Optimization0.50 units

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, 255, 352) and MATH 128 with a grade of at least 70% or MATH 138 or 148

LAB, LEC · Course ID 003898On ucalendarCO 367 today

CO 370 Deterministic OR Models0.50 units

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 or 255 or 352.

Antireq: CO 327

LAB, LEC · Course ID 003899On ucalendarCO 370 today

CO 372 Portfolio Optimization Models0.50 units

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: One of AFM 272/ACTSC 291, ACTSC 371, ACTSC 372, BUS 393W, ECON 371; CO 227 with a grade of at least 70% or One of CO 250, CO 255, CO 352.

Antireq: CO 370 taken prior to winter 2004

LAB, LEC · Course ID 011736On ucalendarCO 372 today

CO 380 Mathematical Discovery and Invention0.50 units

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

LEC · Course ID 003901On ucalendarCO 380 today

CO 430 Algebraic Enumeration0.50 units

The Lagrange Implicit Function Theorem, the MacMahon Master Theorem. Enumeration of planar triangulations. The transfer matrix method. Sieve methods, inclusion/exclusion, Mobius inversion. Polya enumeration, Enumeration of trees. Basic hypergeometric series, q-analogues, Rogers-Ramanujan identities. Asymptotic methods.

Prereq: CO 330; Cumulative overall average of at least 80%

LEC · Course ID 003902On ucalendarCO 430 today

CO 431 Symmetric Functions0.50 units

The ring of symmetric functions, standard bases, the Hall inner product. Young tableaux. The Robinson-Schensted-Knuth correspondence, the hook-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.

Prereq: PMATH 336 or PMATH 347; Cumulative overall average of at least 80%

LEC · Course ID 016410On ucalendarCO 431 today

CO 432 Information Theory and Applications0.50 units

Basics of information theory; Shannon entropy, KL divergence, and mutual information; basic properties of entropic quantities; chain rule, Pinsker's Inequality, Data Processing Inequality; compression; Channel Coding Theorem; error-correction; applications to combinatorics, optimization, cryptography, and computer science.

Prereq: MATH 239 or 249; CO 250 or 255; STAT 230 or 240; Level at least 3A

LEC · Course ID 016487On ucalendarCO 432 today

CO 434 Combinatorial Designs0.50 units

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%

LEC · Course ID 003903On ucalendarCO 434 today

CO 439 Topics in Combinatorics0.50 units

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

LEC · Course ID 003906On ucalendarCO 439 today

CO 440 Topics in Graph Theory0.50 units

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

LEC · Course ID 003907On ucalendarCO 440 today

CO 442 Graph Theory0.50 units

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%

LEC · Course ID 003908On ucalendarCO 442 today

CO 444 Algebraic Graph Theory0.50 units

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%

LEC · Course ID 003909On ucalendarCO 444 today

CO 446 Matroid Theory0.50 units

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%

LEC · Course ID 013337On ucalendarCO 446 today

CO 450 Combinatorial Optimization0.50 units

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 255 or 351; Cumulative overall average of at least 80%

LEC · Course ID 003910On ucalendarCO 450 today

CO 452 Integer Programming0.50 units

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 255 or 351; Cumulative overall average of at least 80%

LEC · Course ID 003911On ucalendarCO 452 today

CO 454 Scheduling0.50 units

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, 255, 352)

LEC · Course ID 003913On ucalendarCO 454 today

CO 456 Introduction to Game Theory0.50 units

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, 255, 352)

LEC · Course ID 003914On ucalendarCO 456 today

CO 459 Topics in Optimization0.50 units

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

SEM · Course ID 010046On ucalendarCO 459 today

CO 463 Convex Optimization and Analysis0.50 units

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 or 367), (AMATH/PMATH 331 or PMATH 351); Cumulative overall average of at least 80%

LEC · Course ID 010047On ucalendarCO 463 today

CO 466 Continuous Optimization0.50 units

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, 352) or CO 255; Cumulative overall average of at least 80%

LEC · Course ID 003917On ucalendarCO 466 today

CO 471 Semidefinite Optimization0.50 units

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. [Offered: S]

Prereq: MATH 239 or 249, AMATH/PMATH 331 or PMATH 351, CO 255 or 367; Cumulative overall average of at least 80%

LEC · Course ID 011364On ucalendarCO 471 today

CO 480 History of Mathematics0.50 units

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: One of ECE 108, MATH 135, or MATH 145; One of MATH 106, 114, 115, 136 or 146; MATH 118, 119, 128, 138, or 148; Level at least 3A

LEC · Course ID 003918On ucalendarCO 480 today

CO 481 Introduction to Quantum Information Processing0.50 units

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.

Prereq: MATH 235 or 245 with grade at least 80%; Level at least 3A

(Cross-listed with CS 467, PHYS 467)

LEC, TST · Course ID 011497On ucalendarCO 481 today

CO 485 The Mathematics of Public-Key Cryptography0.50 units

An in-depth study of public-key cryptography. Number-theoretic problems: prime generation, integer factorization, discrete logarithms. Public-key encryption, digital signatures, key establishment, elliptic curve cryptography, post-quantum cryptography. Proofs of security. [Offered: F]

Prereq: One of PMATH 334, 336, 345, 346, 347; Cumulative overall average of at least 80%

LEC · Course ID 010137On ucalendarCO 485 today

CO 486 Topics in Quantum Information0.50 units

The primary objective is to study current work in specific areas of quantum information. Course content may vary from term to term.

Instructor Consent Required

LEC · Course ID 016488On ucalendarCO 486 today

CO 487 Applied Cryptography0.50 units

A broad introduction to modern cryptography, highlighting the tools and techniques used to secure internet and messaging applications. Symmetric-key encryption, hash functions, message authentication, authenticated encryption, public-key encryption and digital signatures, key establishment, key management. [Offered: F,W]

Prereq: One of CS 116, 136, 138, 146; MATH 135 or 145; One of STAT 206, 220, 230, 240; Level at least 3A

LEC · Course ID 010136On ucalendarCO 487 today

CO 499 Reading in Combinatorics and Optimization0.50 units

Reading course as announced by the department.

Department Consent Required

RDG · Course ID 003920On ucalendarCO 499 today