Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Page 8
Page 9
Page 10
Page 11
Page 12

To ...... 

..enat ? 

........................................From ......

Senate Committee on 

...

?

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

Su6jectcQmPW1 

. g .

?

.o.gizatt

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

.Date. . . 

15.. Novezhex. .197.8

Revisions 

Action taken by the Senate Committee on Undergraduate Studies 

at its meeting on October 24 and November 14, 1978 gives rise to 

the following motion: 

MOTION 

That Senate approve and recommend approv&l to the Board of 

Governors of the proposed revisions to the Computing Science 

Program as outlined below and detailed in S78-143: 

a)

New Course Proposal - CMPT 405-3, Design and Analysis 

of Computing Algorithms 

b)

Changes in upper division course requirements 

(1)

Requirements for a Major in CMPT. 

(2)

Additional requirements for the degree. 

.

?

(3) Requirements for Honors in CMPT. 

(4) Additional requirements for the degree. 

N.R. Reilly 

/kb

SiMON FRASER UNIVERSITY

. ?

MEMORANDUM

Faculty of Interdisciplinary Studies 

.

.. .

thderta.te .c

Committee

Sub,ect ... L5.0......8:1..

CMPT

405 - 

Design and

Analysis

of

Date. OCtOber

178

Computing Algorithms 

The

attached new course proposal, QvIPT 405-3 - 

Design and

Analysis of 

Computing

Algorithms, was approved at the Oc'ober 3, 1978 meeting of the 

Faculty of Interdisciplinary Studies Undergraduate Curriculum Committee, 

subject to circulation to other faculty curriculum committees for overlap 

consideration. 

As per the attached memo, this course 

was

sent out for overlap considera- 

tion October 11, 1978. 

Please place this on the agenda for the next meeting of the Senate Committee 

on Undergraduate Studies. 

Janet Blarkhet

JB:

k

Attach. 

P

'I 1I 

!

7

L.

-

^J

. "o 

'^

'J

,

r

L^

i-

^ V E DO 

OCT 1 6 1978

REGLIAR'S

OFFICE ?

MALL. DESK

SiMON FRASER UNIVERSITY

MEMORANDUM

CHAIRMEN OF FACULTY 

?

From. Doug Seeley 

CURRICULUM CO4ITTEES 

?

Computing Science Department 

Subject....

.

roposed 

CMPT 

405 Course 

?

Dale ?

October 

11, 197.8 

Faculty of Science - Dr. David Ryeburn 

to ? 

Arts ? 

-

Dr. Wyn Roberts 

Education - Dr. M.F. Wideen 

Registrar - Mr. Harry 

M. Evans 

Enclosed for your perusal, is the description of a proposed new course 

in Computing Science, that is being considered by the Faculty of 

Interdisciplinary 

Studies for forwarding to 

SCUS. Copies have also been sent to 

MATH

some time ago. 

I

trust that the 

rationale 

speaks for itself; if not please feel free to contact 

me.

DARS 

:ajj

-?L..4'

_,•c

SENATE (X)Pet 111 lE ON UN DE

MADKELST!!1JS

NLbI sOURSE Pi0rOSA1. N! 

Calendar ? 

Department: Computing 

Science

Mbrevlatiofl

e:_

?

course Number:405 

?

Credit Hour.: 3 

?

Vector:-ü_ 

nU. of

CourOO

Design and Analysis 

of Computing

Algorithms 

Calendar DsscriPttOn of Course: 

Models of

Computation; 

?IetJiod

s of

Algorithm 

Design;

Complexity 

Algorithms; 

Algorithms on Graphs and Integers, Sorting ani Searching, NP-Complete Problems, 

Applications in Graphics and Artificial Intelligence. 

Nature of Course 

rr.r.quisites 

(or

special instructions): 

GeT 201, CPT 205. or MATH 243 

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

course 

is

approveds 

lou

frequently 

will the

course be offered? Fall of each year, initially 

in 79-3

.sU.r 

in which th.

course will first be offered? 

1 c

of your present

faculty would be available to make the proposed offering                           

•

possible? 

J. $arenholtz, Doug Seeley, W. S. 

Havens

ftlsct 

iv..of_the_

course 

To provide students with sufficient tools and understanding of the analysis 

of common computer algorithms that they may apply 

this

knowledge to those 

algorithms which they will design. 

