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&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&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&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