29 courses in the 1987–88 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-exciusion, generating functions, recurrence equations. Elementary graph theory &nd 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, 1348
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-and-bound, implicit enumeration and approximation. Applications. . Prereq: MATH 1308, 1348 Students may not enrol in C&O 270 if they have previously completed, or are concurrently enrolled in, C&O 350 or 367.
The combinatorics of ordinary and exponential generating functions. Matrix methods, and decompositions. The Lagrange theorem. Applications to enumeration of sequences, trees, covers, lattice paths and partitions.
Prereq: C&O 230
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: MATH 224B Offered at St. Jerome’ s College.
C&O M2 FS 3 O05 Graph Theory 1 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, MATH 224A
A continuation of C&O 342. Planar graphs and embeddings in other, surfaces. Vertex, edge and face colourings. The four-colour problem. Hamilton cycles. Applications to: scheduling prablems. 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 Antireq: ACTSC 335
Review of linear programming. Shortest path problems. The max-flow and minimum cost-flow problems. A study of the 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
Vector calculus 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.
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
{invention 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. (MATH 2208, 224B are recommended.)
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
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 combinatorics of Eulerian generating
functions, continued fractions, orthogonal
polynomials and the ring of formal
Laurent series. Enumeration under group
action. ; Prereq: C&O 330
Topics covered include error correcting codes, resolvable designs, affine designe, weighing matrices, and their interaction.
Prereq: MATH 324
Course Descriptions 16:99
Mathematics.
Combinatorics and Optimization
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.
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 aigorithms for optimum assignments, matchings, flows, anti-chains and connectivity. Paths, trees and flowers, Min-max rela: tions. Convexification of discrete prob: lems. Vertices and facete of convex polyhedra, The concepts of NP and co-NP. Reducing NP probleme to Integer programming.
Prereq: C&O 351
16:100 Course Descriptions Mathematics.
Combinatorics and Optimization
A study of several techniques for solving integer (linear) programming problems. Cutting planes, implicit enumeration, branch-and-bound. Introduction to Boolean and pseudo-Boolean programming. Applications to problems of optimum routing, site location, set covering and packing, logic and lattice theory.
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. Prereq: One of CS 372, CS 375, 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 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. Ali 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
Topics include: famous construction problems, Mascheroni’s theorem, amicable pairs, perfect numbers and related numbers; Pythagorean triples; some of Archimedes’ great accomplishments: squaring the parabola; estimation of pi, Archimedes’ “Method”, the volume of the sphere; inscribed regular polygons.
Prereq: MATH 130B, 134A/B. (MATH 2208, 224B are recommended.)
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), but may also be taken independently. Topics include: the Fibonacci sequence; prime numbers; Fermat's last theorem; Gaussian integers: Euler’s formula and regular solids; famous problems in geometry. Prereq: MATH 1308, 134A/8. (MATH 2208, 2248 are recommended.) 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 exclusively for students who have been admitted to a Computer Science Major program, and another especially designed for non-specialists who wish to become sophisticated computer users. Within this context, Computer Science Mayor programs include Honours Computer Science, Honours Co-op Computer Science with Electrical Engineering Electives, Honeurs Co-op Computer Science-information Systems Option, Honours Computer Science/Business Administration, Honours Computer Science/ Chartered Accountancy, Honours Computer Science/Management Accounting, and all Joint and Double Honours BMath programs involving Computer Science as one of the majors.
The non-specialists’ courses 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.. These courses are numbered with a middle digit of 0 through 3.
Where resources permit, students with exceptionally high academic standing in other programs may be considered for admission to CS Major courses on an individual basis. To be considered, students should first obtain a written recommendation from their Faculty Advisor and then consult a Computer Science Advisor.
'
2. The Computer Science Department is experiencing tremendous 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 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.
Regular students will not normally be permitted to enrol in Computer Science courses during the Spring term. (See section 5.3 on page 13:26.) Co-op students will not normally be permitted to enrol in Computer Science courses while on @ work term. All other part-time students, as well ag full-time nondegree and post-degree studenis, 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 insté tution should consult a Computer Science Advisor to arrange an appropriate selection of courses.) For courses that are over-subscribed, however, priority for registration will normally be given to students registered full-time in a degree program.
Limits on the number of CS courses students may take concurrently will be published at preregistration time. Normally, all students in first and Second year may preregister for at most one CS course per term, and .students other than Compliter Science Majors may preregister for at most two CS courses per term in third and fourth year.
Computer Science courses may not normally comprise more than onethird of a student's total credits accumulated at the University of Waterloo.
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.
More detailed course descriptions and course guilines are available upon request from the Computer Science Department. Students in faculties other than Mathematics should take particular note of the fotfowing courses: CS 100, 102, 234, 23, 316.
For the purposes of prerequisites, the following courses are normally considered to be equivaient: (CS 234 and 240), (CS 235 and 250), (CS 334 and 340), and (CS 335 and 350/354).
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.