25 courses in the 1990–91 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, gener-
ating 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. Intraduc-:” tion to basic graph theary and graphical algorithms.
Prereq: MATH 130B, 134B or MATH 136, 138
Antireq: C&O 220.
Also offered at St. Jerome's College in Fail Term.
10270 FW,S 3C 0.5° muroduction to Optimization Structure and classification of optimiza- “=n problems. The concepts of algor.
m and heuristic. Continuous models.
war models. Methods of branch-andbound, dynamic programming, implicit enumeration and approximation. Appli-
tions.
Prereq: MATH 1308, 134B or MATH 771B, 113B
Students may not enrol in C&O 270 if “ay have previously completed, or are
neurrenily enrolieg irs, G&O 350 or
7. Aotgue ny
wy
‘@ combinatorics of the ordinary and eaponential generating functions. Matrix methods, and decompositions. Applica- “-ng to the enumeration of sequences, tmutations, trees, lattice paths and fttitions. Prereq: C&O 230
10331 W 3C 0.5
ding Theory wy rn first course in error-correcting codes. Linear block codes, Hamming-Golay “des and multiple error-correcting
2H codes are studied. Various
coding and decoding schemes are considered.
Prereq: MATH 234B or PMATH 336
Offered at St. Jerome's College.
vd0 342 FS 3C 05
Graph Theory 1
4 introduction to the ideas, methods id applications of graph theory. ‘ding shortest paths and maximum
matchings in weighted graphs. Deter-
mining the connectivity of a graph. Preraq: C&O 230
v0 343 W 3C 0.5 Graph Theory 2 Stanar graphs and embeddings in other irfaces. Vertex, edge and face colourgs. The four-colour problem. Hamilton cycles. Integral flows. Preraq: C&O 342
&0 350 F.W,S 3C 0.5 Near Programming A first course in problem formulation and solution techniques in linear ‘ogramming. The simplex and revised mplex methods. Active set formulation of the simplex method. Theory and applications of duality theory. Sensitivity nalysis. Prereq: MATH 224A or 235 Antireq: ACTSC 335
Course Descriptions Combinatorics and Optimization
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 Antireq: 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 1308, 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.
16:35
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.
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 inciude error correcting codes, resolvable designs, affine designs, weighing matrices, and their interaction.
Prereq: MATH 234B or PMATH 336
Conventional or single key cryptography 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 problems. 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, paraliel 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. Prereg: C&O 350
Course Descriptions Combinatorics and Optimizatio.
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, numerica! 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 CS 473
An undergraduate seminar in optimization. The primary objective is to study tecent 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 porifolio 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 triples, 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 recer. 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
Undergraduate Officers H. Pell, DC 3105, ext. 4661 A. Pidduck, DC 3106, ext 4662
Introductory Notes
1. The Department of Computer Science has two distinct streams c courses, one for students who hav been admitted into a Computer Science Major program, and another especially designed for non-specialists who wish to becorr 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 all othe 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.
The Computer Science Department fs experiencing demand for its courses beyontiavaiatie resources. Thie aeeasssibility to Computer Science courses cannot be guaranteed to all students. Every effort will be: madé to accommodate 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. i.
Regular students will not normally be permitted to enrol in Computer Science courses during the Spring term. (See section 6:4 on page 13:38.)
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.
Course Descriptions Computer Science
6. Students in faculties other than Mathematics should take particular note of the following courses: CS 100, 102, 212, 230, 316.
7. 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 level 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.