4. ?

g.tary_andSpaceDaguirernanti (for information only) 

What additional resources will be required in tle following areas: 

Vscsslty ? 

Faculty provided previously. 

Iaff

Library

NONE

Audio Visual

Space

EquIpment ?

Computer time for a typical CWT course say CMPT 305 

'

Computing Center support of the language PASCAL. 

/

:• 

/

_

/7_

i>

Date 

$.c

/1L

Rationale 

Since the early 70's, this has been recognized as the primary core subject 

of Computing Science, and has been adopted by the vast majority of Computer Science 

programs in North America. Paraphrasing the proposed textbook: 

"The study of algorithms is at the very heart of computer science. 

In recent years a number of significant advances in the field of 

algorithms have been made. These advances have ranged from the 

development of faster algorithms, to the startling discovery of 

certain natural problems for which all algorithms are inefficient. 

These results have kindled considerable interest in the study of 

algorithms, and the area of algorithm design and analysis has 

blossomed into a field of immense interest. The interest of this 

course is to bring together the fundamental results in this area, 

so the unifying principles and underlying concepts of algorithm 

design may more easily be taught." 

The introduction of this course is a major step in alleviating a perceived 

weakness in the current cMPT course offerings, i.e. the lack of a strong theoretical 

core. This does not imply that Computing Science is going to swing to the theoreti- 

cal, but rather the broad coverage of the diversity of computing science in our 

curriculum will be complemented by a course of unifying concepts. This Is a course 

that is concerned not just with applications of programming but with what con- 

stitutes a "good" or effective program (algorithm). 

There exists some potential overlap with '1ATH 343; however where this can 

occur, the emphasis of CMPT 405 will be on the analysis of an algorithm's coinpiexit 

and not on combinatorial theory. This matter has been discussed with appropriate 

members of the MATH faculty. 

In summary, this course represents a well-defined body of knowLedge that 

is perceived to be the key theoretical component of our discipline. This fact 

is recognized as well by its inclusion as a required course in a proposal for new 

Upper Division requirements. 

Textbook -- Aho, Hoperoft, & Ullman, "The Design and Analysis of Algorithms. 

References -- Knuth, "The Art of Computer Programming" 

Vol. 1: Fundamntai Algorithms 

Vol. 3: Soctin & Searching 

Shamos, "CompuIticnal Geometry" 

0 ?

COURSE-OUTLINE 

Pro p 

oskQfl

405

Outline: Desi 

g

n and Analysis of Ccputer Algortttvfls 

In all of the topics mentioned below, the emphasis L10 on the analysis 

of the C 

g

t$tiOflSl complexity of algorithms in these Arils. 

ILI...aL.aU2n:

the complexity of aigorttiI, 

VAIl progrs 

stored program model, tet*tiOtIhip between 

Turing Macbias. 

and RAM, a language for expressing 

Il$brithm.. 

2.

ISIkO4S 

of Al

g

orithm Design data structures, 

rStUfllbn, divide-and- 

conquer, balanciall 

bktrack programming, 

braocb 

and

bewW. 

dynamic programing. 

3.

Ost4 

1asfftatlw

set operations. binary •tâTCh Ui.., optimal 

search trees, balanced tt*., 

dittionaries 

and

priority queue.. 

4. 12%&II'

the types

and uses of internal sorts, 

ÜptiIáI

sorts, Heapsort, 

Qi.ick.ort, order statistics, some methods 

external sorting. 

£auth*3 

binary 

tree searching, balanced trees, ifltrpolation search, 

bashing, 

retrieval on secondary keys. 

•

mossrAmp-MmMis A1gprithn:

integer multipllcatiOfl and division, 

polynomial evaivatibfl, modular arithmetic, 

matrix multiplication, Boolean matrix mu1tipltctiofl. 

7.

AlaorithSs on

Grap hs ? 

spanning trees, depth-first search, path-finding, 

shortest paths. 

S. Cutatiosil 

Geometry: convex hulls, inclusioii prob1ms, intersection 

problems, closest-point 

próbtèms.

9.

1aorithes to Attifictal Intelligence: pattern mathiftg, alphabets pruning. 

10.

iP-Gol.ts 

Problems: the classes NP and F, the equtvdlence of various 

NP-complete problems, intractdblO problems. 

SIMCN FRASER UNIVERSITY $ '

