[AHS] [Arts] [Eng] [ES] [IS] [Math] [Sci] [Inter] [Calendar Top] [UW Home]
[How to read the course descriptions]

Combinatorics and Optimization



Undergraduate Officer
A.S. Lewis, MC 6054, ext. 6983
e-mail: aslewis@orion.uwaterloo.ca

Note: More detailed course descriptions and course outlines are available in the C&O Undergraduate Handbook.

C&O200S

C&O 203 S 3C,1T 0.5
Discrete Mathematics (for Engineers)
Propositional and predicate logic. Sets, functions and sequences. Mathematical reasoning. Combinatorics. Relations. Graphs and trees. Models of computation.
Prereq: E&CE 223, E&CE 250
Antireq: C&O 220
Cross-listed as E&CE 203
Not open to students in the Faculty of Mathematics

C&O 220 W 3C 0.5
Introductory Combinatorics
Elementary principles of enumeration. Principle of inclusion- exclusion, generating functions, recurrence equations. Elementary graph theory and graphical algorithms. Introduction to design theory.
Antireq: C&O 230
C&O 220 cannot be counted for credit toward a BMath Honours degree.

C&O 227 F 3C 0.5
Introduction to Optimization Models
Structure and classification of optimization problems. The concepts of algorithm and heuristic. Continuous models. Linear models. Branch-and-bound, dynamic programming, implicit enumeration and approximation. Applications of optimization models.
Prereq: MATH 108, 125 or equivalent
Antireq: C&O 350, 355
C&O 227 cannot be counted for credit toward a BMath Honours degree.

C&O 230 F,W,S 3C 0.5
Introduction to Combinatorics
Introduction to the combinatorics of ordinary generating functions. Introduction to basic graph theory and graphical algorithms.
Prereq: MATH 136, 138
Antireq: C&O 220
Also offered at St. Jerome's College in the Fall term

C&O300S

C&O 330 F 3C 0.5
Combinatorial Enumeration
The combinatorics of the ordinary and exponential generating functions. Matrix methods, and decompositions. Applications to the enumeration of sequences, permutations, trees, lattice paths and partitions.
Prereq: C&O 230

C&O 331 W 3C 0.5
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.
Prereq: PMATH 336
Offered at St. Jerome's College in the Winter term

C&O 342 F,S 3C 0.5
Introduction to Graph Theory
An introduction to the ideas, methods and applications of graph theory. Finding shortest paths and maximum matchings in weighted graphs. Determining the connectivity of a graph.
Prereq: C&O 230

C&O 350 F,W,S 3C 0.5
Linear Programming
A first course in problem formulation and solution techniques in linear programming. The simplex and revised simplex methods. Theory and applications of duality theory. Sensitivity Analysis.
Prereq: MATH 225 or 235
Antireq: C&O 227, 355, ACTSC 335
C&O 355 may be substituted for C&O 350 in any degree program, or for prerequisite purposes.

C&O 351 W,S 3C 0.5
Network Flow Theory
Review of linear programming. Shortest path problems. The max- flow and minimum cost flow problems. Network simplex, augmentation and out-of-kilter algorithms. Applications to problems of transportation, distribution, job assignments and critical-path planning.
Prereq: C&O 350 or 355

C&O 355 F 3C 0.5
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.
Prereq: MATH 235, 237
Antireq: C&O 350, ACTSC 335
C&O 355 may be substituted for C&O 350 in any degree program, or for prerequisite purposes.

C&O 367 F,W 3C 0.5
Nonlinear Optimization
A first course in the mathematics of nonlinear optimization. Necessary and sufficient optimality conditions for unconstrained and constrained problems. Convexity and its applications. Computational techniques and their analysis.
Prereq: MATH 235, 237

C&O 370 F,W 3C 0.5
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.
Prereq: C&O 350 or 355
Antireq: ACTSC 335

C&O 380 W,S 3C 0.5
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.
Prereq: MATH 135, 136, 138 and third-year standing

C&O400S

