Course Descriptions - Undergraduate Calendar 2009-2010

University of Waterloo Home Page | Undergraduate Calendar | Course Description Index | Contact Us | Privacy
University of Waterloo
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

Note

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.50Course 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/125, 114, 115, 136, 146.
Antireq: CO 350, CO 352/CM 340, CO 355

CO 252 LEC,TST 0.50Course ID: 011753
Linear and Nonlinear Optimization: Algorithms, Models and Applications
Linear programming and the Simplex algorithm. Duality. Introduction to continuous optimization in real n-space for large n. Nonlinear Optimization and Lagrange multipliers. Modelling and applications. [Offered: S]
Prereq: MATH 136 or 146, 138 or 148; BCS students only.
Antireq: CO 227, 350, CO 352/CM 340, CO 353/CM 441, CO 370/CM 443

CO 300s


CO 327 LEC 0.50Course 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, 350, CO 352/CM 340, CO 355.
Antireq: CO 370

CO 330 LEC 0.50Course 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; Not open to General Mathematics students

CO 331 LEC 0.50Course 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 235 or 245; Not open to General Mathematics students

CO 342 LEC 0.50Course ID: 003893
Introduction to Graph Theory
An introduction to some of the key parts of graph theory: connectivity, planarity and matchings. Connectivity: Menger's Theorem, 3-connected graphs and contractible edges, Kuratowski's Theorem, uniqueness of planar embeddings. Planarity, cycle and co-cycle spaces: peripheral cycles and the cycle space of a 3-connected graph. Matchings: Review of Konig's Theorem, Tutte's Theorem. [Offered: F,S]
Prereq: MATH 239 or 249; Not open to General Mathematics students

CO 350 LEC 0.50Course ID: 003895
Linear Optimization
A first course in optimization, emphasizing optimization of linear functions subject to linear constraints (linear programming). Problem formulation. Duality theory. The simplex method. Sensitivity analysis.
[Note: Offered at St. Jerome's University in the Fall term. CO 355 may be substituted for CO 350 whenever the latter is a requirement in an Honours plan. Offered: F,W,S]
Prereq: MATH 115 or 136 or 146; Not open to General Mathematics students.
Antireq: CO 227, CO 352/CM 340, CO 355
Also offered at St. Jerome's University

CO 351 LEC 0.50Course 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,W,S]
Prereq: CO 350 or CO 352/CM 340 or CO 355, MATH 239; Not open to General Mathematics students

CO 352 LAB,LEC 0.50Course ID: 011440
Computational Optimization
A first course in computational optimization. Linear optimization, the simplex method, implementation issues, duality theory. Introduction to computational discrete and continuous optimization. [Offered: F,S]
Prereq: AMATH 341/CM 271/CS 371 and MATH 239 or 249; Not open to General Mathematics students.
Antireq: CO 350
(Cross-listed with CM 340)

CO 353 LAB,LEC 0.50Course 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. [Offered: F]
Prereq: (CO 350 and MATH 239 or 249) or CO 352/CM 340; Not open to General Mathematics students
(Cross-listed with CM 441)

CO 355 LEC 0.50Course ID: 003897
Mathematical Optimization
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 355 may be substituted for CO 350 whenever the latter is a requirement in an Honours plan. Offered: F]
Prereq: MATH 235 or 245, 237 or 247; Not open to General Mathematics students

CO 367 LAB,LEC 0.50Course 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.
[Note: MATH 237/247 is recommended. Offered: W]
Prereq: (CO 350 and MATH 138 or 148) or CO 352/CM 340 or CO 355; Not open to General Mathematics students
(Cross-listed with CM 442)

CO 370 LAB,LEC 0.50Course 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 350 or CO 352/CM 340 or CO 355; Not open to General Mathematics students
(Cross-listed with CM 443)

CO 372 LAB,LEC 0.50Course ID: 011736
Portfolio Optimization Models
Applications of basic optimization models and techniques for decision making in financial markets. Quadratic optimization subject to linear equality constraints. Derivation of efficient portfolios and the Markowitz efficient frontier. The Capital Market Line. Practical portfolio optimization as a quadratic programming problem. A solution algorithm for quadratic programming problems. [Offered: W]
Prereq: (AFM 272/ACTSC 291 or ACTSC 371 or BUS 393W or ECON 371) and (CO 350 or CO 352/CM 340 or CO 355); Not open to General Mathematics students.
Antireq: CO 370 taken prior to Winter 2004

