3000-Level

General Prerequisites

The following requirements must be met before enrollment is permitted in any 3000-level computer science course (except service courses - 35xx.xx).

* COSC2011.03 completed

* One of COSC2001.03 or COSC2021.03 completed

* A cumulative grade point average of 4.0 or better over all completed Computer Science courses

* MATH1300.03 and MATH1310.03 completed

* One of MATH2090.03, MATH2221.03, or MATH2320.03 completed

* Specific prerequisites may also apply

Warning: Some upper level courses use the C programming language, therefore you may want to plan on completing COSC2031.03. Starting in the academic year 1995/96 computer science upper level courses will assume students have a working knowledge of C++, as presented in COSC3010A.03 or COSC2011.03 as taught in 1994/95

COSC 3001.01

Organization and Management Seminar in Space and Communication Sciences

(same as SC/EATS3001.01 and SC/PHYS3001.01)

Full Year Every second Tues 5:00

A seminar course taught by guest speakers from industry, government and the university. Content changes from year to year, but includes such topics as professional ethics, communications regulations, space law, space science policy, project management, privacy and security issues in computing.

Prerequisites: Eligibility to proceed in the Specialized Honours stream in SCS beyond the 2000-level requirements.

Degree Credit Exclusions: EATS 3001.01, PHYS 3001.01

Course director: t.b.a.

COSC 3010A.03

Object-Oriented Software Design and

Programming

COSC3010A (Winter) Tues 12:30-2:30, Thurs 12:30

This course is a detailed introduction to the methodology and practice of Object-Oriented software construction, one of the major areas of software engineering practice and research.

A source program in an object-oriented programming environment is based on independently defined abstract program units called object classes or types; the object instances of the classes are created in the program and interact through message passing at run-time. Each object is a program unit which packages both a coherent collection of data elements and the methods (routines) for their manipulation. The object encapsulates its data elements, which means that the object class has an interface which defines all and only what is visible about the object instances to other objects in the program environment. These techniques promote the reuse of reliable code and reduce the frequency of the kinds of programming which arise in attempting to integrate the different parts of a complex programming task.

The course will introduce the concepts of object-oriented programming and design. The language used in the course is C++.

Among the topics to be covered may be following.

* The definition of Abstract Data Types (ADTs) through generalized object class interfaces.

* The construction of a hierarchy of data types from ADTs down to the most specialized types, in which types are derived from one or more ancestor types by inheritance and refinement.

* The contract model of software design.

* Constraint based programming to ensure the correctness of methods, class invariants, loop invariants, etc.

* Polymorphism and templates as an approach to algorithm generalization.

* Static versus dynamic binding of algorithms to method calls.

* Object class library design to provide reusable software components.

Texts: t.b.a.

Prerequisites: general prerequisites; knowledge of the C language is recommended.

Course director: E. Arjomandi

COSC 3101.03

Design and Analysis of Algorithms

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

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

This course is intended to teach students the fundamental techniques in the design of algorithms and the analysis of their computational complexity. Each of these techniques are applied to a number of widely used and practical problems. At the end of this course, a student will be able to: choose algorithms appropriate for many common computational problems; to exploit constraints and structure to design efficient algorithms; and to select appropriate tradeoffs for speed and space. Various program animation softwares may also be used as an interactive pedagogical tool in the course.

Topics covered may include the following.

* Review: fundamental data structures, asymptotic notation, solving recurrences.

* Sorting and order statistics: heapsort and priority queues, randomized quicksort and its average case analysis, decision tree lower bounds, linear-time selection.

* Divide-and-conquer: binary search, quicksort, mergesort, polynomial multiplication, arithmetic with large numbers.

* Dynamic Programming: matrix chain product, scheduling, knapsack problems, longest common subsequence, some graph algorithms.

* Greedy methods: activity selection, some graph algorithms.

* Amortization: the accounting method, eg, in Graham's Scan convex hull algorithm.

* Graph algorithms: depth-first search, breadth-first search, biconnectivity and strong connectivity, topological sort, minimum spanning trees, shortest paths.

* Theory of NP-completeness.

Texts: t.b.a.

Suggested reading:

* T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, McGraw-Hill and The MIT Press, 1991.

* P. Gloor, S. Dynes, I. Lee, Animated Algorithms CD-ROM, The MIT Press 1993.

* D.E. Knuth, The Stanford GraphBase: A platform for combinatorial computing, Addison-Wesley & The ACM Press, 1993.

