Undergraduate Calendar 2002-2003

University of Waterloo
UW  HOME
CALENDAR  CONTENTS
UNDERGRADUATE COURSE DESCRIPTIONS  INDEX
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 

Notes

  1. More detailed course descriptions and course outlines are available on the CO Undergraduate Homepage.
  2. 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.

UW  HOME
CALENDAR  CONTENTS
UNDERGRADUATE COURSE DESCRIPTIONS  INDEX

The Undergraduate Calendar is published by the
Office of the Registrar, University of Waterloo, Waterloo, ON N2L 3G1 Canada
Inquiries: infoucal@www.adm.uwaterloo.ca
Revised April 2002

CO 100s


CO 103 LEC,TUT 0.50Course ID: 009889
Discrete Mathematics for Engineers
Propositional and predicate logic. Sets, functions and sequences. Elementary number theory. Mathematical reasoning. Combinatorics. Boolean algebra. Graphs and trees. Models of computation.
[Note: Offered: W]
Prereq: 1B Computer Engineering or Software Engineering/1B or higher Electrical Engineering/Computer Engineering Option.
Antireq: CO 220, 230, ECE 203, MATH 239/249
(Cross-listed with ECE 103)

CO 200s


CO 220 LEC 0.50Course ID: 003886
Introductory Combinatorics
Elementary principles of enumeration. Principle of inclusion- exclusion, generating functions, recurrence equations. Elementary graph theory and graphical algorithms. Introduction to design theory. [Offered: W]
Prereq: Not open to Honours Mathematics students.
Antireq: MATH 239/249, CO 230
Also offered by Distance Education

CO 227 LEC 0.50Course ID: 003887
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. [Offered: F,W]
Prereq: One of MATH 115, 125, 136/146 and one of MATH 118, 119, 128, 138/148; Not open to Honours Mathematics students
Antireq: CO 350, 355
Also offered by Distance Education

CO 300s


CO 327 LEC 0.50Course ID: 003890
Optimization II
Linear programming: Applications, geometry, basic solutions, the simplex method. Integer programming: Applications, branch and bound, cutting planes. Network optimization: Minimum-cost flows, maximum flows, applications.
Prereq: CO 227; Not open to Honours Mathematics students.
Antireq: CO 350

CO 330 LEC 0.50Course ID: 003891
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. [Offered: F]
Prereq: MATH 239/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/245; Not open to General Mathematics students

CO 339 LAB,LEC 0.50Course ID: 011439
Computational Discrete Mathematics
Models of computation. An overview of complexity: P, NP, and NP-complete problems. Introduction to the analysis of algorithms through development of number-theoretic algorithms. Computation over rings and finite fields. Graph-theoretic algorithms and applications, including search, planarity testing, and shortest-path problems.
[Note: Lab is not scheduled and students are expected to find time in open hours to complete their work. Offered: W,S]
Prereq: MATH 239 and (CS 234 or 240); Not open to General Mathematics students.
Antireq: CS 341
(Cross-listed with CM 339, CS 339)

CO 342 LEC 0.50Course ID: 003893
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. [Offered: F,S]
Prereq: MATH 239/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. Offered: F,W,S]
Prereq: MATH 136/146; Not open to General Mathematics students.
Antireq: CO 227, 327, ACTSC 335
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 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. [Offered: F,W,S]
Prereq: CO 350 or 355; Not open to General Mathematics students

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. [Offered: F]
Prereq: MATH 235/245, 237/247; Not open to General Mathematics students

CO 367 LEC 0.50Course ID: 003898
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.
[Note: MATH 237/247 is recommended. Offered: W]
Prereq: MATH 138/148, 235/245

CO 370 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 355.
Antireq: ACTSC 335

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 spring term, even-numbered years.]
Prereq: MATH 135/145, 136/146, 138/148; Level at least 3A; Not open to General Mathematics students

CO 400s


CO 430 LEC 0.50Course ID: 003902
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. [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; 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
Colourings: Brooks' Theorem, Vizing's theorem, list colourings. Ramsey Theory: Ramsey's Theorem, Ramsey numbers and bounds, constructive Ramsey theory. Extremal Graph Theory: Forbidden subgraph problems, Turan's Theorem. Graph Minors: Embeddings, well-quasi-orderings, tree width. [Offered: F]
Prereq: CO 342; Cumulative overall average of at least 80%; Not open to General Mathematics students

CO 444 LEC 0.50Course ID: 003909
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: MATH 239/249, PMATH 336; 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. 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. [Offered: F]
Prereq: CO 351 or CO 355 or (CO 350 and MATH 239/249); Not open to General Mathemetics students

CO 454 LEC 0.50Course ID: 003913
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. [Offered: S]
Prereq: CO 351 or CO 355 or (CO 350 and MATH 239/249); Not open to General Mathemetics 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 335 or 367 and AMATH/PMATH 331; Cumulative overall average of at least 80%; Not open to General Mathematics students

CO 466 LEC 0.50Course ID: 003917
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. [Offered: W]
Prereq: CO 355 or 350, 367; 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/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 spring term, odd-numbered years.]
Prereq: MATH 135/145, 136/146, 138/148; Level at least 3A; Not open to General Mathematics students

CO 481 LEC 0.50Course ID: 011497
Introduction to Quantum Information Processing
Quantum superposition, interference, and entanglement. Postulates of quantum mechanics. Quantum computational complexity. Quantum algorithms. Quantum communication and cryptography. Quantum error correction. Implementations.
Prereq: MATH 235/245 or (PHYS 364 and 365); Level at least 4A
(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: PMATH 334; 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/145, STAT 230/240; Level at least 3A; Not open to General Mathematics students.
Antireq: CO 437

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

UW  HOME
CALENDAR  CONTENTS
UNDERGRADUATE COURSE DESCRIPTIONS  INDEX

The Undergraduate Calendar is published by the
Office of the Registrar, University of Waterloo, Waterloo, ON N2L 3G1 Canada
Inquiries: infoucal@www.adm.uwaterloo.ca
Revised April 2002