30 courses in the 1994–95 Undergraduate Calendar, read from the scanned original. The text comes from OCR, so check the scanned page before relying on a detail.
Undergraduate Officer W.H. Cunningham, MC 5033A, ext 4627 email: [email protected]
Introductory Note
More detailed course descriptions and course outlines are available in the C&O Undergraduate Handbook.
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
Elementary principles of enumeration. Principle of inclusion-exclusion, generating functions, recurrence equations. Elementary graph theory and graphical algorithms. Introduction to design theory. Antireg: C&O 230 C&O 220 cannot be counted for credit toward a BMath Honours degree.
Structure and classification of optimization problems. The concepts of algorithm and heuristic. Continuous models. Linear models. Branch-and-bound, dynamic programming, impiicit enumeration and approximation. Applications of optimization models. Prereq: MATH 108, 125 or equivalent Antireg: C&O 350 C&O 227 cannot be counted for credit toward a BMath Honours degree.
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
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
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.
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
A first course in problem formulation and solution techniques in linear programming. The simplex and revised simplex methods. Active set formulation of the simplex method. 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.
Also offered at St. Jerome's College in the Fall term
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 Also offered at St. Jerome's College in the Winter term
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.
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
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
Antireq: ACTSC 335
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 thirdyear standing
The Lagrange implicit function theorem.
hypergeometric series, and the ring of for-
mal 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
Pairwise orthogonal latin squares.
Transversal designs and finite planes.
Balanced incomplete biock designs, group
divisible designs and pairwise balanced
designs. Symmetric designs and
Hadamard matrices. Recursive construc-
tions. Wilson's fundamental construction. Prereq: PMATH 336
Course Descriptions Combinatorics and Optimization
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.
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.
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
An in-depth study of one or two topics in graph theory. Course content may vary from term to term. Topics may include pianar 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
Theorem, Four-Coiour problem. Colourings: Critical Graphs, Five-Colour Theorem, Vizing’s Theorem, Snarks. Flows: Eight-Flow Theorem, Six-Fiow Theorem, Tutte’s Conjectures. Embeddings: Genus, 2-cell Embeddings, Map-Colour Theorem. Coverings: Double Cover Conjecture.
Prereq: C&O 342 or consent of instructor
16:33
Automorphisms. Cayley graphs and their properties. Arc and distance transitive graphs. Generalised polygons. Homomorphisms and covers. Adjacency and incidence matrices. Eigenvectors of graphs. Quotients. Interiacing. Strongly regular graphs. Line graphs and graphs with least eigenvalue -2. Expanders. Shannon capacity.
Prereq: C&O 230, PMATH 336
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
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 365
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. C&O 351 is recommended.
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. C&O 351 or 370 is recommended.
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
An introduction to the modem 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 non differentiable 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
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
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 angie, the Fibonacci sequence, the origins of calculus.
Prereq: MATH 135, 136, 138 and thirdyear standing
Prereq: Consent of department
Course Descriptions Combinatorics and Optimization