SFU Calendar 2001-2002

Table of Contents : searchable with the Find function of your web browser Course Database or Course Outlines
(opens in new window)
Financial Assistance
Index : searchable with the Find function of your web browser Calendar .pdfs Office of the Registrar / SFU

School of Computing Science

9971 Applied Sciences Building, (604) 2914277 Tel, (604) 2913045 Fax, www.cs.sfu.ca


Z.N. Li BSc (Chinese Sci & Technol), MSc, PhD (Wis)

Graduate Program Director

(to be announced)

Faculty and Areas of Research

For a complete list of faculty, see "School of Computing Science"..

M.S. Atkins - medical computing, medical image analysis, operating systems and distributed system design

B.K. Bhattacharya - pattern recognition, computational geometry

F.W. Burton - functional programming, parallel computing

T.W. Calvert - information processing in man and machines, biomedical applications, graphics

R.D. Cameron - programming languages and systems, software engineering

V. Dahl - logic programming, computational linguistics, artificial intelligence

J.P. Delgrande - artificial intelligence, knowledge representation

J.C. Dill - computer graphics, computer aided engineering, design and manufacturing

M.S. Drew - multimedia, computer graphics, computer vision, colour reproduction

B.V. Funt - artificial intelligence, computer vision, colour perception

A. Gupta - constructive combinatorics, parallel complexity theory

R.F. Hadley - artificial intelligence, automated learning, philosophical foundations of cognitive science, computational semantics,

L.J. Hafer - constrained optimization, design automation

J.W. Han - database and knowledge-base systems, deductive databases, logic programming

R. Harrop - medical applications, automata theory, logic

W.S. Havens - expert systems, constraint reasoning, artificial intelligence

P. Hell - computational combinatorics, algorithm graph theory

R.F. Hobson - very large scale integrated design, computer design, circuit design

T. Kameda - analysis of algorithms, computer communications networks, database systems

R. Krishnamurti - reconfigurable architectures, parallel computing, image processing, interconnection networks

Z.N. Li - computer vision, image processing, artificial intelligence

A.L. Liestman - analysis of algorithms, distributed algorithms, graph theory

W.S. Luk - database systems, distributed processing

D. Mitchell - constraint satisfaction; propositional proof complexity; automated reasoning

T. Möller - computer graphics, scientific visualization

M.B. Monagan - computer algebra, symbolic computation, computer graphics, data structures

J.G. Peters - combinatorial approximation, parallel processing, distributed processing

F. Popowich - computational linguistics, logic programming, artificial intelligence

R.D. Russell - numerical solution of ODE, mathematical software

T.C. Shermer - computational geometry, graph theory, computer graphics

T.D. Sterling - statistics and data processing applications, social applications, systems design

E. Ternovska - logical methods in program verification and database theory; complexity issues in knowledge representation

M. Trummer - numerical analysis

K. Wang - database systems and data mining

Q. Yang - scheduling, case-based reasoning, constraint problem solving

Research Facilities

The School of Computing Science operates several interconnected local area networks in co-operation with other departments in the Faculty of Applied Sciences. These networks are connected to SFU LAN, the campus-wide network, which also provides access to the Internet.

Facilities include over 300 networked workstations, file servers, CPU servers, and other specialized systems. The workstations are mostly SUN UltraSparc and PC, with some Silicon Graphics and Macintosh workstations. Additionally, the school has comprehensive resources to facilitate VLSI design, simulation, fabrication and testing.

Other computing resources are provided by Academic Computing Services including six large SGI 4D multiprocessor systems, four Sun SPARC-II computers, an IBM RS6000, and an Auspex file server. These systems and a range of software and services are available to the campus community.

Degrees Offered

The School of Computing Science offers programs leading to the MSc and PhD in computing science. It provides students with graduate studies in the following areas: theoretical computing science; artificial intelligence; database systems; computer graphics and multimedia computing; hardware design; distributed computing; programming languages and systems; computer vision and medical imaging.


To qualify for admission to the MSc program, a student must satisfy the University admission requirements stated in section 1.3 of the Graduate General Regulations and must have a bachelor's degree or the equivalent in computing science or a related field.

To qualify for admission to the PhD program, a student must satisfy the University admission requirements stated in Graduate General Regulations 1.3 (page 297) and

