32 courses in the 1976–77 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 Undergraduate Course Descriptions
Note Course descriptions are given under the new course numbers introduced in 1976.
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. Prerequisite: Math 124/134, 2 hours lectures, 2 hours tutorial.
Convex sets. Linear programming. Directed graphs. Applications of Boolean Algebra to Combinatorical Circuits. Probability; Markov chains, random walks. Theory of Games.
Prerequisite: Math 124/134; 239a is Not a prerequisite. 2 hours lectures, 2 hours tutorial, one term
A study of about 100 challenging problems taken from many areas of elementary mathematics ~ number theory, combinatorics, geometry, probability, logic.
2 hours lectures, one term
A study of about 100 challenging problems taken from many areas of elementary mathematics — number theory, combinatorics, geometry, probability, logic. Prerequisite: None. C&O 330a is Not a prerequisite to C&O 330b. 2 hours lectures, one term
A study of the basic concepts and problems of graph theory: connection, minimum path problems; bipartite graphs, the marriage problem; |-factors of arbitrary graphs; planar graphs.
Prerequisite: Math 239 recommended.
2 hours lectures, one term
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.
Prerequisite: Math 239 and Math 351la recommended.
2 hours lectures, one term
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. Prerequisites: Math 231{221 and Math 230/220.
2 hours lectures, one term
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. Continuous - optimization techniques, Lagrange multipliers. Applications to inventory theory, capital budgeting, regression analysis.
Prerequisites: Math 231/221 and Math 230/220.
2 hours lectures, one term
An applications oriented course that illustrates how various mathematical models and methods of optimization can be us2d to solve problems arising in business, industry and science.
2 hours lectures, one term
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.
Prerequisite: C&O 352a or consent of instructor.
2 hours lectures, one term
Branchings in networks. Elementary matroid theory illustrated by forests, transversals, algebraic dependence, and geometry. Matroid partitions and intersections. Submodular functions and polymatroids.
Recommended for students interested in theoretically advanced study in Combinatorics and Optimization or Computer Science.
Prerequisite: C&O 437a or consent of instructor. 2 hours lectures, one term
Course Descriptions Combinatorics and Optimization
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 computer. Enumeration problems: Polya’s theorem and variations. Applications.
Prerequisites: At least one computer programming language. Math 321/331. 2 hours lectures, one term
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&O 438a. 2 hours lectures, one term
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. Prerequisites: No formal prerequisites are demanded.
2 hours lectures, one term
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, Steiner-Lehmus, Morley).
Prerequisites: No formal prerequisites are demanded.
2 hours lectures, one term
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.
‘2 hours lectures, one term
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.
Prerequisite: C&O 45la or consent of the instructor.
2 hours lectures, one term
(Theory, Applications and Related Topics) 1
Convex sets, geometric motivation for the Simplex Algorithm. Simplex Algorithm. Revised Simplex Algorithm. Degeneracy. Post-optimal analysis (parametric programming, sensitivity analysis, etc.) Applications, Duality Theory, Dual Simplex Algorithm.
Prerequisites: Linear Algebra and Elementary FORTRAN or consent of instructor. 2 hours lectures, one term
(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. Prerequisites: C&O 452a or 352a or consent of instructor. 2 hours lectures, one term
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.
Prerequisite: Introductory Probability.
2 hours lectures, one term
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.
Prerequisites: Math 231 and basic probability theory 2 hours lectures, one term
N-person games; Shapley value; metagames. Prerequisite: C&O 454a.
Course Descriptions 321 Combinatorics and Optimization
Dynamic Programming — deterministic decision process problems; monotonic path problems, equipment + replacement, single and multidimensional 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.
Prerequisite: C&O 352a or consent of instructor.
2 hours lectures, one term
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.
Prerequisite: C&O 455a. 2 hours lectures, one term
Single machine job shops, parallel machines, flow-shop scheduling, the general m/n job shop. Capital budgeting, distribution problems occurring in scheduling trucks, trains, and in warehouse movements.
2 hours lectures, one term.
Prerequisites: C&O 352 recommended.
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.
2 hours lectures, one term.
This course will be concerned with the combinatorial problems of retrieving data from a store and discusses the principal algorithms for doing this. Methods for constructing appropriate relational structures and their stability are considered, as well as devices for improving substantial gains in efficiency.
This course considers the application of combinatorial structures, such as block designs, to information retrieval. The construction of such structures will be considered together with methods for optimising a general model for the retrieval problem.
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. Prerequisite: C&O 35la or consent of instructor.
2 hours lectures, one term
Continuation of topics covered in 458a. Prerequisite: C&O 458a. 2 hours lectures, one term
C&O 459a Algebraic Graph Theory 1 C&O 459b Algebraic Graph Theory 2
C&O 460a Combinatorics 1
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’’.
Prerequisite: A knowledge of elementary group theory
(Math 331}. 2 hours lectures, one term.
The existence and construction of error correcting codes, projective geometries, orthogonal Latin squares, balanced incomplete block design and other combinatorial configurations.
Recommended for C&O 780 Combinatorial Analysis. Prerequisite: Theory of finite groups, rings and fields (Math 331). 2 hours lectures, one term.
Course Descriptions