CO 380 LEC 0.50Course 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, 136 or 146, 138 or 148; Level at least 3A; Not open to General Mathematics students

CO 400s


CO 430 LEC 0.50Course 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: F]
Prereq: CO 330; Cumulative overall average of at least 80%; Not open to General Mathematics students

CO 434 LEC 0.50Course 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; Cumulative overall average of at least 80%; Not open to General Mathematics students

CO 439 LEC 0.50Course 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
Prereq: Not open to General Mathematics students

CO 440 LEC 0.50Course 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; Not open to General Mathematics students

CO 442 LEC 0.50Course ID: 003908
Graph Theory
An in-depth look at the following major topics in graph theory; other topics may also be included: Colouring: Brooks', Vizing's and Grotzsch's Theorems, list colouring. Eigenvalues of adjacency matrices: Moore graphs. Directed graphs: tournaments, kernels, disjoint branchings, Lucchesi-Younger Theorem. [Offered: F]
Prereq: CO 342, MATH 235 or 245; Cumulative overall average of at least 80%; Not open to General Mathematics students

CO 444 LEC 0.50Course 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; Cumulative overall average of at least 80%; Not open to General Mathematics students

CO 450 LEC 0.50Course 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 355; Cumulative overall average of at least 80%; Not open to General Mathematics students

CO 452 LEC 0.50Course 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 355; Cumulative overall average of at least 80%; Not open to General Mathematics students

CO 453 LEC 0.50Course 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 239 or 249 and either CO 350 or CO 352/CM 340) or CO 355; Not open to General Mathematics students

CO 454 LEC 0.50Course 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 239 or 249 and either CO 350 or CO 352/CM 340) or CO 355; Not open to General Mathematics students

CO 456 LEC 0.50Course 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 239 or 249 and either CO 350 or CO 352/CM 340) or CO 355; Not open to General Mathematics students

CO 459 SEM 0.50Course 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
Prereq: Not open to General Mathematics students

CO 463 LEC 0.50Course 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, set-valued analysis, subgradient calculus for convex functions, Fenchel conjugacy and duality. Lagrange multipliers, minimax theory. Algorithms for nondifferentiable optimization. Lipschitz functions, tangent cones and generalized derivatives, introductory non-smooth analysis and optimization.
Prereq: (CO 355 or 367/CM 442), (AMATH/PMATH 331 or PMATH 351); Cumulative overall average of at least 80%; Not open to General Mathematics students

CO 466 LEC 0.50Course ID: 003917
Continuous Optimization
Theory and practical algorithms for nonlinear continuous optimization. Fundamentals of unconstrained optimization: conjugate gradient methods and Newton-type methods. Nonlinear least squares problems. Fundamentals of constrained optimization: optimality conditions, quadratic programming, penalty and barrier methods, interior-point methods, sequential quadratic programming. [Offered: W]
Prereq: (CO 367/CM 442 and either CO 350 or CO 352/CM 340) or CO 355; Cumulative overall average of at least 80%; Not open to General Mathematics students

CO 471 LEC 0.50Course 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 355; Cumulative overall average of at least 80%; Not open to General Mathematics students

CO 480 LEC 0.50Course 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, 136 or 146, 138 or 148; Level at least 3A; Not open to General Mathematics students

CO 481 LEC 0.50Course 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.
Prereq: One of MATH 114, 115, 235, 245; Level at least 4A; Not open to General Mathematics students
(Cross-listed with CS 467, PHYS 467)

CO 485 LEC 0.50Course 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; Cumulative overall average of at least 80%; Not open to General Mathematics students

CO 487 LEC 0.50Course 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 230 or 240; Level at least 3A; Not open to General Mathematics students
(Cross-listed with CM 432)

CO 499 LEC 0.50Course ID: 003920
Reading in Combinatorics and Optimization
[Offered: F,W,S]
Department Consent Required
Prereq: Not open to General Mathematics students