At its discretion, the school's graduate admission committee may offer either MSc or PhD admission to students applying to the PhD program without a master's degree or equivalent in computing science or a related field. Students enrolled in the MSc program may apply to transfer to the PhD program after two semesters in the MSc program; the school's evaluation procedure for such applications is the same as that used for outside applicants.

Breadth and Course Requirements

For purposes of defining the MSc and PhD breadth requirements, a set of sub areas are identified and grouped into three major areas: Formal Topics in computing science, computer systems, and knowledge and information systems. Table 1 shows the standard sub areas within each area.

Table 1
Area I - Formal Topics in Computer Systems

algorithms and complexity

formal logic and language semantics

discrete mathematics

operations research

Area II - Computing Systems

operating systems and networks

computer design and organization

programming languages and compilers

software methodology and engineering

Area III - Knowledge and Information Systems

artificial intelligence and robotics

database and information retrieval systems

numerical and symbolic computing

computer graphics and interfaces

The course requirements for the MSc and PhD degrees each have a distribution requirement to ensure breadth across the major areas defined in table 1. This requirement is specified in terms of number of courses and subareas selected from each of the three major areas. At its discretion, the graduate breadth evaluation committee may accept requests to define subareas other than those in table 1 for the purpose of satisfying MSc or PhD breadth requirements.

Supervisory Committees

A supervisory committee, at either the MSc or PhD level, consists of the student's senior supervisor, at least one other computing science faculty member, and other members (typically faculty) as appropriate. The choice of senior supervisor should be made by mutual consent of the graduate student and faculty member based on commonality of research interests. The student and senior supervisor should consult on the choice of the remainder of the committee members.

Section 1.6 of the Graduate General Regulations specifies that a senior supervisor be appointed normally no later than the beginning of the student's third semester in the program, and that the remainder of the supervisory committee be chosen normally in the same semester in which the senior supervisor is appointed.

Research Topics Seminars

The research topics seminar series is presented over the course of the year by faculty and graduate students. Faculty presentations acquaint new graduate students with the research interests of the faculty. Graduate student presentations typically showcase thesis research. Students in the first year of graduate study are required to attend faculty research topics seminars to become familiar with the research interests of the faculty.

MSc Program

Students are expected to acquire breadth of knowledge through a sequence of courses and depth of knowledge through completion and defence of a thesis or a project. Under normal circumstances, an MSc program should be completed within six semesters and should not require longer than eight semesters. An MSc student must choose between thesis and project options by the end of the second semester. Any change in option thereafter must be approved by the graduate program committee.

Breadth Requirement

MSc students choosing the thesis option complete at least 15 credit hours of graduate work (typically five courses) such that at least one course is chosen from each of areas I, II and III of table 1. At least 12 of the 15 credit hours (typically 4 courses) must be taken in computing science. Course work will normally be completed by the end of the fifth semester.

MSc students choosing the project option complete at least 27 credit hours of graduate work (typically nine courses) such that at least two courses are chosen from each of areas I, II and III of Table 1. The two courses taken in each area should be from different sub-areas. At least 21 of the 27 credit hours (typically seven courses) must be taken in computing science. The project should be roughly equivalent to five credit hours of work.

All breadth requirements are sugject to approval by the student's supervisor and the Graduate Breadth Evaluation Committee.

Depth Requirement

MSc students submit and defend a thesis or project report based on their independent work. Thesis option students consult with his/her supervisory committee, and formulate and submit a written thesis proposal for approval, normally not later than the end of the program's third semester.

Regulations specifying the examining committee's composition and procedures for the final thesis or project exam appear in the Graduate General Regulations 1.9 (page 301) and 1.10 (page 302). MSc students with thesis option are required to give a seminar about their thesis research in the interval between distribution of the thesis to the committee and the defence.

PhD Program

Students in the PhD program are required to demonstrate breath of knowledge as outlined below and demonstrate the capacity to conduct original research through the completion and defence of an original thesis. Under normal circumstances a PhD degree should be completed within 12 semesters and should not require longer than 15 semesters.

Breadth Requirement

PhD students are required to demonstrate breadth to a level equivalent to at least 21 credit hours of graduate level course credit (typically seven courses), subject to the following distribution.

