Please note:  

To view the Spring 2017 Academic Calendar go to http://www.sfu.ca/students/calendar/2017/spring.html

School of Computing Science Simon Fraser University Calendar | Summer 2017

Computing Science

Doctor of Philosophy

Admission Requirements

To qualify for program admission, a student must satisfy the University admission requirements stated in graduate general regulations 1.3 and

  • have a master’s degree or the equivalent in computing science or a related field or
  • have a bachelor’s degree or the equivalent in computing science or a related field, with a cumulative grade point average of 3.5 (on a scale of 0.0-4.0) or the equivalent.

At its discretion, the school’s graduate admissions committee may offer PhD admission to students applying to the PhD program without a master’s degree or equivalent in computing science or a related field.

Program Requirements

Students will demonstrate breadth of knowledge, and demonstrate the capacity to conduct original research through completion and defence of an original thesis. A PhD degree program should be completed within 12 terms and should not require longer than 15 terms. Students must achieve a minimum 3.4 CGPA and passing grades in all courses.

Breadth Requirement

For purposes of defining breadth requirements, courses are grouped into the five major areas shown in Table 1. Courses not related to the breadth requirements are shown in Table 2. Any courses completed outside the School of Computing Science must be approved by the student’s senior supervisor and the director of the graduate program.

The courses used to satisfy the breadth requirements must include either CMPT 705 or 710, unless the student already has credit for one of these courses (or equivalent) from a previous degree as determined by the graduate program breadth committee.

Only two special topics courses (two of CMPT 829, 880, 881, 882, 883, 884, 885, 886, 887, 888, 889) may be used toward satisfaction of breadth requirements, except with permission of the graduate program breadth committee.

PhD students who already possess an MSc in computing science or a related field must complete a breadth requirement of 12 units of graduate course work. At least 9 units must be completed through three courses drawn from Table 1 so that they are all in different areas.

PhD students who do not possess an MSc in computing science or a related field must complete a breadth requirement of 24 units of graduate course work. At least 18 units must be completed through six courses drawn from Table 1 and at least one course must be from Area I (Algorithms and Complexity Theory) so that the six courses cover at least three different areas.

PhD students may enter the Computing Science Graduate Co-operative Education Program but may not count practicums towards the breadth requirement.

Table 1

Area I – Algorithms and Complexity Theory

CMPT 705 - Design and Analysis of Algorithms (3)

The objective of this course is to expose students to basic techniques in algorithm design and analysis. Topics will include greedy algorithms, dynamic programming, advanced data structures, network flows, randomized algorithms.

Section Instructor Day/Time Location
G100 Ramesh Krishnamurti
Mo, We, Fr 12:30 PM – 1:20 PM
SSCC 9000, Burnaby
CMPT 710 - Computational Complexity (3)

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. Equivalent Courses: CMPT810.

Section Instructor Day/Time Location
G100 Valentine Kabanets
Tu 2:30 PM – 4:20 PM
Th 2:30 PM – 3:20 PM
SSCC 9000, Burnaby
AQ 3003, Burnaby
CMPT 711 - Bioinformatics Algorithms (3)

Fundamental algorithmic techniques used to solve computational problems encountered in molecular biology. This area is usually referred to as Bioinformatics or Computational Biology. Students who have taken CMPT 881 (Bioinformatics) in 2007 or earlier may not take CMPT 711 for further credit.

CMPT 813 - Computational Geometry (3)

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 - Algorithmic Graph Theory (3)

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 - Algorithms of Optimization (3)

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. Equivalent Courses: CMPT860.

Area II – Networks, Software and Systems

CMPT 745 - Software Engineering (3)

This course examines fundamental principles of software engineering and state-of-the-art techniques for improving the quality of software designs. With an emphasis on methodological aspects and mathematical foundations, the specification, design and test of concurrent and reactive systems is addressed in depth. Students learn how to use formal techniques as a practical tool for the analysis and validation of key system properties in early design stages. Applications focus on high level design of distributed and embedded systems.

CMPT 765 - Computer Communication Network (3)

This course will cover the fundamentals and recent advances in computer communication networks. The emphasis will be on the design and analysis of networks, especially switching, routing, and network topology.

CMPT 771 - Internet Architecture and Protocols (3)

Investigates the design and operation of the global network of networks: the Internet. This course studies the structure of the Internet and the TCP/IP protocol suit that enables it to scale to millions of hosts. The focus is on design principles, performance modelling, and services offered by the Internet.

CMPT 777 - Formal Verification (3)

The goal of formal verification is to prove correctness or to find mistakes in software and other systems. This course introduces, at an accessible level, a formal framework for symbolic model checking, one of the most important verification methods. The techniques are illustrated with examples of verification of reactive systems and communication protocols. Students learn to work with a model checking tool such as NuSMV.

CMPT 816 - Theory of Communication Networks (3)

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. Equivalent Courses: CMPT881.

Area III – Artificial Intelligence

CMPT 721 - Knowledge Representation and Reasoning (3)

