31 courses in the 1977–78 Undergraduate Calendar, read from the scanned original. The text comes from OCR, so check the scanned page before relying on a detail.
Notes
Department of Combinatorics and Optimization Undergraduate Course Descriptions
Note Course descriptions are given under the new course numbers introduced in 1976
C&O 239a, F 2C,2T 5 An Introduction to Combinatorics Existence and non-existence. Enumeration. Combinations and Permutations. Inclusion-exclusion principle. Linear equations with unit coefficients. Recursion. Generating functions. Chromatic polynomials. Applications to geémetry designs.
Recommended for students wishing an introduction to discrete mathematics. Prereq: Math 124/134
CO 239BAn Introduction to OptimizationW,S 2C,2T 0.5
Convex sets. Linear programming. Directed graphs. Applications of Boolean Algebra to Combinatorical Circuits. Probability; Markov chains; random walks. Theory of Games.
Prereq: Math 124/134; 239a is Not a prerequisite.
C&O 0249b Ww 2C,1T 5
Introduction to Combinatorics and Optimization
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.
CO 330BMathematical Discovery and Invention 2W 2C 0.5
A study of about 100 challenging problems taken from many areas of elementary mathematics — number theory, combinatorics, geometry, probability, logic.
Prereq: None. C &0330a is Not a prerequisite to C&O 330b.
A study of combinatorial properties of plane figures, covering problems, addition of figures, maxima and minima problems, curves of constant breadth and delta-curves.
Offered at St. Jerome's College
C&O 35ila FS 2c. OS
Introduction to Graph Theory and Combinatorics 1
A study of the basic concepts and problems of graph theory: connection, minimum path problems; bipartite graphs, the marriage problem; 1-factors of arbitrary graphs; planar graphs.
CO 351BIntroduction to Graph Theory and Combinatorics 2W 2c 0.5
Hamiltonian circuits in a graph, four colour problem, other colouring problems; directed graphs, balanced orientations; an introduction to the theory of enumeration, with applications to counting graphs and other combinatorial objects.
Optimization techniques common to a wide variety of operations research and engineering problems, and of fundamental theoretical interest. Linear programming, simplex method, duality and complementary slackness, sensitivity analysis, integer programming, games. Prereq: Math 231/221 and Math 230/220
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.
Basic enumeration principles, emphasizing the combinatorial significance of generating functions. Topics to include the principle of inclusion-exclusion, Polya theory, the Lagrange theorem, and vector spaces over finite fields. Applications to a variety of combinatorial problems.
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.
CO 438ACombinatorial Applications of Computer 1F,S 2C to]
General topics: methods of data storage for combinatorial problems, representation of sets, etc. Aigorithms 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: At least one computer programming language. Math 321/331
CO 438BCombinatorial Applications of Computers 2W 2c 0.5
Methods for 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: At least one computer programming language. Math 331, C&0438a.
C&O 0446a F 2c 5
History of Mathematics 1
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: No formal prerequisites are demanded.
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 for elementary number theory, a collection of outstanding problems in geometry (Fagnano, Seiner-Lehmus, Morley).
Prereq: No formal prerequisites are demanded.
C&O 4502e F 2c 5
Linear and Quadratic Programming A
Review of relevant Calculus and Aigebra. Formulation of the problem. Example problem models from Structural Engineering, Economics, Statistics and a quadratic energy model (viz. petroleum, coai, etc.). Optimality conditions fora quadratic programme. Quadratic duality theory; classic linear duality as a special case. Sensitivity analysis. Introduction to algorithms.
Prereq: Math 220/230 and Math 221/231
C&O 4505 W 20 5
Linear and Quadratic Programming B
Algorithms. Conjugate directions, the basic projection algorithm for quadratic programming. The Simplex method for linear programming as a special case. Numerically effective modifcations 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 450a
C&O 0451a F 2c 5
Nonlinear Optimization 1
Recent algorithms for constrained and unconstrained
optimization problems wiil be presented. Topics will
include Newton, quasi-Newton, conjugate gradient.
feasible direction, and penalty algorithms. Recommended for students interested in operations
research, industrial engineering, computer science and
far those wishing to pursue graduate courses in
mathematical programming.
Course Descriptions 357 Combinatorics and Optimization
Convex sets, geometric motivation for the Simplex Aigorithm. Simplex Algorithm. Revised Simplex Algorithm. Degeneracy. Post-optimal analysis (parametric programming, sensitivity analysis, etc.). Applications, Duality Theory, Dual Simplex Algorithm. Prereq: Linear Algebra and Elementary FORTRAN or consent of instructor
C&O 0452b WwW 2c 5
Linear and Integer Programming
(Theory, Applications and Related Topics) 2
Primal Dual Algorithms. Transportation Problem. Decomposition of large systems. Formulation of integer, mixed integer, and discrete programming problems. Methods of solution (cutting plane methods, implicit enumeration, branch-and-bound, etc.). Partitioning methods. Applications, computerized methods of solution.
Prereq: C &0452a or 352a or consent of instructor
C&O 0453a FS 2c 5
Queueing Theory
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.
A mathematically-oriented course on the basis of game theory, with applications to economics, bargaining, and strategy. Classification of games; solution of matrix games and their relationship to linear programming; infinite zero-sum games; utility theory; bimatrix games and the bargaining problem
Dynamic Programming- 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 problem, the travelling salesman problem, introduction to optimal control, an aggregate scheduling problem of inventory.
Dynamic Programming—stochastic decision process problems; stopping time problem, time delay, certainty equivalence, stochastic path problems, series and parallel feedback control, discrete time variational problems, irregular problems.
Single machine job shops, parallel machines, flow-shop scheduling, the general m/n jobshop. Capital budgeting, distribution problems occurring in scheduling trucks, trains, and in warehouse movements.
CO 456BBoolean Methods in Discrete OptimizationF 2c 0.5
Elements of Boolean algebra, Boolean functions and expressions. Implicants, prime implicants. Solving linear programmes in 0-1 variables. Minimization of quadratic functions. Monotonicities, assummability, thresholdness. Applications to graphs, games. Theoretical and algorithmic developments. Research problems.
Topics in graph theory. These may include symmetry in graphs, planarity, bipartite graphs, minimx theorems, directed graphs, enumeration, algorithms, colouring problems, matrices and graphs.
Recommended for students who have taken a course in graph theory and wish to study additional topics not normally covered in an introductory course.
Enumerative Mathematics, Combinatorial identities, generating functions, counting of labelled and unlabelled objects, theorems of Polya, Redfield-Read, and de Bruijn, permanents, combinatorial decompositions.
Recommended as a useful preliminary for Math 7&5 “Planar graphs” and Math 792 ‘‘Enumerative combinatorial theory”’.
Prereq: A knowledge of elementary group theory (Math 337)
This is a continuation of C &O360a. Topics covered include error correcting codes, resolvable designs, affine designs, weighing matrices, and their interaction. Prereq: C &O360a or consent of instructor