Up to two courses outside of computing science may be used in satisfying the breadth requirement, subject to approval by the student's supervisory committee and the graduate breadth evaluation committee. A PhD student must achieve a minimum CGPA of 3.4 and passing marks in all courses.

Students submit, within two months of program entry, a proposal to satisfy breadth requirements or may request that up to four courses and any portion of the breath distribution be waived based on previous graduate work, or by examination. A minimum of 9 credit hours (typically three courses) is required. The graduate breadth evaluation committee may approve the proposal or recommend alternatives at its discretion. The breadth requirement is normally completed by the end of the third to sixth program semester, in proportion to the number of courses actually required.

Depth Requirement

PhD students demonstrate depth of knowledge in their research area through a public depth seminar and oral examination, give a thesis proposal seminar, and submit and defend a thesis based on their independent work which makes an original contribution to computing science.

Depth Examination

The depth seminar and examination may be scheduled at any time following the completion of breadth requirements. Typically this is between the fifth and seventh semester in the PhD program; a recommendation is made by the graduate breadth evaluation committee, in proportion to the amount of course work required to satisfy the breadth requirement. The examining committee consists of the supervisory committee and one or two additional examiners recommended by it and approved by the graduate program committee. The exam centres on the student's research. The examining committee, in consultation with the student, specifies the topics in the examination. The student prepares a written survey and gives a public depth seminar; the oral exam follows, and then the committee evaluates the student's performance in the program to that point. The committee's evaluation is diagnostic, specifying additional work in weak areas if such exists. A second depth examination or withdrawal from the program may be recommended in extreme cases.

Thesis Proposal

The student, in consultation with her/his supervisory committee, formulates and submits, for approval, a written thesis proposal consisting of a research plan and preliminary results. The student gives a seminar and defends the originality and feasibility of the proposed thesis to the supervisory committee. The thesis proposal is normally presented and defended within three semesters of the depth examination.

Thesis Defence

Regulations specifying the examining committee composition and procedures for the final public thesis defence are in sections 1.9 and 1.10 of the Graduate General Regulations. PhD students give a seminar; typically this will be about their thesis research and is presented in the interval between distribution of the thesis to the committee and the defence.

Graduate Courses

CMPT 601-5 Computing Science Education I

This course will introduce graduate students in Education to the basics of computing science. Emphasis will be placed on the use of microcomputers. Topics will be programming microcomputers; file handling; microcomputer hardware; word processing; graphics; social, economic and legal implications. Prerequisite: graduate status in education. If the student has an adequate background in computing, this course must be replaced by other computing science undergraduate or graduate courses.

CMPT 602-5 Computing Science Education II

This course introduces some formal topics in Computing Science to the graduate student in education. Topics include discrete mathematical structures; models of computing; data structures; formal languages and algorithms. Also, methods will be introduced for the design and implementation of large programs using structured modular design. Prerequisite: CMPT 601 or consent of instructor(s).

CMPT 710-3 Computational Complexity

This course provides a broad view of theoretical computing science with an emphasis on complexity theory. Topics will include a review of formal models of computation, language classes, and basic complexity theory; design and analysis of efficient algorithms; survey of structural complexity including complexity hierarchies, NP-completeness, and oracles; approximation techniques for discrete problems.

CMPT 720-3 Artificial Intelligence

