Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7

SIMON FRASER UNIVERSITY (p

eviously part of

S.85-57)

Vi i V

J%.

To: Senate ?

From:

Senate Committee on

Undergraduate Studies

Subject:

School of Computing Science -

Date:

January 21, 1986

Curriculum Revisions

Action undertaken by the Senate Committee on Undergraduate Studies at its

meeting of January 21, 1986 gives rise to the following motion:

MOTION:

"That Senate approve and recommend approval to the Board of

Governors, as set forth in 5.86-21, the following curriculum

changes:

1) Prerequisite and curriculum revisions including new course

MACM 300-3 Introduction to Formal Languages and Automata

with Applications, and deletion of MACM 306-3 Introduction

to Automata Theory.

11) Changes to Upper Division Degree Requirements for majors.

SIMON FRASER UNIVERSITY

MEMORANDUM

Date...

Jry..,..t96

..................................................

The School of Computing Science and the Department of Mathematics and Statistics have now

reached agreement on a mutually acceptable proposal for curriculum revision in the area of Automata

Theory. Essentially, we have agreed to replace the proposed CMPT 309 course with a jointly-offered

course numbered MACM 300. Although Computing Science has concerns about such joint administra-

tion, we are willing to try it subject to review after 2 years. We therefore propose that SCUS ap-

prove the following motions and forward them to Senate.

I Moved that classical computing science theory be integrated into the Computing Science cur-

riculum as follows.

Space freed up by the removal of formal logic from CMPT

205

be used to introduce

automata theory.

A new course MACM 300-3 (Introduction to Formal Languages and Automata with

Applications) is proposed as a joint offering of the School of Computing Science and the

Department of Mathematics and Statistics and is included in the area of Theoretical Com-

puting Science. See attached course proposal.

MACM 306 (Introduction to Automata Theory), MACM 401 (Switching Theory and Logi-

cal Design) and MACM 402 (Automata and Formal Languages) are eliminated from the

area of Theoretical Computing Science.

The prerequisite statement for CMPT 483 (Parsing and Interpretation) is changed to read:

"Prerequisites: CMPT 205, 275,

383, MACM 300."

The prerequisite statement for MACM 401 (Switching Theory and Logical Design) is

changed to read: "Prerequisites:

CMFI' 101

or 104 (or

103

with a grade of B or higher)

and

MACM300

MACM 306.

Students who have obtained credit for

MATH 401

may not

receive

further credit for

MACM

401."

The prerequisite statement for MACM 402 (Automata and Formal Languages) is changed

to read: Prerequisites:

MACM 300

MACM 306.

Students who have obtained credit for

MATH 402

may not receive further credit for

MACM 402."

MACM 306 is eliminated as a course and is consequently dropped from the table of

Computing Mathematics courses that can be used to satisfy upper division requirements

CMPT-UGCC.86-1:1 ?

Page 1 of 2

TABLE I

Computing Science Concentrations

TABLE I ?

Computing Science Concentrations

in Computing Science.

2. Moved that the Upper Division Degree Requirements for Majors in Computing Science be ap-

proved as

given in

S.85-57.

(Note: this item was referred back to SCUS by Senate at its

December 4, 1985 meeting to be amended as necessary to resolve the problem of CMPT 309.

No amendments are needed, however.)

In terms of the Computing Science upper division requirements. the above motions only require

changes to two of the tables shown in Appendix IV of

S.85-57:

these changes are shown below, corn-

paring the original proposal as shown in

S.85-57

and the revised proposal as described above.

TheoreticalComputing ?

TheoreticalApplications

Algorithmsof

LanguagesAlgorithms

??????

TheoreticalComputing ?

TABLE

Computing Mathematics Courses

MACM 306-3 Introduction to Automata Theory

316-3 Numerical Analysis I

401-3 Switching Theory and Logical Design

402-3 Automata and Formal Languages

MATH 308-3 Linear Programming

343-3 Combinatorial Aspects of Computing

408-3 Discrete Optimization

416-3 Numerical Analysis II

TABLE III

Computing Mathematics Courses

MACM 316-3 Numerical Analysis I

401-3 Switching Theory and Logical Design

402-3 Automata and Formal Languages

MATH 308-3 Linear Programming

343-3 Combinatorial Aspects of Computing

408-3 Discrete Optimization

416-3 Numerical Analysis II

CMPT-UGCC.86-1:1 ?

Page 2 of 2

SiMON FRASER UNIVERSITY

$ ?

MEMORANDUM

•To

.........CUS

Subject

CMPT CURRICULUM REVISION: S 85-57? 

/Dr. R.D. Cameron's memo of January 13, 1986 

G.A.C. Graham, Chairman 