Prerequisites: general prerequisites, including MATH2320.03 (SCS students may enrol without MATH2320.03 or concurrently with MATH2320.03)

Course director: Section A X. Deng

Section M t.b.a.

NOTE: This course is required of all specialized honours students in computer science - except those in the SCS stream.

COSC 3111.03

Introduction to Program Verification

Section M (Winter) Mon, Wed 11:30-1:00

Every program implicitly asserts a theorem to the effect that if certain input conditions are met then the program will do what its specifications or documentation says it will. Making that theorem true is not merely a matter of luck or patient debugging; making a correct program can be greatly aided by a logical analysis of what it is supposed to do, and for small pieces of code a proof that the code works can be produced hand-in-hand with the construction of the code itself. Good programming style works in part because it makes the verification process easier and this in turn makes it easier to develop more complex algorithms from simple ones.

The course will provide an introduction to the basic concepts of formal verification methods. It will also including the use of simple tools to aid in verification.

Topics covered may include the following.

* The role of formal verification in the software life-cycle; verification vs. testing and validation

* Introduction to propositional calculus; checking for tautologies and contradictions; annotating code with assertions

* Moving from goals to starting points; proving relative correctness for small code segments

* Creating specifications with quantifiers; translating specifications into loops; establishing termination

* Possibilities for the automatic synthesis of programs from specifications.

Texts: t.b.a.

Suggested readings:

* Backhouse, R., Program Construction and Verification, Prentice-Hall: 1986.

* Gries, D., The Science of Programming, Springer-Verlag: 1981.

Prerequisites: General prerequisites, including MATH 2090.03

Course director: J. Ostroff

COSC 3121.03

Introduction to Numerical Computations I

(same as AS/SC/MATH 3241.03)

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

This course is concerned with an introduction to matrix computations in linear algebra for solving the problems of linear equations, interpolation and linear least squares. Errors due to representation, rounding and finite approximation are studied. Ill-conditioned problems versus unstable algorithms are discussed. The Gaussian elimination with pivoting for general system of linear equations, and the Cholesky factorization for symmetric systems are explained. Orthogonal transformations are studied for computations of the QR decomposition and the Singular Values Decompositions (SVD). The use of these transformations in solving linear least squares problems that arise from fitting linear mathematical models to observed data is emphasized. Finally, polynomial interpolation by Newton's divided differences and spline interpolation are discussed as special cases of linear equations. The emphasis of the course is on the development of numerical algorithms, the use of intelligent mathematical software and the interpretation of the results obtained on some assigned problems.

Topics covered may include the following.

* Preliminaries - linear algebra, computer programming and mathematical software

* Number Systems and Errors - machine representation of numbers, floating-point arithmetic, simple error analysis, ill-conditioned problems and unstable algorithms

