28 courses in the 1992–93 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.
Structure and classification of optimization problems. The concepts of algorithm and heuristic. Continuous models. Linear models. Branch-and-bound, dynamic programming, implicit enumeration and approximation. Applications of optimization models. Prereq: MATH 1118, 113B or equivalent C&O 227 cannot be counted for credit toward a BMath Honours degree.
Introduction to the combinatorics of ordi- Nary generating functions. Introduction to basic graph theory and graphical algorithms.
Prereq: MATH 136, 138
Antireq: C&O 220
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
Course Descriptions
A first course in error-correcting codes. Linear block codes, Hamming-Golay codes and multiple error-correcting BCH codes are studied. Various encoding and decoding schemes are considered. Prereq: 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. Determining the connectivity of a graph.
Prereq: C&O 230
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 225 or 235
Antireq: ACTSC 335
Review of linear programming. Shortest
path problems. The max-flow and mini-
mum cost flow problems. Network sim-
plex, augmentation and out-of-kilter algo-
rithms. Applications to problems of
transportation, distribution, man-job
assignments and critical-path planning. Prereq: C&O 350
A first course in the mathematics of nonlinear optimization. Necessary and sufficient optimality conditions for unconstrained and constrained problems. Convexity and its applications. Computational techniques and their analysis.
Prereq: MATH 235, 237
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 135, 136, 138 and thirdyear standing
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. 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 ctyptography. 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 applica-
tions of computers to combinatorial prob-
lems. 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
Theorem, Four-Colour problem. Colourings: Critical Graphs, Five-Colour Theorem, Vizing's Theorem, Snarks. Flows: Eight-Flow Theorem, Six-Flow Theorem, Tutte's Conjectures. Embeddings: Genus, 2-cell Embeddings, Map-Colour Theorem. Coverings: Double Cover Conjecture.
Prereq: C&O 342 or consent of instructor
Packing, covering and partitioning probtems. 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 branch-and-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
Course Descriptions Combinatorics and Optimization
An introduction to the anatysis, 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
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
An introduction to the modern theory of convex programming, its extensions and applications. Structure of convex sets, separation and support, set-valued analysis, subgradient calculus for convex functions, Fenchel conjugacy and duality, Lagrange multipliers, minimax theory. Algorithms for non differentiable optimization. Lipschitz functions, tangent cones and generalized derivatives, introductory non-smooth analysis and optimization. Prereq: C&O 367, AM/PMATH 331 or 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 367, and C&O 350 or consent of instructor
16:35
An in-depth examination of the origins of mathematics, beginning with examples of Babylonian mathematics. Topics may include Pythagorean triples, solution of equations, estimation of pi, duplication of the cube, trisection of an angle, the Fibonacci sequence, the origins of calculus.
Prereq: MATH 135, 136, 138 and thirdyear standing
Prereq: Consent of department
Computer Science
Undergraduate Advisors A. Pidduck, DC 3106, ext 4662 B.W. Becker, DC 3105, ext 4661
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 Computer Science - Information Systems Option, and all Joint and Double Honours BMath programs involving Computer Science as one of the majors.
CS 130 and 134 are normally restricted to students in the Faculty of Mathematics. All other CS courses numbered with a middie digit of 0 through 3 are non-specialist courses. As such, they will not normally be open to Computer Science Major students, but they will be available to all other students in the University, subject to resource limitations.
Several CS Major courses aré also open to other students. in addition, 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. Computer Science Major courses require students to have experience programming with a block-structured imperative language such as Pascal, C or Turing. These concepts of computer programming are covered in CS 130. Students who have substantial programming experience will be permitted to start their program with CS 134, which is an introduction to the basic concepts of computer science. Students in CS Major programs who do not take CS 130 will be required to take an additional third or fourth-year CS course selected from the specialist stream of courses.
3. The Computer Science Department is experiencing demand for its courses beyond available resources. Thus, accessibility ta Computer Science courses cannot be guaranteed to all students. Every effort will be made 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.
4. 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-tine non-degree and postdegree students, will normally be limited to at most one Computer Science course per term from the non-specialist offerings. (Post-degree 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.
5. 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 er term in third and fourth year. Other students are limited to two CS courses per term in third a fourth year. .
6. 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
7. Students in faculties other than Mathematics should take particular note of the following courses: CS 100, 102, 212, 230, 316.
8. For the purposes of satisfying prerequisites for non-specialist courses, except where otherwise specified, the second entry in each of the following course pairings may normally be sub- Stituted for the first entry of that pairing: (CS 230 and 241) and (CS 334 and 340).
9. 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 tor minimum number of courses in Computer Science at the 400 level, but may be taken in place of additional 400-level courses.
10. The prerequisite phrase “x-year standing” means that a student must be registered in year x or higher.
11. The following courses are offered in conjunction with the Division of Mathematics for industry and Commerce: CS 330, 338, 432, 446, 448 and 482.
12. The standard penalty for cheating will be the assignment of a grade of -100% for the assignment, test or exam in question, with a minimum deduction of 5% from the final course grade. All such incidents will also be reported to the Associate Dean (Undergraduate Studies) of the Student's faculty.
13. Since CS 462 and 476 are offered only in the Fall term, Co-op students in Stream 8 will need to carefully plan the sequence of prerequisites in order to take these courses in the 3B term.