41 courses in the 1980–81 Undergraduate Calendar, read from the scanned original. The text comes from OCR, so check the scanned page before relying on a detail.
Department of Combinatorics and Optimization
Course Descriptions
Note
Course descriptions are given under the new course numbers introduced in 1979. The old numbers appear in brackets.
An introductory study of selected topics of fundamental importance in both combinatorics and optimization. The numerous applications of linear algebra principles make this course complementary to a formal course in linear algebra.
Prereq: Math 231a/b
N.B.: Credit will be granted for at most two of C&O 280, 282, 283.
Existence and non-existence. Enumeration. Combinations and Permutations. Inclusion-exclusion principle. Linear equations with unit coefficients. Recursion. Generating functions. Chromatic polynomials. Applications to geometry designs. Prereq: Math 124a/b
N.B.: Credit will be granted for at most two of C&O 280, 282, 283. Also offered at St. Jerome's College in Winter Term.
(C & O 239a)
An introduction to Optimization
Convex sets. Linear Programming. Directed graphs. Applications of Boolean Algebra to Combinatorial Circuits. Probability; Markov chains; random walks. Theory of Games.
Prereq: Math 124a/b
N.B.: Credit will be granted for at most two of C&O 280, 282, 283. Also offered at St. Jerome’s College in Fall Term.
C&O 331la F,W,S 3C 0.5 (C & O 352a) Linear Programming
Basic linear programming theory; review of relevant linear algebra, systems of linear inequalities, the simplex method, revised simplex method, pivot rules. Theory and applications of duality and complementary slackness. Sensitivity analysis. Prereq: Math 221a/b. ‘
Network programming, optimal paths, trees, transportation problems, k-th best policies. Applications to PERT, CPM, dynamic programming, equipment replacement, knapsack problems, optimal man-job assignments, warehousing problems. Prereq: C & O 331a.
Linear least squares. Properties of quadratic forms with applications to Newton's method and method of steepest descent. One dimensional optimization. Introduction to constrained optimization, including the elements of Kuhn-Tucker theory and Lagrange Multipliers.
Prereq: Math 220a/b.
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: Math 221a/b
Coreq: C & O 331a.
An applications oriented course complementary to C&O 340.
Prereq: C & O 340.
(C & O 353b)
Basic enumeration principles, emphasizing the combinatorial significance of generating functions. Topics to inciude the principle of inciusionexclusion, Polya theory, the Lagrange theorem, and vector spaces over finite fields. Applications to a variety of combinatorial problems.
Prereq: Math 231a/b
(C & O 360b)
Topics covered include orthogonal Latin squares, finite projective planes, balanced incomplete block designs, Hadamard matrices and Room squares. Prereq: Math 231a/b.
Graphs are basic mathematical structures which may be used, in a large variety of contexts, to model relationships between entities (routes between cities, friendship between people, and so on). Topics covered: basic definitions, trees, matchings, connectivity.
Prereq: Math 221a/b.
Course Descriptions 379 Combinatorics and Optimization
Cc & O 370b F,W 3C Introduction to Graph Theory 2 Topics covered inciude: planar graphs; vertex, edge and face colouring; Hamilton cycles.
Prereq: C & O 370a.
0.5 (C & O 351b)
Listed without a description.
Listed without a description.
A study of about 100 challenging problems taken from many areas of elementary mathematics - number theory, combinatorics, geometry, probability, logic.
Prereq: None
A study of about 100 challenging problems taken from many areas of elementary mathematics - number theory, combinatorics, geometry, probability, logic.
Prereq: None
Combinatorial aspects of the plane, such as, the number of regions into which the plane is divided by n lines; the number of two point lines formed from a set of n non-collinear points, etc. Properties of convex sets in the plane.
Prereq: Math 221a
N.B.: Offered at St. Jerome’s College.
(C & O 337a)
This course introduces the idea of a finite geometry and partial geometry. It shows the connection. between Latin squares, orthogonal arrays, finite geometries and block designs.
Prereq: C & O 386a
N.B.: Offered at St. Jerome’s College.
(C & O 337b)
C&O 0431a FS 2C 0.5 Network Flow Theory
Algorithms and theory relating to both combinatorics and optimization. Brief review of linear programming duality theory. Optimum paths and flows in networks. Efficiency of algorithms. Convex polyhedra. Combinatorial max-min relations. Totally unimodular matrices. Integer programming. Optimum matchings and constrained subgraphs.
Prereq: C & O 331a.
(C & O 437a)
Branchings in networks. Elementary matroid theory illustrated by forests, transversals, algebraic dependence, and geometry. Matroid partitions and intersections. Submodular functions and polymatroids.
Prereq: C & O 431a
(C & O 437b)
Variable metric and conjugate gradient methods for unconstrained optimization problems. Constrained optimization methods including convex programming and Rosen's gradient projection algorithms. Nonfeasible direction methods including penaity function techniques. Emphasis is on algorithms rather than abstract theory.
Prereq: C & O 332
(G & © 451b)
Review of duality theory, degeneracy, post-optimality analysis, revised simplex method. Generalized upper bounding. Integer and mixed-integer programming by cutting plane methods, branch-and-bound and implicit enumeration.
Prereq: C & O 331a
(C & O 452a)
Large scale systems. Numerically stable methods. Decomposition. Non-simplex techniques. Applications to large scale economic models, quadratic programming and statistical problems. Prereq: C & O 433a
(C & O 452b)
Integer programmes arising in practice. Modelling techniques. Methods of solution, including an introduction to Boolean methods. Problems with special structure.
Prereq: C & O 331a
(C & O 457a)
Game theory provides, through analysis of appropriate mathematical models, insight into the mechanics of competitive situations, such as those arising in social, economic, political or military conflict. Topics covered: matrix and bimatrix games, utility theory, bargaining problems.
Prereq: C & O 331a and Stat 220
(C & O 454a)
Listed without a description.
Review of relevant Calculus and Algebra. Formulation of the problem. Example problem models from Structural Engineering, Economics, Statistics and a quadratic energy model (viz. petroleum, coal, etc.). Optimality conditions for a quadratic programme. Quadratic duality theory; classic linear duality as a special case. Sensitivity analysis. Introduction to algorithms.
Prereq: C & O 331a
Algorithms. Conjugate directions, the basic projection algorithm for quadratic programming. The simplex method for linear programming as a special case. Numerically effective modifications of the projection method. Parametric cost and/or right-hand side algorithms.
The course is designed to be of particular interest to engineers, management scientists, economists, statisticians and operations researchers.
Prereq: C & O 443a
(C & © 450b)
Queueing models are analyzed, including, single channel queues of infinite and finite capacity; infinite and finite customer populations. Multi-server queues in series or parallel with homogeneous and heterogeneous servers. Models incorporating customer behaviour including balking, reneging and jockeying.
Prereq: Stat 220
(C & O 453a)
Elementary properties of Boolean algebras, Boolean and pseudo-Boolean equations and inequalities. Applications to enumeration theory, graph theory, logic, switching circuits and combinatorial networks. Boolean and pseudo-Boolean programming, integer programming. Formulation of operations research problems.
Prereq: Math 321a/b
(C& O 457b)
Algorithms for functions of completion or due times. Applications to quality control, organization of data files, machine shops. Precedence relations, parallel machines, implicit enumeration algorithms, generalized travelling salesman problem.
Prereq: C & O 331a or C & O 340
FW.S 2C,1T 05 (C & O 456a)
Topics complimentary to those of C & O 447a.- Prereq: C & O 447a and C & O 331b
(C & O 456b)
Deterministic decision process problems; monotonic path problems, equipment replacement, single and multi-dimensional resource allocation, reduction of dimension by use of Lagrange multipliers, optimal reliability, shortest path problems, cargo loading problems, the travelling salesman probiem, introduction to optimal control, an aggregate scheduling problem of inventory.
Prereq: C & O 331a
(C & O 455a)
The topics covered will vary from year to year depending upon the instructor and interests of the students.
Prereq: C & O 331a
(C & O 455b)
Cc & O 460 W 2C 0.5 Enumerative Mathematics Enumerative mathematics, combinatorial identities, generating functions, counting of labelled and unlabelled objects, theorems of Polya, Redfield- Read, and de Bruijn, permanents, combinatorial decompositions.
Prereq: C & O 360
(C & O 460a)
This is a continuation of C & O 362. Topics covered include error correcting codes, resolvable designs, affine designs, weighing matrices, and their interaction.
Prereq: C & O 362 or consent of instructor
(C & O 460b)
General topics: methods of data storage for combinatorial problems, representation of sets, etc. Algorithms for permutations, combinations, partitions, etc. The use of generating functions, and methods of handling them on a computer. Enumeration problems: Polya’s theorem and variations. Applications.
Prereq: Math 321a/b and two of CS 140, 180, 240, 250
Course Descriptions 381 Combinatorics and Optimization
Methods of searching and sorting. Tree-like data structures: branch and bound methods. Back-track methods. Boolean programming. Construction problems: construction of graphs, digraphs, trees. The cell-growth problem and its variations.
Prereq: C & O 464a
Topics in graph theory. These may include symmetry in graphs, planarity, bipartite graphs, minimax theorems, directed graphs, enumeration, algorithms, colouring problems, matrices and graphs.
Prereq: C & O 370a/b or consent of instructor
(C & O 458a)
Continuation of topics covered in C & O 470a.
Prereq: C & O 470a
Listed without a description.
Listed without a description.
A study of selected topics from Greek geometry. Some related work of post-renaissance scholars is included. Topics include: famous construction problems, pythagorean arithmetic, regular solids, four discoveries of Archimedes, the problem of Apollonius; selected works of Archimedes, Euclid, Apollonius, Euler, Steiner.
Prereq: None
(C & O 446a)
A study of selected topics from post-renaissance mathematics. Topics include material on prime numbers, Fermat’s Last Theorem, the Gaussian Integers, the Fibonacci Sequence, other topics form elementary number theory, a collection of outstanding problems in geometry (Fagnano, Steiner- Lehmus, Morley).
Prereq: None
(C & O 446b)
Prereq: Consent of department
Department of