C&O 430 W 3C 0.5
Algebraic Enumeration
The Lagrange implicit function theorem, hypergeometric series, and the ring of formal Laurent series. The combinatorics of Eulerian generating series, enumeration under the action of a group, the algebra of symmetric functions, the group algebra of the symmetric group, with applications.
Prereq: C&O 330

C&O 434 F 3C 0.5
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

C&O 437 W 3C 0.5
Cryptography and Communications Security
Conventional or single key cryptography from the Caesar cipher to the U.S. Data Encryption Standard. Public or two key cryptography. Applications include secrecy/ privacy, user or message authentication, financial transactions security.
Prereq: STAT 230. At least one of C&O 331 and PMATH 340 is recommended.

C&O 438 F 3C 0.5
Combinatorial Computing
Applications of computers to combinatorial problems. General procedures - backtrack programming, generation of permutations, partitions, etc., as well as the solution of many specific problems. Includes an introduction to computational complexity.
Prereq: C&O 230. Some programming experience is required.

C&O 439 3C 0.5
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.
Prereq: Consent of instructor

C&O 440 F 3C 0.5
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: C&O 342 or consent of instructor

C&O 442 F 3C 0.5
Graph Theory
Planar Graphs: Duality, Kuratowski's Theorem, Four-Colour problem. Colourings: Critical Graphs, Five-Colour Theorem, Vizing's Theorem, Snarks. Flows: Eight-Flow Theorem, Six-Flow Theorem, Tutte's Conjectures. Embeddings: Genus, 2-cell Embeddings, Map-Colour Theorem. Coverings: Double Cover Conjecture.
Prereq: C&O 342 or consent of instructor

C&O 444 W 3C 0.5
Algebraic Graph Theory
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.
Prereq: C&O 230, PMATH 336

C&O 450 F 3C 0.5
Combinatorial Optimization
Packing, covering and partitioning problems. Integer programming. Good algorithms for optimum assignments, matchings, flows, anti-chains and connectivity. Paths, trees and flowers. Min-max relations. Convexification of discrete problems. Vertices and facets of convex polyhedra. The concepts of NP and co-NP. Reducing NP problems to integer programming.
Prereq: C&O 351 or 355

C&O 452 W 3C 0.5
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: C&O 351 or 355

C&O 453 F 3C 0.5
Network Design
Network design under constraints on cost, capacity, distance and reliability. Tree solutions: spanning trees, Steiner trees, optimum communication spanning trees. Connectivity, survivability and reliability. Network design with concentrators: the terminal layout problem. Geometric network design: the plane and the sphere. Location problems on networks. Algorithmic aspects.
Prereq: C&O 350 or 355. C&O 351 is recommended.

C&O 454 S 3C 0.5
Scheduling
Sequencing algorithms for scheduling tasks on single machines, parallel machines, and flow shops. Applications to scheduling computers and manufacturing facilities. Combinatorial techniques used in algorithm development and convergence proofs.
Prereq: C&O 350 or 355. C&O 351 or 370 is recommended.

C&O 459 3C 0.5
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.
Prereq: Consent of instructor

C&O 463 F 3C 0.5
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: C&O 355 or 367, and AM/PMATH 331 or consent of instructor

C&O 466 W 3C 0.5
Continuous Optimization
Geometry and numerical algorithms of nonlinear optimization. Variable metric and conjugate gradient methods. Convex programming. Feasible and nonfeasible direction methods. Recursive quadratic programming, nonorthogonal projections and active set strategies.
Prereq: C&O 355, or 350 and 367

C&O 480 F 3C 0.5
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.
Prereq: MATH 135, 136, 138 and third-year standing

C&O 499 F,W,S 2R 0.5
Reading in Combinatorics and Optimization

Prereq: Consent of department

[AHS] [Arts] [Eng] [ES] [IS] [Math] [Sci] [Inter] [Calendar Top] [UW Home]


Infoucal@www.adm.uwaterloo.ca / University of Waterloo