21 courses in the 1986–87 Undergraduate Calendar, read from the scanned original. The text comes from OCR, so check the scanned page before relying on a detail.
Intcoduction to the combinatorics of ordi-
nary generating functions. Introduction to basic graph theory and graphical algorithms.
Prereq: MATH 1308, 134B
Antireq: C&O 220
Also’ offered at St. Jerome's College in Fail 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 approxi-
mation. Applications.
Prereq: MATH 130B, 134B
Students may not enrol in. C&O 270 if they have previously completed, or are . concurrently enrolied in, C&O 350 or 567.
C&O 30 -F 3C (05 Combinatorial Enumeration
The combinatorics of ordinary and @Xpo-.
nential 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 KX O05
Graph Theory 1
An introduction to the ideas, methocs and applications of graph theory. Finding shortest paths and maximum matchings in weighted graphs. Deter- "mining the connectivity of a graph. Prereq: MATH 224A, C&O 230
CRO 43 W 30 05 ~ Graph Theory 2 oe A continuation of C&O 342. Planar - © graphs and embeddings in other surfaces. Vertex, edge and face colourings. The four-coiour problem. Hamilton cycles. Applications to scheduling probtems.
Prereq: C&O 342
A first course in problem formulation
and solution techniques in linear
programming. The’‘simpiéx and revised
simplex methods. Active set formulation
of the simplex method. Theory and
applications of Suality theory. Sensitivity
Analysis, - Prereq: MA 224s ad Antireq: ACTS
Review of linear progr.
_ path problems, The may:flow and
minimum cost-+ ow probipms. A study of the network simplex, augmentation and out-of-kilter algorithms. Applications to problems of transportation, distribution, man-job assignments and A erica path planning..
Prereq: C&O 350.
Vector calculus wah ‘applications to” Newton's method find, trethod of
steepest descant. “dimensional optimization. Intraductio# to constrained optimization, it zthe elements of
Kuhn-Tucker theory ard Lagrange multipliers. : Prereq: MATH 220A, MA
illustrates row ¥ 7S
models and meth of ‘Optimization. dan be usad to 80h Phoblems arising in business, indunydnd Science.
Prereq: C&O 380 Antireg: ACTSC 50 30
Tey
A course in problem solving. 100 pied. lems, are studied. Proslems.are taken mainly from the elementary parts of algebra, geometry, number theory, | combinatorics and probability. -
Prereq: MATH 1308, 1344/8. (2208, 2248, are recommended) '
Although the mathematics for this. course is technically elementary, the course is intended for third and fourth. © year students, and the mathematical maturity of a senior student will be assumed.
C&O 382, 2G 05
Combinatorial Geometry 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 res of different sizes, ine theory of. convex lly’s theorm and will be explored.
athematics for this elementary, the course intended for third and fourthyear si the mathematical matunity.of 4a sehipr student will be assumed, . a
The course is an Bxtension of C&O 330. Thé combi j of Eulerian generating fuactions, inued fractions, orthogonal polynérnials and the ring of: tormal Laurent sevies. Enumeration under group action.
Prereq: C&O 330
Topics covereg include error correcting codes, reselable designs, affine designs, weighing matrices, and their: interaction.
Prereq: MATH 324...
C&O 48 W actos
A course coveting number of applica: tions of computers to. combmatorial -- problems. Gerieral procedures - backtrack prograrnming, generation of permutations, partitions etc. as well as the Solktion of many gpesific problems. Includgs an introductian to computational;complexity. © \
Foye: C&O 230
C&O 439 20. 26 Topics in Combinatorics
An undergreduate seminar in combina-
torics. The primary objective is to study current work in speeific areas of combinatorics. Course content may vary from term to term.
Prereq: Consent of instructor
An in depth study of 1 or 2 topics in graph theory. Course content may vary from term to term. Topics may include planar graphs, extramal 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- , lems, Integer programming. Good aigor-
ithms for optimum assignments, match-
ings, flows, anti-chains and connectivity. Paths, trees and flowers. Min-max rela-
tions. Convexification of discrete prob-
lems. Vertices and facets of convex.
polyhedra. The concepts of NP and
co-NP. Reducing NP problems to integer programming.
Prereq: C&O 351
A study of several techniques for solving integer (linear) programming : Problems. Cutting planes, implicit enumeration, branch-and-bound. introduction to Boolean and pseudo-Boolean prograraming. Applications to problems of optimum routing, site location, set covering and packing, logic and lattice theory.
Prereq: C&O 351
@&O 454 FS 3X O05
Scheduling |
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 constrairtts, with. applications to linear programming and data fitting. Emphasis is on algorithms, numerical considerations and software implemen: tation.
Prereq: One of C&O. 350, CS 337, 375 or consent of instructor.
Cross-listed as CS 473.
An undergraduate seminar in optimization. The ‘primary objéctive is to study recent: work in specific areas ot 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 prograrriming 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
4
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’ "Methad”, the volume of the sphere; inscribed regular polygons.
Prereq: MATH 130B, 134A/B (2208 and 224B are recommended)
Although the mathematics for this course is technically elementary, the course is intended for third and fourttr year students, and the mathematical maturity of a senior student will be assumed. ‘
Course Descriptions 16.97 Mathematics.
Combinatorics and Optimization
A continuation of C&O 480 (History of Mathematics 1), but may. aiso he 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/B (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 @ senior student will be assumed.
Prereq: Consent of department
Computer Science
Course Descriptions
Courses not offered in the current acedemic year are listed at the end of thie section.
Introductory Notes
1. - The Department of Computer Science has 2 distinct streams of courses, 1 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 contexi, Computer Science Major programs include Honours Computer Science, Honours Co-op Computer Science with Electrical Engineering Electives, Honours Co-op Computer Science-information Systams Option, Honours Computer
-— —Seience/Business Administration.
Honours Computer Science/ Chartered Accountancy, Honours Computer Stience/Management Accounting, ail Joint and Double Honours BMath programs involving Computer Science as one of the majors.
The norrspecialists’ courses will not. normally be open to Computer Science Major students, but they will be avaiable to all other students in the University, subject to resource limitations. These courses are
numbered with a middle digital 0’ through 3.
Where resources perrnit,. students 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 recommenda . tion from their Faculty Advisor and then consult a Computer Science
The Computer Science Department ig experiencing tramendous demand for its courses beyond available resources. Thus, accessibility to Computer Science courses cannot be guaranteed to ail 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..
Reguler students wil not normally be permitted to enrol in Computer
- term. (Sae_section 5.3 on page 13.26.) Co-op students wit not normally be permitted to enrof in Computer Science courses while on & work term. Ad other part-time students, as well as full-time nondegree and post-degree students, will normally be imitad to at most 1 Computer Science course per term from the norrspecialist offerings. (Post-degree students on academic leave from their home institution 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 fulltime 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 1 CS course per term, and students other than Computer Science Majors may preragister for at most 2 CS courses par term in third and fourth year.
Computer Science courses may not normally comprise more than onethird of & student's total credits accumulated at the University of Waterloo.
/
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 pre-registration time.
7. More detailed course descriptions and course outlines are available upon request from‘ the Computer Science Department. Students in faculties other than Mathematics should. take particular note of the following courses: CS 100, 102, 234, 235, 316.
8 For the purposes of prerequisites, the following courses are normally ~ considered to be equivalent: (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
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.
Course Descriptions