42 courses in the 1978–79 Undergraduate Calendar, read from the scanned original. The text comes from OCR, so check the scanned page before relying on a detail.
CO 239AAn Introduction to CombinatoricsF 2C,2T 0.5
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. Recommended for students wishing an introduction
to discrete mathematics.
Prereq: Math 124a/b or 134a/b
Also offered at St. Jerome’s College in Winter Term.
C&O 0239b W,S 2C2T 05
An Introduction to Optimization
Convex sets. Linear programming. Directed graphs. Applications of Boolean Algebra to Combinatorical Circuits. Probability; Markov chains; random walks. Theory of Games.
Prereq: Math 124a/b or 134a/b
Also offered at St. Jerome’s College in Fall Term.
CO 249BIntroduction to Combinatorics and OptimizationW 2C,1T 0.5
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 330AMathematical Discovery and Invention 1F,S 2c 0.5
A study of about 100 challenging problems taken from many areas of elementary mathematics — number theory, combinatorics, geometry, probability, logic.
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.
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.
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. A course in linear algebra will be helpful but not essential. No text is required. As a reference text H. Ryser’s Combinatorial Mathematics is suggested. Prereq: C&0337a
CO 350AGraph Theory With Applications 1F,W,S 2C,1T 0.5
Basic definitions; shortest paths; minimum-weight spanning trees; connectivity and communication networks, Euler tours and the Chinese postman problem; Hamilton cycles and the travelling-salesman problem; matchings and the optimal assignment problem. Prereq: Math 221a or 231a.
Course Descriptions 341 Combinatorics and Optimization
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 slacknes8. Sensitivity analysis.
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.
Branchings in networks. Elementary matroid theory illustrated by forests, transversals, algebraic dependence, and geometry. Matroid partitions and intersections. Submodular functions and polymatroids. Prereq: C & 0 437a or consent of instructor
CO 438ACombinatorial Applications. of Computer 1F,S 3C 0.5
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 or 331a/b (or P Math 341a/b) and two of CS 140, CS 180, CS 240, 250
CO 438BCombinatorial Applications of Computers 2W 3c 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: C&O 438a
Course Descriptions Combinatorics and Optimization
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: Third year standing
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).
CO 450ALinear and Quadratic Programming 1F 20 O58 .
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.
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&0 450a
C&O 0451a F 2c 0.5
Nonlinear Optimization 1
Recent algorithms for constrained and unconstrained
optimization problems will 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
for those wishing to pursue graduate courses in
mathematical programming.
Prereq: One ot Math 322a, 332a, P Math 347 a/b, CS 370.
Nonlinear Programming; convergence conditions and convergence rates for some unconstrained optimization methods, introduction to the Kuhn-Tucker conditions
and duality theory for nonlinear programmes, optimality _
conditions for a quadratic programme. Prereq: C&O 451a or consent of the instructor
Queueing models are analyzed, including, single channel queues of infinite and finite capacity; infinite and finite customer populations. Multi-server queues in series of 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 to 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/job shop. Capital budgeting, distribution problems occurring in scheduling trucks, trains, and in warehouse movements.
Prereq: C&0O352a or C&O 353a
C&0O456b WwW 2C,1T 0.5 Scheduling 2
Topics complimentary to those of C&O 456a. Prereq: C&O 456a and C&0O352b
integer programmes arising in practice. Modelling techniques. Methods of solution, including an introduction to Boolean methods. Problems with special structure.
CO 457BBoolean Methods In Discrete OptimizationF 2° 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, assumability, thresholdness. Applications to graphs, games. Theoretical and algorithmic developments. Research problems. Prereq: C&0457a
Topics in graph theory. These may include symmetry in graphs, planarity, bipartite graphs, minimax 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. Prereq: C & 0351a or consent of instructor
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 785 Planar graphs" and Math 792 ‘'Enumerative combinatorial theory”.
This is a continuation of C&O360a. Topics covered include error correcting codes, resolvable designs, affine designs, weighing matrices, and their interaction. Prereq: C& 0360a or consent of instructor