f ?1- 6'

MEMORANDUM

0....

Mr. H. M....... 

R e g

istrar........Se.e.re.t.ary ....

of. ..S.CU,S.. 

revised.... 

Curriculum chaiigs 

is

From .....

.J•. BIanchet, Secretary....o.f,...the.... 

Faculty of Interdisciplinary 

Studies 

....Under.g.raduate. . Curriculum 

Committee. 

Date ?

O.ct.ob:er...30/78............... 

Changes to t1 

?

'equirements for the Computing Science Major and 

Honors were 

approved

at a meeting, of the Faculty of Interdisciplinary 

Studies Un.deaduate Curriculum Committee held on October 

10/78.

Computing Scie subsequently piodified the changes, and these 

have been apprqyed via a telephone poll of the members of the 

Faculty of Iior4cplinary Studies Undergraduate Curriculum 

Committee 

4t the

next formal neeting of this committee these 

items will bQ 

ratifed 

Would you please place this item on the agenda for the next 

meeting of the Senate Committee on Undergraduate Studies.. 

Janet Blanche't.. 

Attachment. 

For the rationale e.low, the i)e p

artment t Computing Science recommends

calendar changes to reflect changes in Uotcr Division

CoursE.

Pat ioriale

Computing Science is a rapidly evoiving ad diverse discipline. It is

intrinsically interdiscinlinary, requiring knowledge of programming, the

theory of computation, the logical circuits and hardware components

conipliters,

the

organization of information systems, uumc'r:i cal methods, graphic disolay

nrubloin-soi.ving, and the archi Lecture ot systems and niich [ties.

A student with a degree in Computing Science should have both breadth

and de

th of knowledge in the field. The student shoUld Obtain experience of

the above diversity through course work, yet have studied some of these areas

in sufficient depth that the student may pursue graduate

work or display

recognized skills in the computing community.

The previous calendar requirements specified neither breadth nor depth,

only required courses. The scheme described here not only provides this but

supplies a coherence to the department's course of fetings that will help the

student select a well-rounded program of courses.

In addition, the courses required for the degree have been revised to

more accurately reflect a core of knowledge that any computing scientist can

be assumed to have.

Proposed Calendar Entry: ?

(to replace material at current locations

pages 296-297 from "Upper Division Course

uirements up until "Program for a Minor . .

Upper Divis:ion Course Requirements

Attention is drawn to the lower division courses stated above. Majors

and Honors. students are required to consult a departmental advisor before

submitting a program of study.

Requirements- are structured according to the areas of concentration

shown in Table 1. Each course appears

One area, but a fdk courses also

overlap other areas- to an extent that permits their Use iii Other areas as

well. These courses- are enclosed in parentheses in Table 1. When a course is

selected from an area to fulfill a breadth requirement, this course should

normally-be one of the key courses for the area, as indicated in Table 2.

Note that no upper division course may be counted for semester hour credit

toward two separate requirements, although it may be used to fulfill course

content purposes in more than one area. For example, MATH 306 may be counted

toward the 30 hours of upper division Computing Science courses or as part of

a 15 hour concentration in Mathematics but not for both.

TABLE 1 

?

Area ? 

Course ? 

Title 

Computer Desigr 

and

C1PT 390 

Digital Circuits & Systems 

Organization 

C1PT 

400

Hardware-Software Architecture I 

(CMPT 

401) 

Hardware-Software Architecture II 

CMPT 

491

Computers in Real-Time Experiments 

MATH 

401

Switching Theory & Logical Design 

Software Systens* 

CMPT 

301

System Development Methodology 

CMPT 

305

Computer Simulation & Modeling 

CMPT 

401

Hardware-Software Architecture II 

CMPT 

404

Computer System Measurement & 

Evaluation 

(CMPT 

491) 

Computers in Real-Time Experiments 

Information Systems* 

CMPT 

302

System Development Projects 

CMPT 

350

Information and Public Policy 

CNPT 

354

Information Organization & Retrieval 

CMPT 

370

Management & Information Systems I 

CMPT 

371

Management & Information Systems I 

Intensive Applications 

C.MPT 

351

Introduction to Computer Graphics 

C.MPT 

380

Computational Linguistics 

CMPT 410 

Artificial Intelligence 

CMPT 

451

Interactive Graphics & Animation Systems 

Theoretical Computing 

(MPT 

405

Design & Analysis of Algorithms 

Science 

MATH 

306

Introduction to Automata Theory 

MATH 343 

Combinatorial Aspects of Computing 

MATH 

401

Switching Theory & Logical Design 

MATH 402 

Automata & Formal Languages 

MATH 

403

Algebraic Theory of Automata 

Analytical Tools 

for

(CMPT 

305) 

Computer Simulation & Modeling 

Scientific Computation 

CMPT 360 

Computation for Statistical Data 

Processing 

MATH 

308

Linear Programming 

MATH 

316

Numerical Analysis I 

(MATH 

343) 

Combinatorial Aspects of Computing 

MATH 408 

Discrete Optimization 

* Software in this context is distinguished from Information Systems which 

are meant to include data bases and systems for management decision-making. 

TABLE 2 

Area ? 

Key Course(s) 

Computer Design and Organization 

?

CMPT 400 

Software Systems ? 

CMPT 301 

Information Systems ? 

CMPT 354 

Intensive Applications ? 

CMPT 410 or CMPT 351 

.

?

Theoretical Computing Science ? 

MATH 306 

Analytic Tools for Scientific Computation 

?

any course 

PROGRAM FOR A MAJOR IN COMPUTING SCIENCE 

?

Attention is drawn to lower division course requirements, as prerequisites, 

as described in the preceding Eections. 

(a) For a Major in Computing Science students must complete:- 

thirty hours of upper division Computing Science courses including 

CMPT 354, 405, and 493. The 30 hours of Computing Science courses must 

satisfy the following distribution requirements: 

1) Depth Requirement: 

Concentrations consisting of 3 courses from two of the areas shown 

in Table 1. 

heoretic a l

Computing Science and' Analytic Tools for 

Scientific Computation may not both be counted as Depth Areas. 

Note: In exceptional circumstances, different depth areas may be 

considered 

apd

sanctioned with the approval of faculty sponsor 

and the Curriculum Committee. 

ii)

Breadth Requirement: 

Three different courses from distinct areas selected from the 

remaining areas (each course should normally be a key course, 

in the area as indicated in Table 2-if not previously taken). 

iii) 