* Solution of Systems of Linear Equations - Gaussian elimination and its computational complexity, pivoting and stability, special structures (Cholesky's factorization for positive definite systems, banded systems, storage and computational complexities) error analysis, condition number and iterative refinement

* Solution of Overdetermined Systems of Linear Equations by Linear Least Squares Approximations - linear least squares problems, normal equations, orthogonal transformations (Given's and Householder's), QR and Singular Values Decompositions (SVD), SVD and rank-deficient problems, computational complexities versus robustness

* Interpolation - Newton's divided differences spline interpolation; banded linear systems, error analysis for interpolation. Other interpolations (rational, B-splines)

Texts: t.b.a.

Prerequisites: for Computer Science majors - General prerequisites, including MATH2221.03; for others - COSC1030.03 or COSC1530.03 or COSC1540.03; MATH1025.03 or MATH2221.03 or MATH2021.03

Degree credit Exclusion: ACMS3010.06; MATH3241.03

Course director: t.b.a.

COSC 3122.03

Introduction to Numerical Computations II

(same as AS/SC/MATH3242.03)

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

The course includes a study of algorithms and computer methods for differentiation, integration, and solution of ordinary differential equations. Nonlinear equations of one variable, systems of nonlinear equations, optimization of functions of one and several variables and their relation to nonlinear equations are also covered. The emphasis of the course is on the development of numerical algorithms, the use of intelligent mathematical software and the interpretation of the results obtained on some assigned problems.

Topics covered may include the following.

* Solution of Nonlinear Equations and Unconstrained Optimization - single nonlinear equation; systems of nonlinear equations; unconstrained optimization.

* Numerical Differentiation and Integration - methods of estimating derivatives; error analysis for differentiation; the rectangle and trapezoid rule for integration; Simpson's rule; Romberg's integration; adaptive quadrature routines; truncation and round-off errors in integration; improper integrals.

* Solution of Ordinary Differential Equations - introduction; analytical versus numerical solutions; basic numerical methods; Euler's, Heun's methods; Taylor series methods; order of a method; local and global errors; Runge-Kutta methods; Predictor-corrector methods; systems of differential equations; boundary value problems.

Texts: t.b.a.

Prerequisites: COSC3121.03; MATH2270.03

Degree Credit Exclusion: ACMS3010.06; MATH3242.03

Course director: t.b.a.

COSC 3201.03

Digital Logic Design

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

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

Introduction to logic design. Analysis and design of combinatorial and sequential circuits. Standard MSI and LSI circuits, programmable logic device (PLD), and their use in the design of digital systems. Reliable design and fault detection. Laboratory experiments.

Digital logic design is concerned with the design of digital systems. The best known example of a digital system is a digital computer. This course is intended to teach students the fundamental concepts in digital logic design as well as the basic techniques used to construct digital systems with widely used MSI, LSI, and PLD components. Use of such devices for implementation of digital circuits is explored through the use hands-on hardware laboratory. In addition, students are introduced to computer-aided design software to assist in the process of complex hardware design.

At the end of this course, a student will be able to use a wide range of software tools; to use MSI, LSI, and PLD components; to choose methods suitable for a variety of logic design applications; and to make tradeoffs for performance and cost.

Topics covered may include the following.

* Boolean algebra and Boolean minimization

* Hardware technologies

* Combinational logic design

* Sequential logic design

* Finite state machine design

* Finite state machine optimization

* Finite state machine implementation

Texts:

* Randy H. Katz, Contemporary Logic Design, The Benjamin/Cummings Publishing Company, 1993.

* Capilano Computing Systems, Ltd., LogicWorks: Interactive circuit design software, The Benjamin/Cummings Publishing Company, 1994.

Suggested readings:

* John Hays, Introduction to Logic Design, Addison Wesley, 1993.

* M.M. Mano, Digital Design, Prentice Hall, 1991.

Prerequisites: General prerequisites, including

COSC2021.03 or COSC2020.06.

Course director: Section A M. Spetsakis

Section M D.L. Lee

COSC 3211.03

Data Communication

Section A (Fall) Mon, Wed 10:00-11:30

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

Topics covered may include the following.

* Introduction to the topic of Data Communication and the ISO OSI layered model, comparing the OSI model with the existing networks (ARPA, SNA, DECNET)

* Physical Layer and Electrical Interface - Data transmission, synchronous vs asynchronous, parallel vs serial, analog vs digital; data encoding (line coding techniques), error detection, error correction techniques; RC-232-C and X21

* Data Link Layer - protocols (from a simplex protocol with no noise in the communication channel to protocols with pipelining and accept frames out of order); packet radio networks; satellite networks and LAN; protocol specifications methods (finite state machines, Petri Nets, pseudo code)

* The Network Layer - Virtual Circuits and data-grams; routing algorithms (centralized vs distributed routing, static vs adaptive routing, and flow control); the network layer in existing systems (ARPANET, SNA, and DECNET).

Texts: t.b.a.

Prerequisites: general prerequisites, including COSC2021.03 and MATH2090.03

Course director: t.b.a.

COSC 3212.03

Computer Networks

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

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

Topics covered may include the following.

* Introduction to the topic of computer networks. Introduction to graph theory, delay analysis, traffic allocation. Local Access and backbone design

* Transport and Session Layers - transport protocol, addressing, buffering multiplexing, crash recovery, dialog management, synchronization remote procedure calling, example of transport and session layers in some existing networks.

* Presentation layer - issues in security and encryption, data compression techniques, cryptography, examples of existing presentation layers

* Application layer - File Transfer Program, virtual terminal protocol, electronic mail.

* Internetworking - internetworking concept and architectural model, TCP/IP, and Gateways.

Texts: t.b.a.

Prerequisite: COSC3211.03

Course director: Section A A. Wallis

Section M A. Wallis

COSC 3301.03

Programming Language Fundamentals

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

The topic of programming languages is an important and rapidly changing area of computer science. This course introduces students to the basic concepts and terminology used in describing programming languages. The emphasis is on algorithmic languages: languages such as Pascal, Modula-2, C, Ada, Algol 68, PL/I, Fortran and Basic, which are directly or indirectly derived from Algol 60. Instead of studying particular languages, the course focuses on the linguistics of programming languages; that is, on the common, unifying themes that are relevant to programming languages in general.

This course is not designed to meet the needs of the student who wishes to learn to write computer programs in a particular language. However, any student who completes this course should be able to learn any new programming language with relative ease.

Texts: t.b.a.

Prerequisites: General prerequisites, including COSC 2001.03 and MATH2090.03

Course director: M. Wharton

COSC 3311.03

Software Design

Section A (Fall) Mon, Wed 8:30-10:00

A program which does not work is undoubtedly wrong; but a program which does work is not necessarily right. It may still be wrong because it is hard to understand or because it is hard to maintain as the program requirements change; or because its structure is different from the structure of the problem. (M. A. Jackson)

This course introduces the topic of software design through lectures, supplementary readings and a set of small design problems. The course deals with the problem of designing software that can be used, understood and modified by people other than the original designer.

Software design is in itself a large topic as design can deal with various classes of programs and systems: small, medium and large; batch; real time; distributed; and interactive (visual and graphical). Every design class has its own problems. In this course we deal with small to medium programs and small systems that work without critical time constraints (although time will be considered).

We examine design methods such as JSP (Jackson System Programming), Data Flow, SADT (Structured Analysis and Design Technique), top down, bottom up and structured design methods. We show how theoretical notions from finite state machines and grammars are related to and used in the design process.

Some of the low level techniques we look at are: abstract data types; backtracking; divide and conquer; structure clash resolution; process inversion; coroutines; and error handling.

Design issues are related to the other phases of developing a program: requirements analysis, specification, implementation, testing, and maintenance.

Upon leaving the course, you can expect to be able to design, implement and modify programs and systems of programs which transform sequences from one form to another. You will understand the role of tools and frames in the design process. You will be able to evaluate program designs and design methods.

Texts: t.b.a.

Prerequisites: General prerequisites, including COSC 2001.03; MATH2090.03

Course director: G. Gotshalks

COSC 3321.03

Operating System Fundamentals

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

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

This course is intended to teach students the fundamental concepts that underlie operating systems, including multiprogramming, concurrent processes, CPU scheduling, deadlocks, memory management, file systems, protection and security. Many examples from real systems are given to illustrate the application of particular concepts. At the end of this course, a student will be able to understand the principles and techniques required for understanding and designing operating systems.

Text: A. Silberschatz, J.L. Peterson, and P. Galvin, Operating System Concepts, Third Edition, Addison-Wesley, 1991.

Prerequisites: General prerequisites, including COSC2021.03

Course director: Section A M. Spetsakis

Section M M. Wharton

COSC 3401.03

Introduction to Symbolic Computation

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

The course will introduce and explore programming concepts used in symbolic and knowledge-based computing. It is intended to give the student a programming background which will be useful for further work in logic programming, expert systems, and artificial intelligence.

The programming language Prolog will be considered in detail. Prolog is a declarative programming language based on the concept of a logical assertion. It is widely used for constructing knowledge-based and expert systems.

The course will develop the following concepts.

* Terms as representations of facts

* Logical clauses as rules

* Recursive programming techniques

* Backward-chaining vs. forward-chaining

* Goal search through backtracking

* Building logical databases for knowledge-based problem-solving

* Representing mathematical knowledge by rewrite rules

* Natural language processing using grammar rules

Text: Rowe, N., Artificial Intelligence Through Prolog, Prentice-Hall 1988

Prerequisites: General prerequisites, including MATH 2090.03

Course director: P. Roosen-Runge

COSC 3402.03

Introduction to Concepts of Artificial

Intelligence

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

Artificial Intelligence (AI) deals with building a system which can operate in an intelligent fashion. Neat as this simple definition is, it obscures the complex nature of intelligence. At the time of the Dartmouth Conference (1956), regarded by many as the start of AI, some researchers believed it would be possible to create a "thinking machine" in a matter of a few years. That was close to 40 years ago, and we are still far from our goal, but we have learned a lot on the way.

In this course, we will begin by discussing differing definitions of artificial intelligence and go on to examine fundamental concepts in AI, building on material introduced in COSC3401.03: Introduction to Symbolic Computation. Topics will include reasoning under uncertainty, search, constraint propagation, planning and problem solving.

Text: Rowe, N., Artificial Intelligence Through Prolog, Prentice-Hall 1988

Prerequisites: COSC3401.03; MATH2320.03

Course director: P. Roosen-Runge

COSC 3408.03

Simulation of Discrete Systems

(not offered in FW94/95)

Simulation is a technique for dealing with problems that do not admit exact (or "analytic") solutions via mathematical analysis. A model of the system to be studied is constructed, and then the model is run to see how it performs, either to predict how the system will behave, or, if the behaviour of the system is known, to test the validity of the model of the system. A computer is a tool for supporting a large amount of activity in the running of the model.

A "discrete system" simulation is one which admits a discrete-event model that can run be in discrete steps that match the structure of the model. (For simulation of continuous systems see COSC 3418.03)

Examples of discrete systems studied by simulation include games and other dynamic systems involving small populations where it is feasible to model individual's behaviour. Major sub-topics include the generation and use of random numbers, queuing systems, and the visual presentation of behaviour.

Texts: t.b.a.

Prerequisites: general prerequisites; MATH2560.03 or equivalent.

COSC 3411.03

File Structures and Data Management

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

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

The purpose of this course is to introduce students to file organizations and the hardware and software involved in the creation and manipulation of files. The course presents basic concepts, criteria for choosing between alternative file organizations, and other topics that are important for the understanding of file management. At the end of this course a student will be able to understand and apply file organization techniques in design and analysis of file management systems.

Topics covered may include the following.

* Overview of data processing, file organizations. Review of external storage devices characteristics

* Sequential files

* Hash files

* Indexed sequential files

* B-trees, B+-trees, B*-trees

* Tries and Patricia

* Multi-key file organizations

* Data encoding

* External sorting

* Buffer and memory management

Texts: M.J. Folk and B. Zoellick, File Structures, 2nd edition, Addison-Wesley, 1992.

Suggested readings: P.D. Smith and G.M. Barnes, Files and Databases: an Introduction, Addison Wesley, 1987.

Prerequisites: General prerequisites, including COSC 2021.03 and MATH2090.03; knowledge of the C language is recommended

Course director: Section A E. Arjomandi

Section M T. Papadakis

COSC 3412.03

Introduction to Database Management

Systems

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

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

Concepts, approaches and techniques in database management systems (DBMS). Logical models of databases: relational, network and hierarchical DBMSs. An introduction to relational database design. Other topics such as query processing, crash recovery and concurrency control.

The purpose of this course is to introduce students to the fundamental concepts of database systems. The four major database models: the relational model, the entity-relationship model, the network and the hierarchical model are treated. However, the relational model and the design of relational databases are emphasized, due to their increasing importance in database research and practical industrial application. Other important aspects of database systems - query processing, crash recovery and concurrency control may be also discussed. At the end of this course, a student will be able to understand and apply database system concepts in the use or design of database management systems.

Topics covered may include the following.

* Intro. to database management systems

* Entity-Relationship Model

* Hierarchical Model

* Network Model

* Relational Model (SQL, dependencies, normalization)

* Query processing

* Crash recovery; Concurrency control.

Texts: t.b.a.

Suggested readings:

* H.F. Korth and A. Silberschatz, Database System Concepts, 2nd edition, McGraw-Hill, 1991.

* R. Elmasri and S. B. Navathe, Fundamentals of Database Systems, 2nd edition, Benjamin Cummings, 1994.

* C.J. Date, An Introduction to Database Systems,Vol. 1, 4th edition, Addison-Wesley, 1986.

Prerequisites: COSC3411.03

Course director: Section A T. Papadakis

Section M J. Xu

COSC 3418.03

Simulation of Continuous Systems

(not offered in FW94/95)

Simulation is a technique for dealing with problems that do not admit exact (or "analytic") solutions via mathematical analysis. A model of the system to be studied is constructed, and then the model is run to see how it performs, either to predict how the system will behave, or, if the behaviour of the system is known, to test the validity of the model of the system. A computer is a tool for supporting a large amount of activity in the running of the model.

A "continuous system" may either be presumed to be inherently continuous or it may, at a fine enough scale, be actually composed of discrete events. However, in simulation, a "continuous system" is one for which the model, due to practical necessity, is described by continuous variables regardless of its physical structure. However, the running of a continuous model involves, also of necessity, discrete steps. Thus central to continuous system simulation is the problem of approximation. (For simulation of discrete systems see COSC 3408.03)

Examples of continuous systems studied by simulation include dynamic systems involving very fine variations or large populations. Major sub-topics include chaotic behaviour, the numerical solution of differential equations by finite methods, and related issues of stability and errors.

Texts:: t.b.a.

Prerequisites: general prerequisites; MATH2560.03 or equivalent; MATH1310.03 or MATH1010.03 or MATH1011.03