[How to read the course descriptions]

*
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