Knowledge representation is the area of Artificial Intelligence concerned with how knowledge can be represented symbolically and manipulated by reasoning programs. This course addresses problems dealing with the design of languages for representing knowledge, the formal interpretation of these languages and the design of computational mechanisms for making inferences. Since much of Artificial Intelligence requires the specification of a large body of domain-specific knowledge, this area lies at the core of AI. Prerequisite: CMPT 310/710 recommended. Cross-listed course with CMPT 411.

CMPT 726 - Machine Learning (3)

Machine Learning is the study of computer algorithms that improve automatically through experience. Provides students who conduct research in machine learning, or use it in their research, with a grounding in both the theoretical justification for, and practical application of, machine learning algorithms. Covers techniques in supervised and unsupervised learning, the graphical model formalism, and algorithms for combining models. Students who have taken CMPT 882 (Machine Learning) in 2007 or earlier may not take CMPT 726 for further credit.

CMPT 823 - Formal Topics - Knowledge Representation (3)

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, non monotonic reasoning, inexact and imprecise reasoning, meta-reasoning, etc. Suggested preparation: a course in formal logic and a previous course in artificial intelligence.

CMPT 825 - Natural Language Processing (3)

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 - Automated Learning and Reasoning (3)

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 term will vary, depending upon the instructor, but most of the following topics will be addressed in any given term: 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 - Intelligent Systems (3)

Intelligent systems are knowledge-based computer programs which emulate the reasoning abilities of human experts. This introductory course will analyze 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.

Area IV – Databases, Data Mining and Computational Biology

CMPT 740 - Database Systems (3)

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 741 - Data Mining (3)

The student will learn basic concepts and techniques of data mining. Unlike data management required in traditional database applications, data analysis aims to extract useful patterns, trends and knowledge from raw data for decision support. Such information are implicit in the data and must be mined to be useful.

CMPT 829 - Special Topics in Bioinformatics (3)

Examination of recent literature and problems in bioinformatics. Within the CIHR graduate bioinformatics training program, this course will be offered alternatively as the problem-based learning course and the advanced graduate seminar in bioinformatics (both concurrent with MBB 829). Prerequisite: Permission of the instructor.

CMPT 843 - Database and Knowledge-base Systems (3)

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.

Area V – Graphics, HCI, Vision and Visualization

CMPT 764 - Geometric Modelling in Computer Graphics (3)

Advanced topics in geometric modelling and processing for computer graphics, such as Bezier and B-spline techniques, subdivision curves and surfaces, solid modelling, implicit representation, surface reconstruction, multi-resolution modelling, digital geometry processing (e.g., mesh smoothing, compression, and parameterization), point-based representation, and procedural modelling. Prerequisite: CMPT 361, MACM 316. Students with credit for CMPT 464 or equivalent may not take this course for further credit.

CMPT 820 - Multimedia Systems (3)

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. Equivalent Courses: CMPT880.

CMPT 822 - Computational Vision (3)

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 828 - Illumination in Images and Video (3)

Explores current research in the field of imaging, computer vision, and smart cameras that aims at identifying, eliminating, and re-lighting the effects of illumination in natural scenes. One salient direction in this research is the identification and elimination of shadows in imagery. The topics touched on in the endeavour include physics-based image understanding, image processing, and information theory. Students in vision and in graphics should be interested in the material in this course.

CMPT 888 - Special Topics in Computer Graphics, HCI, Vision and Visualization (3)

Examines current research topics in computer graphics, human computer interaction (including audio), computer vision and visualization.

Table 2

CMPT 880 - Special Topics in Computing Science (3)

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

The course requirements have a distribution requirement to ensure breadth across the major areas that are defined in Table 1. This requirement specifies the number of courses selected from each of the five major areas.

Depth Requirement and Examination

Students demonstrate depth of knowledge in their research area through a public depth seminar/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.

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 term in the program; a recommendation is made by the graduate breadth 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 the examining committee, and approved by the graduate program committee. The depth exam centres on the student’s research area. The examining committee, in consultation with the student, specifies the examination topics. The student prepares a written survey and gives a public depth seminar; the oral exam follows, and then the committee evaluates the student’s program performance. The committee’s evaluation is diagnostic, specifying additional work in weak areas if such exists. A second depth exam or withdrawal from the program may be recommended in extreme cases.

Thesis Proposal and Defence

The student, in consultation with the 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 terms of the depth examination.

Regulations specifying the examining committee composition and procedures for the final public thesis defence are in the graduate general regulations. PhD students present 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 final thesis defence.

Supervisory Committees

A supervisory committee consists of the student’s senior supervisor, at least one other computing science faculty member, and others (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 remainder of the committee members.

Graduate general regulation 1.6 specifies that a senior supervisor be appointed normally no later than the beginning of the student’s third term in the program, and that the remainder of the supervisory committee be chosen normally in the same term in which the senior supervisor is appointed.

Academic Requirements within the Graduate General Regulations

All graduate students must satisfy the academic requirements that are specified in the Graduate General Regulations, as well as the specific requirements for the program in which they are enrolled.