It
SiMON FRASER UNIVERSITY
?
L;-
7^
-r
MEMORANDUM
t
?
From SENATE COMMITTEE ON UNDERGRADUATE
STUDIES
Subject
FACULTY OF SCIENCE NEW COURSE
PROPOSALS - MATHEMATICS 1043, 306-3J
Date
JUNE 26, 1973
308-3,316-3, 343-3, 401-3,
402-3,
,
W -3
MOTION 1: ?
"That Senate approve, as set forth in S.73-79,
the new course proposals in Mathematics,
Mathematics 104-3 - Elementary Computational Methods
Mathematics
306-3 - Introduction to Automata Theory
Mathematics
308-3
- Linear Programming
Mathematics
316-3 -
Numerical Analysis I
Mathematics
343-3 - Combinatorial Aspects of Computing
Mathematics
401-3 - Switching Theory and Logical Design
Mathematics
402-3 - Automata and Formal Languages
Mathematics
403-3
- Algebraic Theory of Automata
Mathematics
416-3 - Numerical Analysis II."
MOTION 2:
?
"That Mathematics 104-3;
Mathematics 306-3; Mathematics
401-3; Mathematics 402-3; and Mathematics 403-3
as now approved, now be included as part of the
Computing Science Program as earlier recommended."
MOTION 3:
?
"That Mathematics 316-3, as now approved, be included
as part of the Computing Science Program as a sub-
stitute for Mathematics 406-3, earlier recommended
for inclusion in the Program."
MOTION 4:
?
"That Mathematics 405-4 be discontinued on the
commencement of Mathematics 306-3; and Mathematics
406-3 be discontinued on the commencement of
Mathematics 316-3."
0
-2-
MOTION 5: ?
"That the two semester time lag requirement be
waived in order that Mathematics 104-3 may be
first offered in the Fall 73-3 semester; and
that Mathematics 306-3, 308-3, 316-3, 401-3,
402-3, 403-3 and 416-3 may be first offered in
or after Spring 74-1 semester."
S
0
From
SENATE COMMITTEE ON UNDERGRADUATE
STUDIES
•1
?
SENATE
I
SiMON FRASER UNIVERSITY
?
i.73-79
MEMORANDUM
FACULTY OF SCIENCE NEW COURSE ?
Subiect
_
PROPOSALS
-
MATHEMATICS 1043 306-3
308-3; 316-3; 343-3; 401-3; 402-3;
Date
JUNE 26, 1973
The Senate Committee on Undergraduate Studies, on recommenda-
tion of the Faculty of Science, has approved new course proposals in
Mathematics, as set forth in SCUS 73-20:
Mathematics 104-3
- Elementary Computational Methods
Mathematics 306-3
- Introduction to Automata Theory
Mathematics 308-3
- Linear Programming
Mathematics 316-3
- Numerical Analysis I
Mathematics 343-3
- Combinatorial Aspects of Computing
Mathematics
401-3
- Switching Theory and Logical Design
Mathematics
402-3
- Automata and Formal Languages
Mathematics 403-3
- Algebraic Theory of Automata
Mathematics 416-3
- Numerical Analysis II.
is
The Committee further recommends that:
1.
Mathematics 104-3; Mathematics 306-3; Mathematics
401-3; Mathematics 402-3; and Mathematics 403-3
as now approved, now be included as part of the
Computing Science Program as earlier recommended.
2.
Mathematics 316-3, as now approved, be included as
part of the Computing Science Program as a substitute
for Mathematics 406-3, earlier recommended for in-
clusion in the Program.
3.
Mathematics 405-4 be discontinued on the commence-
ment of Mathematics 306-3; and Mathematics 406-3 be
discontinued on the commencement of Mathematics 316-3.
4. The two semester time lag requirement be waived in
order that Mathematics 104-3 may be first offered in
the Fall 73-3 semester; and that Mathematics 306-3;
308-3; 316-3; 401-3; 402-3; 403-3 and 416-3 may be
first offered in or after Spring 74-1 semester.
It should be noted that
six
of the courses now recommended
for approval - Mathematics 104; 306; 316; 401; 402; and 403 - will
form part of the Computing Science Program requirements and will also
fulfil requirements in the Mathematics degree programs.
O
-2-
In making its submission, through the Faculty of Science,
to the Senate Committee on Undergraduate Studies, the Mathematics
Department requested that the two semester time lag rule be waived
for a number of courses proposed at this time. The request to the
Committee noted that this was particularly urgent in the cases of
Mathematics 104; Mathematics 306; and Mathematics 316. A copy of
the memorandum from the Chairman of the Mathematics Department is
attached.
In making its recommendation to Senate, SCUS has restricted
its request for permission to offer courses in the Fall semester,
1973 to Mathematics 104 and suggested that the remaining courses,
including Mathematics 306 and 316, be offered first in the Spring
semester,.1974 or subsequently. Its reasons for making this recommen-
dation are as follows:
1.
The Committee felt that a special case could be
made for the offering of Mathematics 104 in the
Fall semester. It is an integral part of the
developing Computing Science Program and failure
to offer it in the Fall semester would seriously
hinder that program and the progress of students
intending to enroll in it. Further, this course
had been submitted earlier, as Computing Science
•
?
124, and would have been in time for normal in-
clusion in the Fall semester course guide had not
a Motion of Senate removed it from that program.
2.
The Committee felt that a special case could not
be made for the offering of Mathematics 306 and
316 during the Fall semester. These are courses
which are being offered as substitutes for courses
currently offered by the Mathematics Department,
Mathematics 405 and 406 respectively. These latter
courses have already been included in the Mathematics
course projections for the Fall semester and, as is
indicated In the memorandum from the Department
Chairman, will be covering substantially the same
material as will be included in Mathematics 306 and
316. The Committee therefore felt that, while it
was prepared to make a special recommendation in
the case of Mathematics 104 and the Registrar's
Office has indicated its willingness to make arrange-
ments for a late inclusion of Mathematics 104 in the
Fall course guide, the confusion and inconvenience
which would result from the late inclusion of further
courses which are already being substantially offered
would be too great to justify a further recommendation
in this case.
0
SiMON FRASER UNIVERSITY
MEMORANDUM
SENATE COMMITTEE ON UNDERGRADUATE
.
From.... Dr. R. W. Lardner
?
STUDIES
?
Chairman
Department of Mathematics
Subject
SGIEDULINGOFNEWMATHEMAT.Csç
0URSES
?
Date ...... .. .... June
?
. 3
With the advent of the new Computer Science program a number of new courses
have been proposed by the Mathematics Department related to this program. These
are Mathematics 104-3, 306-3, 308-3, 31-, 401-3, 402-3, 403-3 and 416-3. All
of these courses except one were described within the Computer Science program
accepted by Senate and it states there that these courses would later be proposed
by the Mathematics Department through the Faculty of Science. These courses form
part of the Computer Science program as well as part of the Mathematics program.
It is essential that three of these courses be offered in the coming Fall
semester (these are 104-3, 306-3 and 316-3). The Department of Mathematics has
requested that Senate give special permission to waive its rules regarding the
two-semester period before a course may be offered and to permit these courses to
be offered in the Fall. Because the July Senate meeting falls after the deadline
for inclusion of courses in the Fall Course Guide it is necessary that Senate give
a special dispensation for the courses to be offered in the Fall. I am writing to
request such special permission.
We also wish to mount most of the remainder of courses listed in the first
paragraph in the Spring semester. I should like to request
.
Senate permission to
do this.
The reasons why it is essential to mount the courses in the Fall are as
follows:
1.
Math 104-3: This is an elementary course in Numerical Methods
designed primarily for students with weak Mathematical
backgrounds. Its primary purpose is to allow students
with weak backgrounds to take the new courses in
Computer Science. As such it is essential to offer it
early in the program. It is also much to be preferred
to offer this course in the Fall semester in order to
permit the relevant students to take it as soon as they
come to the University. Finally, the faculty member who
will teach the course already has a full load of courses
in the Spring semester next year and therefore great
difficulty would be caused if the course has to be post-
poned from the Fall to the Spring.
2.
Math 306-3: This course is essentially the same as an existing course,
Math 405
L
4, and will replace that course. It will become
prerequisite for the courses 401-3, 402-3 and 403-3, one
• ?
of which will be offered in the Spring semester next year.
It will therefore disrupt this sequence of courses if we
were not able to offer 306-3 in the Fall.
./2
SENATE COMMITTEE ON UNDERGRADUATE
?
2
?
June 13, 1973
STUDIES
Al
4. Math 316-3: This course is essentially the same as an existing
course, 406-3, which it will replace. It will become
prerequisite for the new course 416-3 which will be
offered in the Spring next year. Again this sequence
will be disrupted Ff we are not able to offer 316-3
in the Fall.
I understand from Mr. Evans that he is willing to take special measures
to ensure that the first of these courses (104-3) is included in the Fall Course
Guide should it receive approval to be offered at the July Senate meeting.
As far as the other two courses are concerned the Course Guide will state
that the original courses (405-4 and 406-3) will be offered in the Fall. These
will be replaced by the two new courses if they receive Senate approval. As far
as the transition from 406-3 to 316-3 is concerned this will cause no problem
since the credits for the two courses are the same and there is relatively little
change in syllabus. For the transition from 405-4 to 306-3 there is a potential
problem in that it would involve a reduction in the number of credits for the
course. In this 'case what we propose to do is that after pre-registration is
completed the Departmental Assistant approach personally every student who has
registered in 405-4 and the course will be changed to 306-3 if these students
agree unanimously to do so.
R. W. Lardner
RWL:ag
Li
IiUiN 1I(AL1 UNIVERSITY
?
f...)
L.i
MEMORANDUM
o
T
o...
•
Senate Coninittee on tJnd'rgrachate
?
From ?
J.S. Barlow
?
.
Studies .. ............ ........ .... ..........................
Associate Dean of Science
Subjoc$. . . MAThEMATICS . COURSE PROPOSALS
?
Date
?
June .5, 1973...
Attached for the approval of SCUS are the Mathematics course
proposals as approved by the Faculty of Science at its meeting
of May 29, 1973. It should be noted that six of these courses
(Math 104, 306, 316, 401, 402, and 403) will form part of the
Computing Science program requirements, as well as fulfill
requirements in the Mathematics degree programs.
lv
0
-1
0,
,
,NOTES ON THE AUTOMATA THEORY COURSES
These courses, placed as they arc between mathematical logic, computing
and electrical engineering should have motivational and applied aspects
as well as theOretical mathematical interest. Care must he taken to ensure
that persons from computer science are not swamped immediately with
abstract pure mathematics and that students from mathematics are not over-
powered by persons who, having done lots of computing work, may find the
application sides of the course 'familiars
'
in concept even though probably
'new' in detail.
The present mathematics course (Math 405), now being given for the
third time, is based on the premise that it is the only automata course
being regularly offered at this stage. For this reason it has been taken
to have a wide base. The directed studies follow-up course, given twice
at student request, has been thought of as an extension of Math 405 to fill
in certain details and to bring into focus an additional area, namely that
lying between regular sets and recursively enumerable sets, an indication
of a motivation for the extension being given in terms of a consideration
of methods of sequence generation and an analysis of sentence structure
(c.f. Post, Chomsky). Consideration of the concept of calculation has
entered into the course but not very deeply.
The course pattern now suggested first replaces Math 405 by a 300
level course with approximately the same material. Differences between
Math 405 and the new course would be that in the new course there is
i)
a slight increase in the theory of finite automata - at the
moment Math 405 fails to deal with minimization work except
at a very superficial level
ii)
a decrease in basic Turing Machine theory - the students will
have met Turing Machines in CS 100
iii)
an increase at the end of the course to include 'program
machines' which conceptually lie between Turing Machines
and ordinary computers.
The course will act as a better basis than Math 405 for later courses on
switching theory and algebraic automata theory. Further,
in
modifying the
syllabus, account has been taken of the fact that the students should, in
• ?
view of the content of CS 100, enter the course better acquainted with
relevant background material than has previously been the case.
-
?
2
..' ?
.-'
2
In the new proposal, Math 306-3 is intended to act as a foundation for
three follow-up courses, one on switching theory, one on formal languages
and automata, and one on algebraic automata theory.
The switching theory course is thought as presenting a theoretical
background to some of the techniques involved in the design of logical
circuits. ?
The book chosen as a "possible text" is written by professors
of Electrical Engineering and this was a deliberate choice in the sense
that it is hoped that the course will '
help bridge the gap between the more
theoretical aspects of circuit design and some of the problems involved
in practical hardware construction. ?
The fact that some work was done on
McCulloch-Pitts nets in Math 306-3 should prove useful to students taking
Math 401-3.
The formal languages and automata theory course (Math 402-3) is similar
to a course offered twice before under directed studies/honours essay
numbers in the Mathematics Department.
?
It develops the theory of context-
sensitive and context-free languages, relating them to regular and recursively
S
enumerable languages.
?
It also provides a theoretical background for a study
has ?
done ? in
of some of the work which
?
been ?
or is being attempted ?
the field
of sentence recognition in natural and formal languages.
?
Considering, as
it also does, modified and restricted forms of Turing machines, the course
acts as a suitable point for introduction of aspects of calculation complexity
(time and tape forms).
The final course, Math 403-3, on algebraic theory of automata is intended
to deal at an abstract level with the close connections between automata
theory and certain aspects of semigroup theory (and group theory). ?
A
serious algebra prerequisite is desirable (from knowledge and maturity
considerations). ?
The course is envisioned as one which will be taken by
persons specializing in Pure Mathematics and Computer Science but not
necessarily by those concerned more with the central areas of Computer
Science and almost certainly not by those concerned mainly with Applied
Computer Science.
?
Although mathematically the most specialized of the
courses suggested, its importance within Computer Science should probably
not be underestimated, for concepts introduced within modern advanced
- ?
3
'S
.
automata theory are frequently expressed in an abstract algebraic format.
In summary, the four (4) courses are cons:idered to be undergraduate
ones, starting with a widely based foundational one with intuitive,
practical and mathematical content and then extending to include a substantial
amount of basic work in each of three different but related fields.
.
.
4
LAI
FACULTY OF SCIENCE
NEW COURSE PROPOSAL
CALENDAR INFORMATION
Department:
Mathematics*
?
Course Number:
104_3*
Titie:*Elementary
Computational
Sub-title or Description:
?
Methods
An introductory course in numerical methods and various applications.
Credit Hours: 3
?
Vector Description:
2-0-2
Pre-requisite(s):
Mathematics 11 (B.C. High Schools) and knowledge of a
programming language (e.g., Mathematics
106-3
orComputing Science 102-2).
II ?
ENROLMENT AND SCHEDULING
Estimated Enrolment:
?
30
per offering
?
-
Semester Offered (e.g. Yearly, every Spring; twice yearly, Fall and
Spring):
Yearly, every Fall
.
or Spring
When course will first be offered:
Fall 73
or Spring
74
III ?
JUSTIFICATION
A.
What is the detailed description of the course including differentiation
from lower level courses, from similar courses in the same department
and from courses in other departments in the University?
Many fields, for example - Biology, Chemistry, Physics, Psychology,
Econojnics, deal with problems which are not amenable to analytic solution.
This course provides background for some of the necessary nupierical methods
for solving problems of this nature. No similar course is offered by this
or any other department in the University.
B.
What is the range of topics that may be dealt with in the course?
See attached syllabus - page four.
?
r
5
rkqsr^
d.
C.
How
does this course fit the goals of the department?
This course will have an
important position
in
the Computing Science
program. It will also provide a useful service
to
students in other
disciplines who wish to learn elementary computational techniques.
D.
How does this course affect degree requirements?
This course has no direct effect on de
gree
requirements, except that
majors in computing science will be reauired to have a mathematics
background at least equivalent to this course.
E.
What are the calendar changes necessary to reflect the addition of
this course?
New entries in the Mathematics and
Compu t ing Science
sections of the
calendar.
F.
What course, if any, is being dropped from the calendar if this
course is approved?
Mathematics 205-3
has
already been dropped from the calendar.
G.
What is the nature of student demand for this course?
As previously stated,
many
fields require some knowledge of
elementary numerical techniques. Since this will be a new course
and
no similar course has been offered,
it
is difficult to draw
comparisons.
H.
Other reasons for introducing the course.
IV
?
BUDGETARY
AND
SPACE FACTORS
A. Which faculty will be available to teach this course?
G.A.C.
Graham, E.
Pechlaner,
R.
Russell
r.
6
Page 3
B.
What are the special space and/or equipment requirements for
this course?
Computer time.
C.
Any other budgetary implications of mounting this course:
None.
.
i *0
r..
7
Page 4
S
ELEMENTARY COMPUTATIONAL METHODS
CONCEPT OF A NUMERICAL METHOD: what it means to and how to
numerically guess the solution to a problem.
ITERATIVE METHODS: heuristic explanation with examples, (including
a brief introduction to derivatives).
APPROXIMATION METHODS: including their relation to iteration.
LINEAR EQUATIONS: what they are and when they arise.
LINEAR PROGRAMMING PROBLEMS: mainly aspects related to computation.
MONTE-CARLO METHODS
is
Suggested textbooks: (Topics from) ELEMENTARY COMPUTER APPLICATIONS by
Barrodale, Roberts and Ehle. (John Wiley and Sons)
(Topics from) COMPUTER-ORIENTED MATHEMATICS by
L.D. Kovach (Holden Day 1964)
(Topics from) NUMERICAL ANALYSIS by I.A. Dodes and
S.L. Gratzer (Hayden)
S
SFACULTY OF SCIENCE
NEWCOURSE PROPOSAL
?
I ?
CALENDAR INFORMATION
Department:
Mathematics*
?
?
Course Number:
306_3* Titlerntroduction to
Automata Theorti
Sub-title or Description:
Finite-state
machines, McCulloch-Pitts nets and the
eauivalence of these concepts;
recognition of sequences by finite state machines and by nets; regular expressions
Kleene's
theorem.
Turing machines; a universal Turing machine; unsolvability of
the
halting
problem
and of some related problems; Turing computability and
recursivity; program machines.-
I ?
Credit Hours:
3 ?
Vector Description: ?
3-1-0
Prc.requisi t
e(s): Computing Science
100-3, and fifth
level
standing or permission
the
instructor. Students who have obtained credit for Mathematics 405-4 cannot
obtain credit for
Mathematics
306-3
?
II
?
ENROLMENT AND SCHEDULING
Estimated Enrolment:
25 per offering.
Semester Offered (e.g. Yearly, every Spring; twice yearly, Fall
and
Spring):
Yearly, every Fall
When course will first be offered:
?
Fall 73
?
III ?
JUSTIFICATION
A.
What is the detailed description of the course including differentiation
from lower level courses, from similar courses in the same department
and from courses in other departments in the University?
This course is a widely
based
foundational one which replaces the present
Mathematics 405-4
(Theory
of Computability).
No
similar coarse is offered
by
this or any other Department in
the
University.
B.
What is the range of topics that may be dealt with in the course?
See attached syllabus -
page four.
?
-
9
Page 2
is
C. How
does this course fit the goals of the department?
This course has an important position in the proposed
Computing
Science program,
being the basic course for the automata theory section of that pro
gram. The
present automata theory course, Mathematics 405-4 was the only automata theory
course being offered. The new course follows essentially the same syllabus but
takes into account the increase in prior preparation of students for such work,
since they
1llw ?
eJurre5c
For majors or honours students in
Computing
Science, this course may be used
in partial satisfaction of degree requiements. For Mathematics students,
it will increase the selection of upper level courses which can be used to
satisfy their degree requirements.
E.
What are the calendar changes necessary to reflect the addition of
•
this course?
New entries in the Mathematics and
Computing Science
sections of the calendar.
F.
What course, if any,
is
being dropped from the calendar if this
?
?
course
is
approved? ?
-
Mathematics 405-4.
C. What is the nature of student demand for this course?
Even without a program in
Computing
Science, Mathematics 405-4 has had a
regular enrolment of about 10 students per year. There should now be
I ?
an increased demand.
H.
Other reasons for introducing the course.
The course will also be used for students whose main area of interest is
mathematical logic and who wish to study applications of that subject in a
computing context.
IV ?
BUDGETARY AND SPACE FACTORS
A. Which faculty will be available to teach this course?
A. Freedman, R. Harrop, A. Lachlan
10
Page 3
B.
What are the special space and/or equipment requirements for
this course?
Computing time.
C.
Any other budgetary implicati
l
on
'—
s of mounting this course:
None - replacement course.
H.
Q
it
Page 4
INTRODUCTION TO AUTOMATA THEORY
FINITE-STATE
MACHINES:
Equivalent histories and states; state-transition
diagrams; limitations of calculation possibilities with finite-state machines.
Minimization of number of states.
NEURAL NETS:
McCulloch-Pitts nets; equivalence of neural nets with finite-
state machines.
REGULAR EXPRESSIONS:
Recognition of sequences by finite automata and nets;
regular expressions; Kleene's theorem.
TURING
MACHINES:
Review of definition of Turing machines; examples of
computations by Turing machines; universal machines; unsolvability of the
halting problem and some related problems; primitive recursive functions;
(total and) partial recursive functions and equivalence to Turing computability.
PROGRAM MACHINES:
Concept of program machine; equivalence of recursive
functions and program machine computable functions.
Suggested Textbook: COMPUTATION: FINITE AND INFINITE MACHINES by
?
Minsky (Prentice-Hall)
I]
fli
Li
12
S
?
FACULTY OF SCIENCE
NEW COURSE PROPOSAL
?
I
?
CALENDAR INFORMATION
Department:
Mathematics
?
?
Course Number:
308 ?
Title:
Linear
Programming
Sub-title or Description:
Theory and applications of linear programming. Geometric and
computational considerations.
Credit Hours:
3 ?
Vector Description:
3-1-0
Pre-requisite(s):
Mathematics 232-3 and preferably, knowledge of a
programming language (e.g., Mathematics 106-3 orComputing Science 102-2).
?
II ?
ENROLMENT AND SCHEDULING
5
?
Estimated Enrolment:
?
30 per offering.
Semester Offered (e.g. Yearly, every Spring; twice yearly, Fall and
Spring):
Yearly, every Fall or Spring
When course will first be offered:
Fall 73 or Spring 74
?
III ?
JUSTIFICATION
A. What is the detailed description of the course including differentiation
from lower level courses, from similar courses in the same department
and from courses in other departments in the University?
r.
The course will explore in detail the relationship between the
mathematical foundations of linear programming and applications.
No similar course is offered by this Department or any other in
the Upiversity.
B. What is the range of topics that may be dealt with in the course?
See attached syllabus - page four
13
fr'age £
ii
-
C. How does this course fit the goals of the department?
In
addition to those courses primarily concerned with mathematical
theory, the Department wishes to offer courses which will enable
students to learn skills which could be applied to concrete problems
they might encounter either in other disciplines or in industry.
D. How does this course affect degree requirements?
This course has
no
direct effect on degree requirements. However, for
mathematics majors and honours q.tuqents, it will increase the selection
of upper level courses they may take to complete their requirements.
It also will provide a useful option for those students who wish to
take a minor in mathematics.
B. What are the calendar changes necessary to reflect the addition of
this course?
New entry.
F.
What course, if any, is being dropped from the calendar if this
course is approved?
None.
G.
What is the nature of student demand for this course?
The Department has offered 'linear programming' as directed studies
courses in previous semesters, with enrollments of 10 - 20 per
offering.
H.
Other reasons for introducing the course.
The course will be useful for mathematics students who are interested in
statistics and computing and their relationship to other fields.
IV
?
BUDGETARY AND SPACE FACTORS
A. Which faculty will
be available
to teach this course?
B. Aispach, D. Mallory, R. Lardner, R. Ruse1l
?
MM
1
14
Page 3
•H'
B.
What are the special space and/or equipment requirements for
this course?
Computer time.
C.
Any other budgetary implications of mounting this course:
The teaching of Mathematics 106-3 (Fortran) is being phased
out with the introduction of the new
Computing
Science program.
Consequently, those resources so freed will be used in the
teaching of mathematics courses related to
computing
science.
!
0
ie
•15
Page 4
LINEAR PROGRAMMING
1.
Convex sets in n-dimensional spaces.
2.
Logics, models and applications of linear programming.
3.
Simplex method - geometric and economic interpretation.
4.
Simplex method as a computational procedure.
5.
Shadow prices, imputed values, duality theorem.
6.
Sensitivity algorithm.
7.
Parametric programming.
8.
Decomposition algorithm.
9.
Variants of simplex method.
Suggested textbook: INTRODUCTION TO LINEAR PROGRAMMING by C. Kim
(Holt, Rinehart and Winston, 1971)
0
FACULTY OF SCIENCE
NEW COURSE PROPOSAL
I
?
CALENDAR INFORMATION
Deiartrncnt:
Mathernatics*
?
Course Number: 316,3*
Title:
*Numerical
Analysis I
Sub-title or Description:
A presentation of the problems commonly arisin
q
in numerical
analysis and the basic methods for their solution.
Credit Hours:
3 ?
Vector Description:3-1-0
Pre-requisite(s):
Mathematics 152-3 and
232-3 and knowledge of a programming
language (e.g., Mathematics
106-3
or Computing Science 102-2).
H.
II ?
ENROLMENT AND SCHEDULING
Estimated Enrolment:
?
15-20 per offering.
Semester Offered (e.g.
Yearly,
every Spring; twice yearly, Fall and
Spring):
Yearly, every Fall
When course will first be offered:
Fall 74
III
?
JUSTIFICATION
A.
What is the detailed description of the course including differentiation
from lower level courses, from similar courses in the same department
and from courses in other departments in the University?
The course is concerned with the practical solution of scientific problems on
computers, with emphasis on the various available algorithms. Emphasis is
placed on the theoretical considerations such as rate of converáence comparisons
as well as on practical considerations involvin
g
actual implementation of the
codes. This course will replace Mathematics
406-3.
B.
What is the range of topics that may be dealt with in the course?
0
?
1
See attached syllabus .- page four.
- ?
171
I'age
C.
How does this course fit the goals of the department?
A review of the Department's present numerical analysis course (Mathematics 406-3)
led to the conclusion that it was impossible to teach the subject satisfactoril
y i
a one-semester course. The revisions which led to this course proposal (and to th
one submitted for Mathematics 416-4) will provide students with a better under-
standing of numerical analysis.
,
It will also enable those who take the course to
see a major application of theortica1. tools to numericaL applications.
D.
How dOes this course affect aegree requirements
This course has no direct effect on degree requirements. However, for mathematics
majors and honours students, it will increase the selection of upper level courses
they may take to satisfy their degree requirements. It will also provide an
interesting and useful option for those students completing a minor program in
mathematics and for students majoring in
computing
science.
E.
What are the calendar changes necessary to reflect the addition of
this course?
New entries in the Mathematics and
Computing
Science sections of the calendar.
F.
What course s
if any, is being dropped from the calendar if this
course is approved?
.1
Mathematics 406-3.
G.
What is the nature of student demand for this course?
The numerical analysis course offered previously (Math 406) had an enrollment
of 10-15 students per offering. By replacing certain advanced topics with
those which are more easily accessible, it is possible to lower the prereo'uisites.
This should make the course more attractive to students, both in mathematics and
in
computing
science.
H.
Other reasons for introducing the course.
• ? IV ?
' BUDGETARY AND SPACE FACTORS
A. Which faculty will be available to teach this course?
G.A.C. Graham, E. Pechianer, R. Russell
?
• : ?
'r..
Page
3
B.
What are the special space and/or equipment requirements for
this course?
Computer time.
C.
Any other
budgetary implications of mounting this course:
None.
.
19
* ?
4
Page 4
NUMERICAL ANALYSIS I
1.
NUMBER SYSTEMS AND ERRORS: representation of .numbers; error propagation
and error estimation.................1 112 weeks.
2.
SOLUTION OF NONLINEAR EQUATIONS: bisection, modified regula falsi, secant
method, Newton's method; fixed
pointiteration,
Aitken's algorithm, Steffensen's
iteration; Muller's method...........2 112 weeks.
3.
SYSTEMS OF LINEAR EQUATIONS: elimination method - factorization, pivoting
strategy, compact schemes, iterative improvement, inverse calculation;
iterative methods; eigenvalue problem... .3 weeks.
4.
INTERPOLATING AND APPROXIMATION: interpolation polynomial - Lagrange, Newton,
divided difference forms, error formula; piecewise polynomial interpolation
and approximation; data fitting, orthogonal polynomials, least-squares
approximation, Chebyshev approximation. . .4 weeks.
5.
DIFFERENTIAION AND INTEGRATION: numerical differentiaion; numerical
integration -
composite rules, Gaussian quadratures, Romberg integration.
SUGGESTED TEXTBOOK: ELEMENTARY NUMERICAL ANALYSIS by Conte and deBoor
(McGraw Hill, 1972)
S
.
S
-
?
20
6C
FACULTY OF SCIENCE
NEW COURSE PROPOSAL
CALENDAR INFORMATION
Department:
Mathematics
?
Course Number:
?
Title:
Combinatorial
Aspects of
Sub-title or Description:
?
Computing
This course is primarily concerned with computational applications
of combinatorial theory.
Credit Hours:
3 ?
Vector Description:
31-0
Pre-requisite(s):
Mathematics
232-3 and either knowledge of a programming
language or Mathematics 106-3 or Computing Science 102-2.
?
II ?
ENROLMENT AND SCHEDULING
Estimated Enrolment:
?
15
per offering
Semester Offered (e.g. Yearly, every Spring; twice yearly, Fall and
Spring):
Yearly, every Fall or Spring
When course will first be offered:
?
Fall 74
or Spring 75
?
III
?
JUSTIFICATION
A.
What is the detailed description of the course including differentiation
from lower level courses, from similar courses in the same department
and from courses in other departments in the University?
The Mathematics Department offers no similar course and neither does
any other Department in the University.
B.
What is
the range of topics that may be dealt with in the course?
.
?
see attached syllabus - page four.
21:
Page ;
C.
How
does this course fit the goals of the department?
This course will provide students who are interested in pure and
applied mathematics with an opportunity to relate theoretical
knowledge to practical considerations.
D.
How does this course affect degree requirements?
This course has no direct effect on degree requirements, However, for
mathematics majors and honours students, it will increase the selection
of upper level courses they may take to satisfy their degree requirements,
It will also provide an interesting option for those students completing
a minor program in mathematics.
E.
What are the calendar changes necessary to reflect the addition of
this course?
New entry.
F.
What course, if any, is being dropped from the calendar if this
course is approved?
None, specifically - see
comment on page three.
C. What is the nature of student demand for this course?
Since this is a new course in a new area of mathematics it is impossible to
make an accurate assessment of student demand at this time. However, rapidly-
growing interest in the subject, particularly in industry, would seem to
forecast a reasonable demand.
H. Other reasons for introducing the course.
Although the course proposed is a mathematics course, it is hoped that
students in Computing Science would find it useful as well as interesting.
IV
?
BUDGETARY
AND
SPACE FACTORS
A. Which faculty will be available to teach this course?
B.R. Aispach, T.C. Bzown ?
r.
Mr^
Page 3
B.
What are the special space and/or equipment requirements for
this course?
Computer time.
C.
Any other budgetary implications of mounting this course:
The teaching of Mathematics 106-3 (Fortran) is being phased
out with the introduction of the new
Computing
Science
program.
Consequently, those resources so freed will be used to teach
mathematics courses related to
computing
science.
r-.
23
Page 4
.
COMBINATORIAL
ASPECTS OF COMPUTING
1.
Representations of integers.
2.
Representations of sets.
3.
Enumeration and counting techniques: back track methods,
inclusion-exclusion
, and Polya's method.
4.
searching in linearly ordered sets.
5.
Trees and their uses in searching and traversal problems.
6.
Algorithms for graph theory: path problems, flow problems,
and matching problems.
QSUGGESTED TEXTBOOK: ELEMENTS OF
COMBINATORIAL
COMPUTING by M.B. Wells
(Per gamon)
24
FACULTY OF SCIENCE
NEW COURSE PROPOSAL
I
?
CALENDAR INFORMATION
Department:
Mathematics* ?
Course Number:
401_3*
Title:
*5jjflg
Theory
and Logical
Sub-title or Description:
?
Design
Mathematical foundations, switching devices, minimization of Boolean functions,
tabular minimization and multiple-output circuits. Se
q
uential circuits, pulse-
mode and fundamental mode sequential circuits. Introduction to threshold logic.
U
Credit
3 ?
Hours:
Vector Description:
3 -1-0
Pre-requisite(s):
Computing Science 102-2 (or Mathematics 106-3) and
Mathematics 306-3
?
(or Mathematics
405-4).
?
II ?
ENROLMENT AND SCHEDULING
Estimated Enrolment:
15 per offering.
Semester Offered (e.g. Yearly, every Spring; twice yearly, Fall and
Spring):
Initially, Spring every three years.
When course will first be offered:
Sprinq 75
?
III ?
JUSTIFICATION
A.
What is the detailed description of the course including differentiation
from lower level courses, from similar courses in the same department
and from courses in other departments in the University?
This course will present a theoretical background at a mathematical/automata
theory level to some of the techniques involved in the design of logical
circuit's. No similar course it offered by this Department or4any other
in the University.
B.
What is the range of topics that may be dealt with in the course?
See attached syllabus - page four.
25
Page 2
it ?
C. How does this course fit the goals of the department?
This course forms an integral part of the development of the Computing
Science program at this University, and in particular, of the automata
theory section of that program.
D.
How does this course affect degree requirements?
This course has no effect on degree requirements. However, for majors
or honours students in ComputingScience, it may be used to partially
satisfy degree requirements, For Mathematics students, it will increase
the selection of upper level courses which can be used to satisfy their
degree requirements.
E.
What are the calendar changes necessary to reflect the addition of
this course?
New entries, in the Mathematics and Computing Science sections of the
calendar.
F. What course, if any, is being dropped from the calendar if this
course is approved?
None
G.
What is the nature of student demand for this course?
Since this is a new course, it is difficult to assess what the actual
student demand will be, but it is expected that the demand will be
a natural outgrowth of the Computing Science program.
H.
Other reasons for introducing the course.
IV ?
BUDGETARY AND SPACE FACTORS
A. Which faculty will be available to teach this course?
R. Harrop
26
Page 3
B. What are the special space and/or equipment requirements for
this course?
Computer Time
C. Any other budgetary implicatIons of mounting this course:
None.
r-.
27
Page 4
I
SWITCHING THEORY AND LOGICAL DESIGN
MATHEMATICAL FOUNDATIONS: Truth functions
and
review of Boolean algebra.
SWITCHING DEVICES: Switches
and
relays; diode transistor logic, resistor
transistor logic; NAND and NOR circuits; flip-flops.
TABULAR MINIMIZATION AND MULTIPLE-OUTPUT CIRCUITS: The Quine-MCK1 uskey
method for determining prime implicants; minimization
and
prime implicants
for multiple-output circuits.
SEQUENTIAL CIRCUITS: Counters; timing in clocked circuits;, transition tables
and state diagrams; simplification
of circuits; state assignment and excitation
equations; incompletely specified sequential circuits.
PULSE-MODE AND FUNDAMENTAL MODE SEQUENTIAL CIRCUITS: Flow tables and
transition tables; analysis and synthesis of circuits; cycles and races.
INTRODUCTION TO THRESHOLD LOGIC: Linear separability and the use of
threshold logic devices.
Suggested textbook: INTRODUCTION TO SWITCHING THEORY
AND LOGICAL DESIGN by
F.M. Hill and G.R. Peterson, (Wiley)
L_^
28
FACULTY OF SCIENCE
NEW COURSE PROPOSAL
I ?
CALENDAR INFORMATION
Department:
- ?
Mathematics*
?
Course Number:
402_3*
Title:
Automata
Formal
and
Sub-title or Description:
?
Languages
Languages and grammars. Finite automata and regular grammars; context-free
grammars and pushdown automata; Turing machines and recursively enumerable
(type 0) languages;
context-sensitive
grammars and linear bounded automata.
Operations on languages. Complexity of calculation. Deterministic pushdown
automata.
Credit Hours:
?
3
?
Vector Description: ?
3-1-0
Pre-requisite(s):
Mathematics
306-3
?
(or Mathematics
405-4),
or permission of the Mathematics Department.
II ?
ENROLMENT AND SCHEDULING
Estimated Enrolment:
?
15
per offering
Semester Offered (e.g. Yearly,
every
Spring; twice
yearly, Fall and
Spring):
Initially, Spring, every three years.
When course will first be offered:
Spring 74
III ?
JUSTIFICATION
A.
What is the detailed description of the course including differentiation
from lower level courses, from similar courses in the same department
and from courses in other departments in the University?
The course develops the theory of context-sensitive and context-free lan
g uages, relati
them to regular and recursively enumerable languages. It also provides a theoretical
background for.a study of some of the work which has been done or is bein
g
done in
the field of sentence recognition in natural and formal lan
q uages. Considering as it
also does, modified and restricted forms of Turing machines, the course acts as a
suitable point for the introduction of aspects of calculation com
p lexit y . No similar
B.
What is
the range of topics that may be dealt with in the course?
course is
now offere
r-
See attached syllabus - page four.
?
9.
Page 2
11
?
0
?
C. How does this course fit the goals of the department?
This course forms an integral part of the development of the Computing Science
program at this University, and in particular, of the automata theory section
of that program. The course should also enhance the Mathematics Department's
service function with respect to students interested in the linguistics field
at an advanced level.
D.
How does this course affect degree requirements?
This course has no direct effect on degree requirements. However, for
majors or honours students in Computing Science, it may be used to
partially satisfy degree requirements. For Mathematics students, it
will increase the selection of upper level courses which can be used
to satisfy their degree reciuirments.
E.
What are the calendar changes necessary to reflect the addition of
this course?
New entries, in the Mathematics andComputing Science sections of the calendar.
F.
What course, if any, is being dropped from the calendar if this
?
4
?
course is approved?
None.
G.
What is the nature of student demand for this course?
A course of this nature has already been given, at student request,
under selected topics/honors essay numbers during two of the three
years in which Math 405-4 (Theory of Computability) has been offered.
It was again requested for the Spring semester 73, but could not be
offered.
H.
Other reasons for introducing the course.
IV ?
BUDGETARY AND SPACE FACTORS
A. Which faculty will be available to teach this course?
?
P.
?
R.
Harrop
?
r.
30
Page 3
B.
What are the special space and/or equipment requirements for
this course?
Computer time.
C.
Any other budgetary imp1ications of mounting this course:
Although this is not a replacement course, the Mathematics Department
will be able to mount it during the next academic year, since there
will be no selected topics courses offerin
g during that time. (For
the 72-73 academic year, 8 hours of selected topics courses were
mounted.)
C
31
Page 4
S
AUTOMATA AND FORMAL LANGUAGES
LANGUAGES AND GRAMMARS: Concepts of language and grammar including reference
to natural and formal languages and to regular, context-free, context-sensitive
and recursively enumerable (type Q) grammars and their related languages.
FINITE AUTOMATA AND REGULAR GRAMMARS: Deterministic and non-deterministic finite
automata, relation to regular grammars; closure and decidability properties. Two-
way finite automata.
CONTEXT-FREE GRAMMARS AND PUSHDOWN AUTOMATA: Derivation trees; Chomsky and Greibach
normal forms. The 'uvwxy' theorem; self-embedding property; pushdown automata in
empty store and accepting state form; equivalence of the concepts of context-free
language and language accepted by (non-deterministic) pushdown automaton. Examples
of 'closure' and 'decidäbility' results.
TURING MACHINES AND RECURSIVELY ENUMERABLE (Type 0) LANGUAGES: Review of the
definition and elementary properties of Turing machines; modified forms of the
definition including, for example, the use of storage tapes, multi-track tapes,
and read only inputs; Turing machines and type 0 grammars.
. ?
CONTEXT-SENSITIVE GRAMMARS AND LINEAR BOUNDED AUTOMATA: Languages determined by
linear bounded automata; equivalence to context-sensitive languages; the context-
sensitive languages as a proper subclass of the class of recursive languages.
OPERATIONS ON LANGUAGES: Consideration of closure of properties of regular,
context-free, context-sensitive and recursively enumerable languages under
operations such as union, intersection, complementation,
concatenation,
reversal,
and *..closure
COMPLEXITY OF CALCULATION: Consideration of time and tape bounded Turing machines
and of time and tape complexity classes.
DETERMINISTIC PUSHDOWN AUTOMATA: Definition of deterministic pushdown automata and
an example of a context-free language which-is not definable using a deterministic
pushdown automaton. ?
-
Suggested Textbook: FORMAL LANGUAGES AND THEIR RELATION TO AUTOMATA by
J.E. Hoperoft and J.D. Ulman (Addison Wesley)
.
32
FACULTY OF SCIENCE
NEW COURSE PROPOSAL
I ?
CALENDAR INFORMATION
Department:
Mathematics*
?
Course Number:
403_3*
Title:
Algebraic Theory
of
Automata*
Sub-title or Description:
This course gives a development within an abstract algebraic context
of several
concepts introduced in Mathematics 306-3. Algebraic preliminaries. Semiautomata,
recognizers, regular expressions, coverings of automata.
Credit Hours:
?
3
?
Vector Description:
3-1-0
Pro-requisite(s):
Mathematics 306-3
?
(or Mathematics
405-4),
and Mathematics 432-4; or. permission of the Mathematics Department.
II ?
ENROLMENT AND SCHEDULING
1.
?
Estimated Enrolment:
?
15
per offering.
Semester Offered (e.g. Yearly, every Spring; twice yearly, Fall and
Spring):
Initially, Spring, every three years.
When course will first be offered:
Spring 76.
JUSTIFICATION
A.
What is the detailed description of the course including differentiation
from lower level courses, from similar courses in the same department
and from courses in other departments in the University?
This course is intended to deal at an abstract level with the close
connections between automata theory and certain aspects of pemigroup
theory (and group theory). No similar course is offered by this or
any other Department in the University.
B.
What is the range of topics that may be dealt with in the course?
He
?
See attached syllabus - page four.
33
Page 2
C.
How does this course fit the goals of the department?
This course forms an integral part of the development of the Computingscience proqram at
this University, and in particular, of the automata theory section of that program. The
course will be taken by those specializaing in pure mathematics and computer science, but
not necessarily by those concerned with the central areas of Computing Science. Mathematica
it is the most specialized of the automata theory courses proposed. Concepts introduced
within modern advanced automata theory are expressed in an abstract algebraic format.
D.
How does this course affect degree requirements?
This course has no direct effect on degree requirements. However, for majors or honours
students in
Computing
Science, it may be used to partially satisfy degree requirements.
For Mathematics students, it will increase the selection of upper level courses which can
be used to satisfy degree requirements.
E.
What are the calendar changes necessary to reflect the addition of
this course?
New entries in the Mathematics and
Computing
Science sections of the calendar.
F.
What course, if any, is being dropped from the calendar if this
course is approved?
None
C. What is the nature of student demand for this course?
Study of aspects of this course have been requested by students
in the Mathematics Department's Automata Theory Seminar.
H. Other reasons for introducing the course.
The course forms a useful link with the algebra courses offered by
• ?
the Mathematics Department and there may be students entering the
course with a strong algebra background-who consider the course as
an applied algebra course rather than an abstract
Computing science
course.
IV ?
• BUDGETARY AND SPACE FACTORS
A.
Which faculty will be available to teach this course?
.i.
?
R. Harrop
?
r.
34
Page •3
1 *
?
B. What are the special space and/or equipment requirements for
this course?
Computer time.
C. Any other budgetary implications of mounting this course:
None
Li
H'
?
35
?
F.-.
Page 4
ALGEBRAIC THEORY OF
AUTOMATA
ALGEBRAIC PRELIMINARIES: Review of some aspects of the theory of semi-
groups and the theory of groups including simple groups and direct products
of groups.
SEMIAUTOMATA: Subgroup associated with a semiautomaton, subsemiautomata and
sabseinigroups; homomorphisms of semiautomata; nondeterministic semiautomata.
RECOGNIZERS: Automata as recognizers; regular and nonregular sets;
characterization of regular sets; equivalence of non-deterministic and
deterministic automata; reduction and homomorphisms of automata.
REGULAR EXPRESSIONS: Kleene's theorem; equality of regular expressions;
axioms systems for the algebra of regular expressions; canonical form of
a regular expression.
COVERINGS OF AUTOMATA: Moore and Mealy machines; coverings of automata
and of semiautomata. Direct product and cascade product of automata;
preinutation-reset and grouplike semiautomata; covering of reset and group-
like semiautomata; theory of Krone and Rhodes.
Suggested Textbook:
ALGEBRAIC THEORY
OF AUTOMATA by Ginzburg
(Academic Press, 1968)
.
S
L4
36
FACULTY OF SCIENCE
NEW COURSE PROPOSAL
I
?
CALENDAR INFORMATION
Department:
Mathematics ?
Course Number:
416-3
Title: Numerical
Analysis
II
Sub-title or Description:
The
numerical solution of ordinary differential
equations
and elliptic,
hyperbolic and parabolic partial differential equations
will
be
considered.
Credit Hours:
3 ?
Vector Description:
31.0
Pre-requisite(s):
Mathematics 316-3
?
and
Mathematics
352-2.
II ?
ENROLMENT AND SCHEDULING
Estimated Enrolment:
15 per offering
Semester Offered (e.g. Yearly, every Spring; twice yearly, Fall and
Spring):
Alternate
years in the Spring.
When course will first be of
fered:Spring 75
III
?
JUSTIFICATION
A.
What is the detailed description of the course including differentiation
from lower level courses, from similar courses in the same department
and from courses in other departments in the University?
Students
with some knowledge of differential equations will be introduced to a
number of
methods
for
their
numerical solution. The advantages of the various
methods
for solving ordinar
y
differential equations will be compared. For parti
differe.nti1 equations, each
type of problem
will be emphasized. No
similar co
is now
offered by this
or any, other department
in the
University.
B.
What is the range of topics that
may be dealt with in the course?
See
attached
syllabus - page four.
37
rugv L
C.
How does this course fit the goals of the department?
This course will allow an in-depth treatment of some of the aspects
of numerical analysis which could not be covered in previous courses. It
is an advanced course, primarily for mathematics students with strong
interest in differential equations or numerical methods.
D.
How does this course affect degree requirements?
This course has no direct effect on degree requirements. However, for mathematics
majors and honours students, it will increase the selection of upper level courses
they may take to satisfy their degree requirements.
E.
What are the calendar changes necessary to reflect the addition of
this course?
? -
New entry.
F. What course, if
any, is being dropped
from the calendar if this
course is approved?
?
-
None.
G.
What is the nature of student
demand for this course?
In addition to mathematics students, it is hoped that those outside mathematics
with backgrounds in scientific applications of computing will be attracted to
the course.
H.
Other reasons for introducing the course.
--
?
- ---------------. nnnr
IV ?
BUUWIAI(Y PLNL)
A.
Which faculty will be available to teach this course?
R. Russell.
38
---
Page 3
B.
What are the special, space and/or equipment requirements for
this course?
Computing time.
C.
Any other budgetary implications of mounting this course:
Each year, the Department plans to alternate the offering of
this course with the offering of Mathematics 413-4 (Ordinary Differential
Equations)
so that there will be no
increase in the total number of
course hours.•
. ?
- %,
Page 4
NUMERICAL ANALYSIS II
1.
SOLUTION OF DIFFERENTIAL EQUATIONS: Taylor series, convergence and
error for Euler's method; Runge-Kutta, Multistep, predictor-corrector
methods; stability, round-off propogation; systems of differential
equations.................4 weeks.
2.
BOUNDARY VALUE PROBLEMS IN ORDINARY DIFFERENTIAL EQUATIONS: initial
value or shooting methods; finite difference methods; Ritz and collocation
methods...................2 weeks.
3.
ELLIPTIC PARTIAL DIFFERENTIAL EQUATIONS: Laplace equation on a rectangle-finite
differences, matrix formulation; iterative methods for solution - GAuS-Seidel,
SOR; ADI..................3 weeks.
4.
PAROBOLIC AND HYPERBOLIC PARTIAL DIFFERENTIAL EQUATIONS: Wave equation - differs
• ?
approximation, convergence, domain of dependence; heat equation - explicit
and implicit methods......3 weeks.
5.
GENERAL THEORY: consistency, convergence and stability......1 week.
SUGGESTED TEXTBOOKS: ELEMENTARY NUMERICAL ANALYSIS by Conte and deBoor;
materia2 from various texts, especially ANALYSIS OF
NUMERICAL METHODS by E. Isaacson and H. B. Keller.
40