Artificial Intelligence brings concepts such as computation, process, sub-procedure, data structure, and debugging to bear upon questions traditionally raised by psychologists, linguists, and philosophers. In this course we will study a representative sample of work in the field. This will include programs which process written English, `see', play games, prove theorems, and solve problems.

CMPT 730-3 Foundations of Programming Language

This course will cover basic concepts in the area of programming languages. The course will be largely of a theoretical nature and will concentrate on fundamental concepts of lasting importance, rather than topics of current interest.

CMPT 740-3 Database Systems

Introduction to advanced database system concepts, including query processing, transaction processing, distributed and heterogeneous databases, object-oriented and object-relational databases, data mining and data warehousing, spatial and multimedia systems and Internet information systems.

CMPT 750-3 Computer Architecture

Parallel processing: SIMD & MIMD systems, pipelining, data flow architecture; microprogramming; control memory minimization, optimization and verification of micro-programs.

CMPT 760-3 Operating Systems

This course will discuss design issues relating to the functionality and performance of modern workstation operating systems, such as methods for sharing memory, file and data objects, and choice of communication protocols. The special needs of high performance multiprocessor systems and real time systems will also be addressed.

CMPT 770-3 Computer Graphics

This course covers advanced topics and techniques in computer graphics such as solid modelling, curves and surfaces, fractals, particle systems, advanced rendering techniques, animation and post-production techniques. Research topics in virtual reality, human figure animation, CAD, scientific visualization and other areas will also be discussed. Students with credit for CMPT 461 or equivalent may not take CMPT 770 for further credit.

CMPT 813-3 Computational Geometry

This course covers recent developments in discrete, combinatorial, and algorithmic geometry. Emphasis is placed on both developing general geometric techniques and solving specific problems. Open problems and applications will be discussed.

CMPT 814-3 Algorithmic Graph Theory

Algorithm design often stresses universal approaches for general problem instances. If the instances possess a special structure, more efficient algorithms are possible. This course will examine graphs and networks with special structure, such as chordal, interval, and permutation graphs, which allows the development of efficient algorithms for hard computational problems.

CMPT 815-3 Algorithms of Optimization

This course will cover a variety of optimization models, that naturally arise in the area of management science and operations research, which can be formulated as mathematical programming problems.

CMPT 816-3 Theory of Communication Networks

This course investigates the design, classification, modelling, analysis, and efficient use of communication networks such as telephone networks, interconnection networks in parallel processing systems, and special-purpose networks.

CMPT 817-3 Knowledge Bases with Visual and Natural Language

This course examines recent significant advances in knowledge bases, focusing in particular on knowledge representation, reasoning, and integration of knowledge bases with friendly front ends such as visual and natural language interfaces. It is expected that students who complete the course will gain sufficient background to begin research projects at the master's or doctoral levels in the topics covered. Students from computing science, mathematics, linguistics, education, philosophy, psychology, cognitive science and engineering science are especially encouraged to register for this course.

CMPT 820-3 Multimedia Systems

This seminar course covers current research in the field of multimedia computing. Topics include multimedia data representation, compression, retrieval, network communications and multimedia systems. Computing science graduate student or permission of instructor.

CMPT 821-3 Robot Vision

This course discusses issues and research results pertinent to robot vision. Topics include depth recovery for robot navigation, three dimensional object recognition and scene analysis, model-based approaches, parallel vision machines and algorithms, and case studies of contemporary robot vision systems.

CMPT 822-3 Computational Vision

A seminar based on the artificial intelligence approach to vision. Computational vision has the goal of discovering the algorithms and heuristics which allow a two dimensional array of light intensities to be interpreted as a three dimensional scene. By reading and discussing research papers - starting with the original work on the analysis of line drawings, and ending with the most recent work in the field - participants begin to develop a general overview of computational vision, and an understanding of the current research problems.

CMPT 823-3 Formal Topics in Knowledge Representation

This course surveys current research in formal aspects of knowledge representation. Topics covered in the course will centre on various features and characteristics of encodings of knowledge, including incomplete knowledge, nonmonotonic reasoning, inexact and imprecise reasoning, meta-reasoning, etc. Suggested preparation: a course in formal logic and a previous course in artificial intelligence.

CMPT 825-3 Natural Language Processing

In this course, theoretical and applied issues related to the development of natural language processing systems and specific applications are examined. Investigations into parsing issues, different computational linguistic formalisms, natural language syntax, semantics, and discourse related phenomena will be considered and an actual natural language processor will be developed.

CMPT 826-3 Automated Learning and Reasoning

This course covers topics shared both by AI and cognitive science. Current AI research papers are examined from the perspective of cognitive science, and vice versa. Topics covered in a given semester will vary, depending upon the instructor, but most of the following topics will be addressed in any given semester: connectionist models of intelligence; `human-like' automated deduction; reasoning by analogy; topics in natural language; automated concept learning; and computational approaches to semantics. Prerequisite: at least one graduate or undergraduate AI course, or instructor's permission.

CMPT 827-3 Intelligent Systems