Any other upper division Comoiting Science course to bring the 

total upper division hours to at least 30. 

(b) In addition, for 

the

general degree students must include a concentration 

in a discipline (department) other than Computing Science, approved by the 

program advisor, consisting of at least 15 semester hours, and including 

at least 6 hours 

upper division credit. 

(c) For a genera' degree with a Major in Computing Science a student must 

complete 120 semester hours, with an overall minimum of at least 45 hours 

of upper division credit. 

Students are advised to consult the University and Faculty regulations governing 

graduation requirements which are specified elsewhere in the calendar. 

4

-

PROGRAM FOR HONORS IN COMPUTING SCIENCE 

Attention is drawn to lower division cou:se requirements, as prerequisites, 

as described in the preceding sections. 

(a) For Honors in Computing Science students must complete:- 

fifty hours of upper division Computing Science courses including 

CMPT 354, 405, and 493. The 50 hours of Computing Science courses 

must satisfy the following distribution equirements: 

i) Depth Requirement: 

Concentrations consisting of 4 

cou::ses 

in one of the areas shown 

in Table 1 and 3 courses in each oE two other areas. One of the 

three areas chosen must be Theoretical Computing Science 

Note: In exceptional circumstances, differen: depth areas may be 

considered and sanctioned with the app-.:oval of faculty sponsor 

and the Curriculum Committee. 

ii)

Breadth Requirement: 

Three different courses consisting of one course from each of the 

remaining areas (each course should normally be a key course in 

• ? 

the area as indicated in Table 2, :.f not previously taken). 

iii) 

Any other Computing Science course; to bring the total upper division 

hours to at least 50. 

(b) In addition, for the Honors degree students must include a concentration 

in a discipline (department) other than Computing Science, approved by 

the program advisor, consisting of at least 15 semester hours, and 

including at least 6 hours of upper division credit. 

(c) For a degree with Honors in Computing Science a student must complete 132 

semester hours with an overall minimum oE at least 60 hours of upper 

division credit. 

Students are advised to consult the 

Universit', 

and Faculty regulations governing 

graduation requirements which are specified 

e-

Lsewhere in the calendar. 