General Prerequisites

The following requirements must be met before enrollment is permitted in any 4000-level computer science course.

* COSC2001.03, COSC2011.03, COSC2021.03 completed

* at least 12 credits in COSC courses at the 3000-level completed

* a cumulative gpa of 5.0 in completed computer science courses

* MATH2090.03 completed

* Specific prerequisites may apply

COSC 4001.06

Space and Communication Sciences

Design Workshop (same as SC/EATS4001.06 and SC/PHYS4001.06)

Individual projects will be assigned by mutual agreement between the student and a faculty member. The work may be done under supervision by the faculty member, or under supervision of an industrial associate to that faculty member. The projects will be self-contained problems of a design nature, and will be pursued in the manner of a space project. Thus, the first step is to define the requirements of the design, the second to carry out a review of previous work, and the third to execute the design. Following that, the design shall be tested, normally through simulation, and conclusions drawn. A report of professional quality shall be written and submitted.

Prerequisites: Satisfactory completion of the 3000-level courses in the Space and Communication Science core

Degree Credit Exclusions: COSC4080.03, EATS40001.06, PHYS4001.06

Course director: E. Milios

COSC 4080.03

Computer Science Project

This is a course for advanced students, normally those in the fourth year of an honours programme, or students who have completed six full computer science courses. Students who have a project they wish to do, need to convince a member of the faculty in the department that it is appropriate for course credit. Alternatively, students may approach a faculty member in the Department (typically, one who is teaching or doing research in the area of the project) and ask for project suggestions. Whatever the origin of the project, a `contract' is required. It must state the scope of the project, the schedule of work, the resources required, and the criteria for evaluation. The contract must be signed by the student and his/her project supervisor and be acceptable to the course director.

Internship students may elect to receive credit for their internship as a project course. This is outlined further at the beginning of this calendar. A 'contract' is still required.

Prerequisites: general prerequisites; permission of the course director. Restricted to students who have completed 36 credits in Computer Science.

Degree Credit Exclusions: COSC4001.06

Course director: G. Gotshalks

COSC 4101.03 (x-listed COSC 5191)

Advanced Data Structures

Section A (Fall) Tues, Thurs 2:30-4:00

Section M (Winter) Tues, Thurs 8:30-10:00

The course discusses advanced data structures: heaps, balanced binary search trees, hashing tables, red--black trees, B--trees and their variants, structures for disjoint sets, binomial heaps, Fibonacci heaps, finger trees, persistent data structures, etc. When feasible, a mathematical analysis of these structures will be presented, with an emphasis on average case analysis and amortized analysis. If time permits, some lower bound techniques may be discussed, as well as NP-completeness proof techniques and approximation algorithms.

The course may include the following topics.

* Amortized and worst-case analysis of data structures.

* Data structuring paradigms: self-adjustment and persistence.

* Lists: self-adjustment with the move-to-front heuristic.

* Search trees: splay trees, finger search trees.

* Heaps: skew heaps, fibinacci heaps.

* Union-find trees.

* Link-and-cut trees.

* Multidimentional data structures and dynamization.

Texts: t.b.a.

Suggested reading: T.H.Cormen, C.E.Leiserson, R.L.Rivest, Introduction to Algorithms, McGraw-Hill, 1990.

Prerequisites: General prerequisites, including COSC 3101.03 and MATH2320.03

Course director: Section A T. Papadakis

Section M t.b.a.

COSC 4111.03

Automata and Computability

Section M (Winter) Mon, Wed, Fri 2:30

This course is the second course in the theory of computing. It is intended to introduce students to the formal method of analysis of computational phenomena intuitively described as computability, unsolvability, complexity, etc, their meanings and theoretical importance. Topics chosen for study include: models of Turing machines and the techniques for their construction; undecidability phenomena; introduction to computational complexity theory; intractable problems.

Texts: t.b.a.

Prerequisites: General prerequisites, including COSC

3101.03; MATH2320.03.

Course director: Z. Stachniak

COSC 4201.03

Computer Architecture

Section A (Fall) Tues, Thurs 2:30-4:00

This course presents the core concepts of computer architecture and design ideas embodied in many machines and emphasizes a quantitative approach to cost/performance tradeoffs. This course concentrates on uniprocessor systems. A few machines are studied to illustrate how these concepts are implemented; how various tradeoffs that exist among design choices are treated; and how good designs make efficient use of technology. Future trends in computer architecture are also discussed.

Topics covered may include the following.

* Fundamentals of computer design

* Performance and cost

* Instruction set design and measurements of use

* Basic processor implementation techniques

* Pipeline design techniques

* Memory-hierarchy design

* Input-output subsystems

* Future directions


* J. Hennesey and D. Patterson, Computer Architecture

* A Quantitative Approach, Morgan Kauffmann Publishers, Inc., 1990.

Prerequisites: General prerequisites, including COSC 3201.03 and COSC3321.03

Course director: D.L. Lee

COSC 4211.03

Performance Evaluation of Computer


(not offered in FW94/95)

Topics covered may include the following.

* Review of Probability Theory - probability, conditional probability, total probability, random variables, moments, distributions (Bernoulli, Poisson, exponential, hyperexponential, etc.)

* Stochastic Processes - Markov chains and birth and death processes

* Queueing Theory - M/M/1 Queueing system in detail; other forms of queueing systems including limited population and limited buffers.

* Application - A case study involving use of the queuing theory paradigm in performance evaluation and modeling of computer systems such as open networks of queues and closed queuing networks. Use of approximation techniques, simulations, measurements and parameter estimation.

Texts: t.b.a.

Prerequisites: General prerequisites, including COSC 3211.03 and COSC3408.03

COSC 4242.03 (x-listed COSC 5391)

Signals and Systems

Section A (Fall) Tues, Thurs 6:30-8:00

The study of computer vision, graphics and robotics requires background in the concept of discrete signals, filtering, and elementary linear systems theory. Discrete signals are obtained by sampling continuous signals.

In this course, students will review the concept of a discrete signal, the conditions under which a continuous signal is completely represented by its discrete version, linear time-invariant systems.

Topics covered may include the following.

* Continuous and discrete signals

* Linear time-invariant systems

* Fourier analysis in continuous time

* Fourier analysis in discrete time

* Sampling

* Filtering, image enhancement

* Laplace transform

* Z transform

* Linear feedback systems

* Random signals, image coding

* Kalman filtering

* Statistical pattern recognition

Text: A. V. Oppenheim, A. S. Willsky, Signals and Systems, Prentice Hall, 1983

Prerequisites: General prerequisites; COSC3121.03 or AS/SC/MATH3241.03.

Degree Credit Exclusion: COSC4010B.03, SC/ACMS/4020.03, SC/EATS4020.03, AS/SC/ MATH4830.03, SC/PHYS4060.03.

Course director: E. Milios

COSC 4301.03

Programming Language Design

Section M (Winter) Mon, Fri 4:30-6:00

This course is a continuation of COSC3301.03 Programming Language Fundamentals. Like its predecessor, the course focuses on the linguistics of programming languages; that is, on the common, unifying themes that are relevant to programming languages in general. Both algorithmic and nonalgorithmic language categories are examined. Current techniques for the formal specification of the syntax and semantics of programming languages are studied. Skills are developed in the critical and comparative evaluation of programming languages.

Texts: t.b.a.

Prerequisites: General prerequisites, including COSC 3301.03

Course director: M. Wharton

COSC 4302.03

Language Processors

Section A (Fall) Mon, Wed, Fri 12:30

This course is concerned with a variety of theoretical and practical questions that are raised by the need to implement programming languages. The implementation of a language is accomplished by the production of a program known as a "processor" or "translator". Language processors may be categorized as compilers, cross-compilers, interpreters, assemblers and pre-processors. However, the different kinds of processors generally exhibit a common internal structure consisting of standardized "phases": the scanner, parser and semantics. The focus in this course is on the most important class group of language processors: compilers.

Some of the questions to be considered are the following: How can the syntax and semantics of a programming language be specified? How does the specification of the syntax of a programming language relate to the design of a parser for the language? How can the semantic actions of a programming language be implemented? What data structures are required by a language processor?

As a practical exercise, students are required to design and implement components of a language processor.

Texts: t.b.a.

Prerequisites: General prerequisites, including COSC 3301.03

Course director: M. Wharton

COSC 4311.03

System Development

Section M (Winter) Mon, Wed 8:30-10:00

The use and the harnessing of concurrency in system design. A mathematical study of concurrency and communication. Specification, design and implemention of computer systems which continuously interact with other systems.

This course focuses on abstraction, specification, and analysis in software system development. Abstraction and specification can greatly enhance the understandability, reliability and maintainability of a system. Analysis of concurrency and interaction is essential to the design of a complex system of interacting processes.

The course covers process abstraction and communication abstraction, informal and formal specifications, analysis of interacting processes, trends in software system design. Time permitting it may also survey software engineering tools used in industry.

Texts: t.b.a.

Prerequisites: General prerequisites, including COSC 3311.03, and COSC3111.03 or COSC3321.03.

Course director: G. Gotshalks

COSC 4321.03 (x-listed COSC 5421)

Operating System Design

Section M (Winter) Mon, Wed 6:00-7:30

An operating system has four major components: process management, input/output, memory management, and the file system. This project- oriented course puts operating system principles into action. This course presents a practical approach to studying implementation aspects of operating systems. A series of projects is included, making it possible for students to acquire direct experience in the design and construction of operating system components. A student in this course must design and implement some components of an operating system and have each interact correctly with existing system software. The programming environment is C++ under Unix. At the end of this course, a student will be able to design and implement the basic components of operating systems.

A solid background in operating systems concepts, computer architecture, C, and UNIX is expected.

Texts: Bacon, J., Concurrent Systems, and a course reader available from Department of Computer Science.

Prerequisites: General prerequisites, including COSC 3321.03.

Course director: T. Brecht

COSC 4331.03 (x-listed COSC 5431)

Computer Graphics

Section A (Fall) Mon, Wed Fri 9:30

Section M (Winter) Mon, Wed, Fri 11:30

This course introduces the student to the fundamental algorithms of 3-D computer graphics and image synthesis.

The first half of the course will cover window systems, display hardware, graphical primitives, scan conversion, two and three-dimensional transformations and the mathematics of planar geometric projection.

The second half will concentrate on raster algorithms and image synthesis. Some of the topics include visible surface algorithms, modeling, shading, global illumination, anti-aliasing and texture mapping.

Students are expected to be familiar with C and UNIX and will be using the X window environment on the undergraduate workstations.

Texts t.b.a.

Prerequisites: general prerequisites; MATH2221.03

Course director: Section A M. Jenkin

Section M J. Amanatides

COSC 4341.03 (x-listed COSC 5491)

Interactive System Design

Section M (Winter) Mon, Wed, Fri 10:30

Recent studies have shown that on average, 50% of the costs of modern application programs come from the development of the program's user interface. At the same time, users of programs are becoming increasingly aware and critical of poorly designed user interfaces. The modern system designer must, therefore, be capable of creating systems that are easy to use and that truly address the needs of the users, while still managing to remain within budget.

This course introduces the concepts and technology necessary to manage the design and implementation of interactive software. Students will learn methods for designing software matched to the goals, tasks and skills of the eventual users of the system. A development methodology is presented in which each development stage involves evaluation of the quality of the system design. Units in the course will cover User Needs Analysis, User Interface Design, Task-Oriented Specification, Architecture Design of Interactive Systems, System Implementation, and User Testing and Evaluation.

The course is based on a project which involves programming in Turing, a Pascal-like language. Students are expected to learn Turing on their own.

Texts: t.b.a.

Prerequisites: general prerequisites.

Course director: N. Graham

COSC 4351.03

Real-Time Systems Theory

Section A (Fall) Tues 12:30-2:30, Thurs 12:30

In real-time computing systems the correctness of the system depends not only on the logical result of the computation but also on the time at which the results are produced. For example, a computer controlling a robot on the factory floor of a flexible manufacturing system, must stop or turn the robot aside in time to prevent a collision with some other object on the factory floor. Other examples of current real-time systems include communication systems, traffic systems, nuclear power plants and space shuttle and avionic systems.

Real-time programs in many safety-critical systems are more complex than sequential programs or concurrent programs that do not have real-time requirements. This course will deal with the modelling, simulation, specification, analysis, design and verification of such real-time programs. The objective of the course is to expose the student to current techniques for formally proving the correctness of real-time behaviour of systems.

Topics covered may include the following.

* Techniques for expressing syntax and semantics of real-time programming languages

* Modelling real-time systems with discrete event calculi (e.g. Petri net and state machine formalisms)

* Specification of concurrency, deadlock, mutual exclusion, delays and timeouts

* Scheduling of tasks to meet hard time bounds.

* CASE tools for analysis and design. At the end of the course the student will be able to model and specify real-time systems, design and verify correctness of some real-time systems.

Texts: t.b.a.

Prerequisites: General prerequisites, including COSC 3311.03 or COSC3321.03 or COSC3111.03.

Course director: J. Xu

COSC 4352.03

Real-Time Systems Practice

Section M (Winter) Mon, Wed 2:30-4:00

In real-time computing systems the correctness of the system depends not only on the logical result of the computation but also on the time at which the results are produced. For example, a computer controlling a robot on the factory floor of a flexible manufacturing system, must stop or turn the robot aside in time to prevent a collision with some other object on the factory floor. Other examples of current real-time systems include communication systems, traffic systems, nuclear power plants and space shuttle and avionic systems.

This course is an introduction to the use and applications of real-time systems and programming languages. The course will include the following among other things.

* Real-Time systems specification methods such as State charts and Petri Nets.

* CASE tools such as Statemate for designing and analyzing real time systems. Behavioural, structural and data-flow views of complex safety critical systems.

* At least one example of a real-time language, such as Ada, Pearl, Conic or Occam will be studied, concentrating on facilities for concurrency and timing.

Prerequisites: General prerequisites, including COSC 3301.03 or COSC3311.03 or COSC3321.03

Course director: J. Ostroff

COSC 4361.03

Human-Computer Communication (formerly COSC4010A.03)

Section A (Fall) Wed, Fri 2:30-4:00

The course focuses this year on the design and implementation of hypermedia presentation systems. "Hypermedia" refer to the non-linear organization of digital information, in which items (such as a word in a text field or a region of an image) are actively linked to other items. Users interactively select and traverse links in a hypermedia presentation system in order to locate specific information or entertainment, or to browse in large archives of text, sound, images, and video. Well-structured hypermedia give users a way of coping with the "navigation" problem created by availability of low-cost, fast access, high-density storage media.

We may explore the following topics.

* The historical roots of hypermedia: Bush, Engelbart, and Nelson;

* Building simple presentation applications using HyperCard and HyperTalk;

* The digital representation of media: rich text, sound, speech, images, animation, and video;

* The role of scripting and markup languages;

* Networked hypermedia (WWW/Mosaic);

* QuickTime, XCMDs, AppleScript, Script X;

* Design of a high-level scripting language for hypermedia documents;

* Design of a presentation system for hypermedia archives.

Students will be expected to familiarize themselves quickly with the Macintosh interface, and with HyperTalk programming concepts. A knowledge of C or C++ will be useful.

Students will be asked to schedule themselves for at least six hours/week lab time in the Department's Macintosh Lab (158 CCB), as the course work will involve a significant amount of exploring and developing multimedia/hypermedia software. Students will be divided into small teams with specific responsibilities for individual programming tasks assigned in connection with the course topics. Tasks may take the form of constructing prototype applications (using HyperTalk), or the programming of useful procedures (using C or C++). The teams will be asked to write short reports on their work which will be presented in class.

Text: t.b.a.

Prerequisites: general prerequisites; plus an additional 6 credits at the 3000-level.

Degree Credit Exclusion: COSC4010A.03.

Course director: P. Roosen-Runge

COSC 4401.03 (x-listed COSC 5393)

Topics in Artificial Intelligence

Section M (Winter) Tues, Thurs 2:30-4:00

This course will be an in-depth treatment of one or more specific topics within the field of Artificial Intelligence. Possible topics include the following.

* Machine learning: deduction, induction, abduction, explanation-based learning, learning k-DNF.

* Statistical learning: reinforcement learning, genetic learning algorithms, connectionist learning systems, supervised and unsupervised.

* Statistical and structural pattern recognition.

* Speech recognition.

* Artificial intelligence programming paradigms: search, pattern-directed inference, logic- and object-oriented programming, symbolic mathematics, constraint satisfaction and symbolic relaxation, building problem solvers, efficiency issues.

* Sensor-based robotics: path planning, position estimation, map-building, object recognition, robotic sensor and actuator hardware, software, and interfacing.

Contact the course director for information regarding the focus of the course this year.

Texts: t.b.a.

Prerequisites: General prerequisites, including COSC 3402.03

Course director: E. Milios

COSC 4402.03 (x-listed COSC 5311)

Logic Programming

Section M (Winter) Mon, Wed, Fri 12:30

Logic programming has its roots in mathematical logic and it provides a view of computation which contrasts in interesting ways with conventional programming languages. Logic programming approach is rather to describe known facts and relationships about a problem, than to prescribe the sequence of steps taken by a computer to solve the problem.

One of the most important problems in logic programming is the challenge of designing languages suitable for describing the computations which these systems are designed to achieve. The most commonly recognized language is PROLOG.

When a computer is programmed in PROLOG, the actual way the computer carries out the computation is specified partly by the logical declarative semantics of PROLOG, partly by what new facts PROLOG can "infer" from the given ones, and only partly by explicit control information supplied by the programmer. Computer Science concepts in areas such as artificial intelligence, database theory, software engineering knowledge representation, etc., can all be described in logic programs.

Topics covered may include the following.

* Logical preliminaries: syntax and semantics of first order predicate logic and its Horn logic fragment;

* Logical foundations of logic programming: unification, the resolution rule, SLD-resolution and search trees;

* PROLOG as a logic programming system;

* Programming techniques and applications of PROLOG;

* Constrained logic programming systems.

At the end of this course a student will be familiar with fundamental logic programming concepts and will have some programming expertise in PROLOG.

Texts: t.b.a.

Prerequisites: General prerequisites, including COSC 3401.03, and COSC3101.03 or COSC3111.03.

Course director: Z. Stachniak

COSC 4411.03

Database Management Systems

Section A (Fall) Tues, Thurs 10:00-11:30

The focus of the course is on design theory for relational databases. Theory of functional dependencies, normal forms and multivalued dependencies, relational models based on relational algebra and calculus and query languages based on these concepts are studied. Two thirds of the course would be dedicated to the above concepts. Other topics, possibly covered by student presentations, would include: distributed databases, query optimization, security and integrity, and concurrency control.

Texts: t.b.a.

Prerequisites: General prerequisites, including COSC3412.03.

Course director: J. Xu

COSC 4421.03 (x-listed COSC 5324)

Introduction to Robotics

Section M (Winter) Tues 12:30-2:30, Thurs 12:30

The course introduces the basic concepts of robotic manipulators and autonomous systems. After a review of some fundamental mathematics the course examines the mechanics and dynamics of robot arms. In particular forward and inverse kinematics, force and velocity, inertia and control. A Robotics Laboratory is available equipped with a manipulator and a moving platform with sonars, several workstations and an extensive collection of software.

Texts: J. Craig, Introduction to Robotics: Mechanics and Control, 2nd edition, Addison Wesley.

Prerequisites: MATH2221.03; general prerequisites.

Course director: M. Spetsakis

COSC 4422.03 (x-listed COSC 5323)

Computer Vision

Section A (Fall) Mon, Wed, Fri 11:30

Computer Vision is a very challenging problem with wide applications. It spans several disciplines within science and engineering: computer science, computer engineering, photogrammetry, telecommunications, robotics, medicine and the list goes on. This course introduces the fundamental concepts of vision with emphasis on computer science.

In particular the course covers the image formation process, color analysis, image processing, enhancement and restoration, feature extraction and matching, 3-D parameter estimation and applications. A Vision Laboratory is available where students can gain practical experience. The Lab includes several workstations equipped with video cameras, digitizers and image processing software.

Texts: t.b.a.

Prerequisites: general prerequisites, including COSC3121.03

Course director: M. Jenkin