Intelligent systems are knowledge-based computer programs which emulate the reasoning abilities of human experts. This introductory course will analyse the underlying artificial intelligence methodology and survey advances in rule-based systems, constraint solving, incremental reasoning, intelligent backtracking and heuristic local search methods. We will look specifically at research applications in intelligent scheduling, configuration and planning. The course is intended for graduate students with a reasonable background in symbolic programming.

CMPT 830-3 Compiler Theory

Precedence, LL(k), LR(k) grammars; SLR(k), LALR(k), L(m)R(k) and LR(k) parsing techniques; transduction grammars; general compiler organization, code generation and optimization; memory allocation for object programs; garbage collection.

CMPT 831-3 Functional Programming

This course will cover functional programming including introduction to a functional programming language, program transformation and verification, implementation of functional programming languages, and other selected topics which may include parallel evaluation of functional programs, analysis of performance, and advanced applications.

CMPT 842-3 Concurrency Control in Database Systems

Transactions, recoverability, serializability theory, schedulers, locking, timestamping, optimistic schedulers, multiversion database systems; recovery, commit protocols, termination protocols; replicated database systems, quorum based concurrency control; distributed snapshot taking, distributed deadlock detection, reliable storage systems; concurrency control in object oriented database systems.

CMPT 843-3 Principles of Database and Knowledge Base Systems

An advanced course on database systems which focuses on data mining and data warehousing, including their principles, designs, implementations, and applications. It may cover some additional topics on advanced database system concepts, including deductive and object-oriented database systems, spatial and multimedia databases, and database-oriented Web technology.

CMPT 852-3 VLSI Systems Design

This course links two fields that traditionally have been considered two separate entities: computer architecture and integrated circuit design. The vehicle used to demonstrate the interaction of layout issues and architectural concepts is metal oxide semiconductor technology.

CMPT 853-3 Computer-Aided Design/Design Automation for Digital Systems

Algorithms for logic synthesis and physical CAD/DA. Emphasis on routing, placement, partitioning, and gate level logic synthesis.

CMPT 873-3 User Interface Design

This course provides an overview of a number of research areas in human-computer interaction. Topics may include: overview of HCI (historical/intellectual, GUI, case studies), interactive systems (design, evaluation, software development), interaction methods (vision, graphic design, touch, speech, etc.), human factors (information processing, capabilities), research frontiers (computer supported co-operative work, intelligent systems, hypertext, multimedia, virtual reality, cyberspace). Recommended: CMPT 363 or equivalent (instructor discretion).

CMPT 878-3 Scientific Visualization

This course presents advanced topics in the field of scientific visualization. Topics may include: an introduction to visualization (importance, basic approaches and existing tools), abstract visualization concepts, human perception, visualization methodology, 2D and 3D display and interaction, advanced techniques (polygon reduction, volume rendering, multivariate representations, parallel algorithms, etc.) and virtual reality. Prerequisite: CMPT 461, 770 or equivalent (by permission of instructor).

CMPT 880-3 Special Topics in Computing Science

This course aims to give students experience to emerging important areas of computing science. Prerequisite: instructor discretion.

CMPT 881-3 Special Topics in Theoretical Computing Science
CMPT 882-3 Special Topics in Artificial Intelligence
CMPT 883-3 Special Topics in Programming Languages
CMPT 884-3 Special Topics in Database Systems
CMPT 885-3 Special Topics in Computer Architecture
CMPT 886-3 Special Topics in Operating Systems
CMPT 887-3 Special Topics in Hardware Design
CMPT 888-3 Special Topics in Computer Graphics

This course introduces graduate students to specialized topics in computer graphics. In most cases, such topics will build upon those discussed in previous graphics classes, or of prime interest to faculty (such as current research topics).

CMPT 889-3 Special Topics in Interdisciplinary Computing
CMPT 891-3 Advanced Seminar

Grade given: S (satisfactory) or U (unsatisfactory).

CMPT 894-3 Directed Reading
CMPT 897-0 MSc Project
CMPT 898-0 MSc Thesis
CMPT 899-0 PhD Thesis

Please email the Webmaster with any comments or problems with this website. Calendar Home Page Simon Fraser University
8888 University Drive
Burnaby, BC V5A 1S6
Index : searchable with the Find function in your web browser Calendar.pdfs Office of the Registrar / SFU
Table of Contents : searchable with the Find function in your web browser Course Database or Course Outlines
(opens in new window)
Financial Assistance