From

.....................................................

Department of Mathematics , Statistics 

an

J

13 January 1985 

Date..................................................... 

This is to acknowledge that I have read and approve of the 

proposals made in Dr. Cameron's memo of January 13, 1986. 

G.A.C. Gra m 

GACG/bcl 

c.c. Dean of Science - Dr. G. Geen 

Dean of Applied Sciences - Dr. D. George 

Appendix 

SENATE COMMITTEE ON UNDERGRADUATE STUDIES 

COURSE PROPOSAL FORM 

?

School of Computing Science 

Dept. of Mathematics ? 

Stati 

?

1.

Calendar Information 

Department: 

Abbreviation Code:MACM Course Number: 

300

Credit Hours: 

3

Vector: 

3-1-0 

Title of Course: 

Introduction to Formal Languages and Automata with Applications 

Calendar Description of Course: 

Languages, grammars,.automata and their applications. Turing machines. 

Computability and undecidability. Complexity theory. 

Nature of Course 

?

Lecture/Tutorial 

Prerequisites (or special instructions): 

CMPT 205 

What course (courses), if any, is being dropped from the calendar if this course is 

approved: 

MACM 306 

2.

Scheduling 

How frequently will 

the course be offered? Twice a year or as required. 

Semester in which the course will first 

be offered? 86-3 

Which of your present faculty would be available to make the proposed offering 

possible: 

?

A. Freedman, C. Godsil, B. Hadley, R. Harrop, A. Liestman, A. Mekler? 

J. Peters, N. Reilly 

3.

Objectives of the Course 

p

To provide both a theoretical and an applied treatment of formal 

languages and automata. 

4.

Budgetary and Space Requirements (for information only) 

What additional 

resources will 

be required in the following areas: 

Faculty 

?

None 

Staff ? 

None 

Library ? 

None 

Audio Visual 

None 

Space ? 

None 

Equipment 

?

None 

S. Approvalj 

/

.i

Date: 

e

ct

Department Chairman 

?

Chairman, SCUS 

.

SCUS 73-34b:- (When completing this form, for instructions see Memorandum SCUS 73-34a. 

Attach course outline). 

MACM 300 

Introduction to Formal Languages and 

Automata with Applications 

Course Outline 

1.

Chomsky Hierarchy - languages, grammars. 

2.

Regular and Context-Free Languages - grammars, finite and push-down 

automata. 

3.

Applications - text processing, artificial intelligence. 

4.

Deterministic Languages - LR(k) grammars, deterministic pushdown 

automata, application to compilers. 

S. Turing Machines and Linear Bounded Automata - recursive, recursively 

enumerable and context-sensitive languages., 

6. Computability and Complexity Theory - introduction to recursive 

function theory, time and space hierarchies, complexity measures. 

Suggested Reference Book 

Introduction to Automata Theory, Languages, and Computation 

J.E. Hoperoft, J.D. Ullman 

Addison-Wesley, 1979. 

Prerequisites: 

CMPT 205 

Senate Paper

S5TTJ!t

4.5. Upper Division Degree Requirements. for Majors

Moved that the following changes be made to upper division requirements for a CMPT major

for the BA.. B.Sc.. B.B.A. and B.Ed. degree.

The Social Aspects of Computing requirement is dropped for B.A.. B.B.A., and B.Ed.

degrees.

Candidates for the B.A.. B.B.A. and B.Ed. degrees must, in addition to satisfying

breadth and depth requirements, take one further course from the Computing Science

depth areas or the list of Computing Science Electives to make up their total of 30

upper division CMPT credits.

The requirement for a concentration of 15 semester hours in another discipline is

eliminated for the B.B.A.. BEd. and B.Sc. degrees. The requirement is retained for

the B.A. degree, in which case the department of concentration must be in the

Faculty of Arts.

Candidates for the B.Sc. degree are required to take two further courses chosen the

lists of Computing Science depth areas, Computing Science Electives or Computing

Mathematics Electives, in addition to meeting depth and breadth requirements and

completing MACM 316.

Candidates for the B.Sc. degree must additionally complete 9 credits of electives (at

any level) from the Faculty of Arts.

Rationale

These changes strengthen the requirements for a B.Sc. degree in Computing Science, recognizing

that the increasingly professional nature of the discipline places increasing requirements on the

Computing background of graduates. The total number of required upper division credits has

been raised to 39 from 36 (30 CMPT credits plus 6 upper division credits in a concentration).

At the same time, however, requirements for B.A.. B.B.A. and BEd. are held to 30 upper

division CMPT credits. The concentration of 15 credits outside of CMPT is dropped for B.B.A.

and B.Ed. degree candidates as it is redundant in their case.