44 courses in the 1979–80 Undergraduate Calendar, read from the scanned original. The text comes from OCR, so check the scanned page before relying on a detail.
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.
Coreq: Math 231a/b
N.B8.: Credit will be granted for at most two of C & 0 280, 282, 283..
Existence and non-existance. 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 N.B:: Credit will be granted for at most two of C & 0 280, 282, 283. Also offered at St. Jerome's College in Winter Term.
(C & O 239a)
Course Descriptions 359
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.8.: Credit will be granted for at most two of C & O 280, 282, 283. Also offered at St. Jerome's College in Fall Term.
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
(C & O 352a)
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&0331a
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& O331a
(C & 0 353a)
An applications oriented course complementary to C&O 340.
Prereq: C & 0340
(C & O 353b)
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.
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
Basic definitions; trees, connectivity; Euler tours; matchings; edge colourings. The emphasis will be on proof techniques and problem solving.
Prereq: Math 221a/b
(C&O 351a)
Independent sets and cliques; vertex colourings; planar graphs, face colourings and Hamilton cycles; directed graphs.
Prereq: C & O 370a
(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
Course Descriptions . Combinatorics and Optimization
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 & 0 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 &0337b)
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&O331a
Branchings in networks. Elementary matroid theory illustrated by forests, transversals, algebraic dependence, and geometry. Matroid partitions and intersections. Submodular functions and polymatroids. Prereqg:C &0431a
(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. ‘ Non-feasible direction methods including penalty function techniques. Emphasis is on algorithms rather than abstract theory.
Prereq: C & 0 332
(C&O 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 &0331a
(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 & 0 433a
(C&O 452b)
Listed without a description.
A mathematically-oriented course on the basics 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.
Prereq: C & O331a and Stat 220
(C&O 454a)
Listed without a description.
Listed without a description.
Listed without a description.
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)
Course Descriptions 361 Combinatorics and Optimization
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& O331aorC & 0 340
(C & O 456a)
Listed without a description.
Listed without a description.
Listed without a description.
Enumerative mathematics, combinatorial identities, generating functions, counting of labelled and unlabelled objects, theorems of Polya, Redfieid-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 ona computet. Enumeration problems: Polya’s theorem and variations.. Applications.
Prereq: Math 321a/b and two of CS 140, 180, 240, 250
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 & 0 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 & 0 370a/b or consent of instructor
(C&O 458a)
Continuation of topics covered in C & O 470a. Prereq: C & 0 470a
(C & O 458b)
Listed without a description.
Listed without a description.
Astudy of selected topics from Greek geometry. Some related work of post-renaissance scholars is inciuded. Topics include: famous construction problems, pythagorean arithmetic, regular solids, four discoveries of Archimedes, the problem of Apollonius; selected
(C&O 446a)
works of Archimedes, Euclid, Apollonius, Euler, Steiner.
Prereq: None ’
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). a
Prereq: None
(C & O 446b)
Cao49 FWS 2R 05 (C&0499) Reading in Combinatorics and Optimization Prereq: Consent of department