30 courses in the 1989–90 Undergraduate Calendar, read from the scanned original. The text comes from OCR, so check the scanned page before relying on a detail.
Elementary principles of enumeration. Principle of inclusion-exclusion, generating functions, recurrence equations. Elementary graph theory and graphical algorithms. Introduction to design theory.
Antireq: C&O 230
C&O 220 cannot be counted for credit toward a BMath Honours degree.
Introduction to the combinatorics of ordinary generating functions. Introduction to basic graph theory and graphical algorithms.
Prereq: MATH 130B, 134B or MATH 136, 138
Antireq: C&O 220
Also offered at St. Jerome's College in Fall Term.
Structure and classification of optimization problems. The concepts of algorithm and heuristic. Continuous models. Linear models. Methods of branch-andbound, dynamic programming, implicit enumeration and approximation. Applications.
Prereq: MATH 130B, 134B or MATH 117B, 113B
Students may not enrol in C&O 270 it they have previously completed, or are concurrently enrolled in, C&O 350 or 367.
The combinatorics of the ordinary and exponential generating functions. Matrix methods, and decompositions. Applications to the enumeration of sequences, permutations, trees, lattice paths and partitions.
Prereq: C&O 230
A first course in error-corracting codes. Linear block codes, Hamming-Golay codes and multiple error-correcting BCH codes are studied. Various encoding and decoding schemes are considered. Prereq: MATH 234B or PMATH 336 Offered at St. Jerome's College.
An introduction to the ideas, methods
and applications of graph theory.
Finding shortest paths and maximum
matchings in weighted graphs. Deter-
mining the connectivity of a graph. Prereq: C&O 230
Planar graphs and embeddings in other surfaces. Vertex, edge and face colourings. The four-colour problem. Hamilton cycles. Integral flows.
Prereq: C&O 342
A first course in problem formulation and solution techniques in linear programming. The simplex and revised simplex methods. Active set formulation of the simplex method. Theory and applications of duality theory. Sensitivity Analysis.
Prereq: MATH 224A or 235
Antireq: ACTSC 335
Review of linear programming. Shortest
path problems. The max-flow and
minimum cost flow problems. Network
simplex, augmentation and out-of-kilter
algorithms. Applications to problems of
transportation, distribution, man-job
assignments and critical-path planning. Prereq: C&O 350
One-dimensional optimization. Introduction to unconstrained optimization in several variables including Newton's method, secant methods, conjugate gradient methods and the special case of quadratic forms. Introduction to constrained optimization including the elements of Kuhn-Tucker theory, active set methods and penalty function techniques.
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: C&O 350 Antireg: ACTSC 335
A course in problem*solving. 100 problems are studied. Problems are taken mainly from the elementary parts of algebra, geometry, number theory, combinatorics and probability.
Prereq: MATH 130B, 134A/B or MATH 135, 136, 138
Although the mathematics for this course is technically elementary, the course is intended for third and fourthyear students, and the mathematical maturity of a senior student will be assumed.
An introduction to the combinatorial aspects of the real plane. Main topics covered are the enumeration of various combinatorial objects in the plane, Sylvester's Triad Problem, Pick's Theorem, partitioning the interior of a rectangle into squares of different sizes, an introduction to the theory of convex sets in the plane. Helly's theorem and certain ramifications will be explored.
Prereq: MATH 130B, 134A/B or MATH 135, 136, 138 Although the mathematics for this
course is technically elementary, the course is intended for third and fourthyear students, and the mathematical maturity of a senior student will be assumed.
Course Descriptions 16:103 Mathematics.
Cortmatorics and Optimization
The course is an extension of C&O 330. The Lagrange implicit function theorem, hypergeometric series, and the ring of formal Laurent series. The combinatorics of Eulerian generating series, enumeration under the action of a group, the algebra of symmetric functions, the group algebra of the symmetric group, with applications.
Prereq: C&O 330
Topics covered include error correcting codes, resolvable designs, affine designs, weighing matrices, and their interaction.
Conventional or single key cryptogtaphy from the Caesar cipher to the U.S. Data Encryption Standard. Public or two key cryptography. Applications include secrecy/privacy, user or message authentication, financial transactions security.
Prereq: STAT 230. At least one of C&O 331 and PMATH 340 is recommended.
A course covering a number of applications of computers to combinatorial problems. General procedures — backtrack programming, generation of permutations, partitions, etc., as well as the solution of many specific problems. Includes an introduction to computational complexity.
Prereq: C&O 230
An undergraduate seminar in combinatorics. The primary objective is to study current work in specific areas of combinatorics. Course content may vary from term to term.
Prereq: Consent of instructor
An in-depth study of one or two topics in graph theory. Course content may vary from term to term. Topics may include planar graphs, extremal graph theory, directed graphs, enumeration, algebraic graph theory, probabilistic graph theory, connectivity, graph embedding, colouring problems. Prereq: C&O 342 or consent of instructor
Packing, covering and partitioning prob- Jems. Integer programming. Good algorithms for optimum assignments, matchings, flows, anti-chains and connectivity. Paths, trees and flowers. Min-max relations. Convexification of discrete problems. Vertices and facets of convex polyhedra. The concepts of NP and co-NP. Reducing NP problems to integer programming.
Prereq: C&O 351
Formulation of problems as integer linear programs. Solution by branchand-bound and cutting plane algorithms. Introduction to the theory of valid inequalities and polyhedral combinatorics..
Prereq: C&O 351
Sequencing algorithms for scheduling tasks on single machines, parallel machines, and flow shops. Applications to scheduling computers and manufacturing facilities. Combinatorial techniques used in algorithm development and convergence proofs.
Prereq: C&O 351 or 370
An introduction to the analysis, through
appropriate mathematical models, of
competitive situations such as those
arising in social, economic, political or
military conflict. Emphasis is placed on
the theory of two-person games. Prereq: C&O 350
Methods for the minimization and maximization of piecewise linear functions and linear functions subject to linear constraints, with applications to linear programming and data fitting. Emphasis is on algorithms, numerical considerations and software implementation, that take into account the fact that in practise many of these problems are large and Sparse.
Prereq: One of CS 372, C&O 350, or CS 337 and consent of instructor. CS 374 is recommended.
Cross-listed as C& 473
16:104 Course Descriptions Mathematics.
Combinatorics and Optimization
An undergraduate seminar in optimization. The primary objective is to study recent work in specific areas of optimization. Course content may vary from term to term.
Prereq: Consent of instructor
A detailed presentation of optimality conditions and effective algorithms for the solution of a quadratic programming problem. All concepts are developed as natural extensions of their counterparts in linear programming. Applications from portfolio analysis, engineering plasticity, regression, pattern recognition.
Prereq: C&O 350
Geometry and numerical algorithms of nonlinear optimization. Variable metric and conjugate gradient methods. Convex programming. Feasible and nonfeasible direction methods. Recursive quadratic programming, nonorthogonal projections and active set Strategies.
Prereq: C&O 350, 367
An in-depth examination of the origins of modern mathematics, beginning with examples of Babylonian mathematics. Topics include Pythagorean tripies, solution of equations, estimation of pi, ' duplication of the cube, trisection of an angle.
Prereq: MATH 130B, 134A/B or MATH 135, 136, 138
Although the mathematics for this course is technically elementary, the course is intended for third and fourthyear students, and the mathematical maturity of a senior student will be assumed.
A continuation of C&O 480 (History of Mathematics 1), based on more recent mathematics, beginning with the Fibonacci sequence and including the origins of calculus.
Prereq: MATH 130B, 134A/B or MATH 135, 136, 138
Although the mathematics for this course is technically elementary, the course is intended for third and fourthyear students, and the mathematical maturity of a senior student will be assumed.
Prereq: Consent of department
Computer Science
Course Descriptions
Courses not offered in the current academic year are listed at the end of this section.
Introductory Notes
1. The Department of Computer Science has two distinct streams of courses, one for students who have been admitted into a Computer Science Major program, and another especially designed for non-specialists who wish to become sophisticated computer users. Within this context, Computer Science Major programs include Honours Computer Science, Honours Co-op Computer Science with Electrical Engineering Electives, Honours Co-op Computer Science - Information Systems Option, and all Joint and Double Honours BMath programs involving Computer Science as one of the majors.
CS 131 and 132, required in all four-year BMath programs, are normally restricted to students in the Faculty of Mathematics. All other CS courses numbered with a middle digit of 0 through 3 are nonspecialist courses. As such, they will not normally be open to Computer Science Major students, but they will be available to ail other students in the University, subject to resource limitations.
Several CS Major courses are also open to other students. In addé tion, where resources permit, students with exceptionally high academic standing in other programs may be considered for admission to restricted CS Major courses on an individual basis. To be considered, students should consult a Computer Science Undergraduate Advisor.
2. The Computer Science Department is experiencing demand for its courses beyond available resources. Thus, accessibility to
Computer Science courses cannot be guaranteed to all students. Every effort will be made to accom modate those students who preregister during published University preregistration periods. While priority will be given to these preregistrants, admission to specific courses cannot be guaranteed and course substitutions may be required to satisfy degree requirements.
Regular students will not normally be permitted to enrol in Computer Science courses during the Spring term. (See section 5.4 on page 13:36.)
Co-op students will not normally be permitted to enrol in Computer Science courses while on a work term.
All other part-time students, as well as full-time non-degree and post-degree students, will normally be limited to at most one Computer Science course per term from the non-specialist offerings. (Postdegree students on academic leave from their home institution should consult a Computer Science Advisor to arrange an appropriate selection of courses.) Priority for registration will normally be given to students registered full-time in a degree program.
Students in first and second year are limited to one Computer Science course per term. Students in CS Major programs are limited to three CS courses per term in third and fourth year. Other students are limited to two CS courses per term in third and fourth year.
Please note that the terms in which courses are offered may deviate from those indicated below. Students are advised to consult the University Course Offerings List published at preregistration time.
Students in faculties other than Mathematics should take particular note of the following courses: CS 100, 102, 212, 230, 316.
For the purposes of satisfying prerequisites for non-specialist courses, the second entry in each of the following course pairings may normally be substituted for the first entry of that pairing: (CS 230 and 242), (CS 334 and 340), and (CS 335 and 351/354).
8. Students who have demonstrated exceptionally strong academic performance will be permitted to enrol in 600-level CS courses at the discretion of the instructor, if there is available capacity. Courses at the 600 lavel may not be used to satisfy a program requirement for minimum number of courses in Computer Science at the 400 level, but may be taken in place of additional 400-level courses.
9. The prerequisite phrase “x-year standing” means that a student must be registered in year x or higher.
10. The following courses are offered in conjunction with the Division of Mathematics for Industry and Commerce: CS 330, 432, 438, 446, 448 and 482.