Graduate Calendar Archives: 2001 / 2002

Computer Science

The School

The School of Computer Science offers degrees leading to a Master of Computer Science or a Ph.D. in Computer Science through the Ottawa-Carleton Institute for Computer Science. The Institute is jointly administered by the School and the School of Information Technology and Engineering at the University of Ottawa. For further information, including admission and program requirements, see p.137.

A program leading to the M.Sc. in Information and Systems Science is offered in cooperation with the School of Mathematics and Statistics and the Department of Systems and Computer Engineering. For further information see p.209.

The research expertise of the School's faculty is concentrated in the following areas:

Algorithms and Complexity

Computational geometry and algebra, combinatorial optimization, distributed and parallel algorithms, multi-dimensional data structures, stochastic automata, graph theory, partial orders.

Intelligent Systems

Expert systems, knowledge acquisition tools, knowledge based assistants, connectionism and neural networks, natural language understanding, learning and adaptability, robotics, pattern recognition.

Object-Oriented Systems

Visual programming, filing systems, databases, user interfaces, simulation, animation, software engineering, office automation.

Distributed Systems

Operating systems, databases, systolic architectures, tools for performance studies, distributed programming languages, parallel computing, communication complexity, networks.

In addition to its undergraduate laboratories, the School maintains a number of state-of-the-art research laboratories all integrated via a department and campus area network.

Graduate Courses

Not all of the following courses are offered in a given year. For an up-to-date statement of course offerings for 2001-2002, please consult the Registration Instructions and Class Schedule booklet published in the summer.

F,W,S indicates term of offering. Courses offered in the fall and winter are followed by T. The number following the letter indicates the credit weight of the course: 1 denotes 0.5 credit, 2 denotes 1.0 credit.

The complete list of courses available through the Ottawa-Carleton Institute for Computer Science is given on p. 141. The following courses are offered by the School of Computer Science.

Computer Science 95.501F1 (CSI5113)

Foundations of Object-Oriented Programming Languages

Object-oriented programming, design, and implementation from first principles to advanced concepts. Possible topics include: need-driven designing, metaleval programming, visual programming, event-oriented programming, web-related applications, subtyping/subclassing/isa relationships, futures and proxies, distributed applications.

Prerequisite: Computer Science 95.307 or the equivalent.

Computer Science 95.503F1 (CSI5308)

Principles of Distributed Computing

Formal models; semantics of distributed computations; theoretical issues in design of distributed algorithms; computational complexity; reducibility and equivalence of distributed problems. Related topics: systolic systems and computations, oligarchical systems and control mechanisms.

Prerequisite: Computer Science 95.401 or equivalent.

Computer Science 95.505F1 (CSI5390)

Learning Systems for Random Environments

A course on computerized adaptive learning for random environments and its applications. Topics include a mathematical review, learning automata which are deterministic/stochastic, with fixed/variable structures, of continuous/discretized design, with ergodic/absorbing properties and of estimator families.

Prerequisite: Mathematics 70.260 or 70.350, or Engineering 94.553 or the equivalent.

Computer Science 95.506W1 (CSI5306)

Natural Language Understanding

Introduction to current research in natural language processing, with emphasis on semantics and pragmatics rather than syntactic issues, and on analyzing text rather than single sentences. Topics include: meaning representation, representation of pragmatic information, speech act theory, flexible parsing, anaphor and reference, contextual meaning.

Prerequisite: Computer Science 95.407 or 95.416 or the equivalent.

Computer Science 95.508F1 (CSI5164)

Computational Geometry

A study of the design and analysis of algorithms to solve geometric problems with an emphasis on applications such as robotics, graphics, and pattern recognition. Topics include: visibility problems, hidden line and surface removal, path planning amidst obstacles, convex hulls, polygon triangulation, point location.

Prerequisite: Computer Science 95.384 or the equivalent.

Computer Science 95.509F1 (CSI5141)

Associative Data Structures and Advanced Databases

Concepts and advanced topics in the design, implementation and analysis of physical storage schemes with emphasis on their application to specialized database and information retrieval systems. Topics include: associative searching techniques; multidimensional storage structures; algorithms for spatial data modeling; formulation and optimization of database queries.

Prerequisites: Computer Science 95.305 and 95.384, or the equivalent.

Computer Science 95.510W1 (CSI5180)

Topics in Artificial Intelligence

A programming-oriented introduction to selected topics in Artificial Intelligence (A.I.). Possible topics include: A.I. programming techniques, pattern matching systems, natural language systems, expert systems, rule-based systems, constraint systems, learning systems, cerebral computation, neural networks, computer vision, and cognitive systems.

Prerequisite: Computer Science 95.407 or 95.417 or the equivalent.

Computer Science 95.511F1 (CSI5311)

Distributed Databases and Transaction Processing Systems

Principles involved in the design and implementation of distributed databases and distributed transaction processing systems. Topics include: distributed computing concepts, computing networks, distributed and multi-database system architectures and models, atomicity, synchronization and distributed concurrency control algorithms, data replication, recovery techniques, and reliability in distributed databases.

Precludes additional credit for Computer Science 95.411.

Prerequisites: Computer Science 95.305, 95.401, and 95.403 or equivalent.

Computer Science 95.512W1 (CSI5312)

Distributed Operating Systems

Design issues of advanced multiprocessor distributed operating systems: multiprocessor system architectures; process and object models; synchronization and message passing primitives; memory architectures and management; distributed file systems; protection and security; distributed concurrency control; deadlock; recovery; remote tasking; dynamic reconfiguration; performance measurement, modeling, and system tuning.

Prerequisite: Computer Science 95.300 or the equivalent.

Computer Science 95.513W1 (CSI5313)

Computer Security and Cryptography

Introduction to information security in computer and communication systems. Classical and public-key cryptosystems are overviewed. Applications to information schemes and digital signatures, key distribution and key agreement, authentication and secret sharing are also discussed. Also offered at the undergraduate level, with different requirements, as Computer Science 95.413, for which additional credit is precluded.

Prerequisite: Computer Science 95.384 or equivalent.

Computer Science 95.514W1 (CSI5314)

Object-Oriented Systems

Advanced topics in current issues in object-oriented software development. Topics include the implementation of Object-Oriented languages, object-oriented software engineering models and methodologies, design patterns and issues relating to large scale development such as real-time performance, persistence, concurrency, and distributed objects.

Precludes additional credit for Computer Science 95.304 and 95.414.

Prerequisite: Computer Science 95.501 or the equivalent.

Computer Science 95.515W1 (CSI5132)

Parallel Processing Systems

Introduction to the issues involved in designing and using parallel processing systems. Topics include: taxonomy and applications of parallel systems; SIMD systems; multiprocessor systems; multicomputer systems; computation versus communication issues in parallel processing; scheduling parallel systems; spinning versus blocking; interconnection networks; hot-spot contention.

Prerequisite: Permission of the School.

Computer Science 95.516W1 (CSI5123)

Languages for Parallel Computing

Survey of major language paradigms for parallel computing: sequential imperative, parallel imperative, logic, functional(reduction and dataflow), object and message-passing based languages; communicating sequential processes; and massive data-level parallelism. Topics include: detection, determinism, data partitioning, task scheduling, task granularity, synchronization methods, resource management, and debugging.

Prerequisite: Computer Science 95.501

Computer Science 95.517W1 (CSI5185)

Statistical and Syntactic Pattern Recog-nition

Topics include a mathematical review, Bayes decision theory, maximum likelihood and Bayesian learning for parametric pattern recognition, non-parametric methods including nearest neighbor and linear discriminants. Syntactic recognition of strings, substrings, subsequences and tree structures. Applications include speech, shape and character recognition.

Prerequisites: Permission of the School.

Computer Science 95.523F1 (CSI5173)

Data Networks

Mathematical and practical aspects of design and analysis of communication networks. Topics include: basic concepts, layering, delay models, multiaccess communication, queuing theory, routing, fault-tolerance, as well as advanced topics on high-speed networks, ATM, mobile wireless networks, and optical networks.

Prerequisite: Computer Science 95.484 or permission of the School.

Computer Science 95.524W1 (CSI5124)

Computational Aspects of Geographic Information Systems

Computational perspective of geographic information systems (GIS). Data representations and their operations on raster and vector devices: e.g., quadtrees, grid files, digital elevation models, triangular irregular network models. Analysis and design of efficient algorithms for solving GIS problems: visibility queries, point location, facility location.

Prerequisite: Computer Science 95.384 or the equivalent.

Computer Science 95.526W1(CSI5183)

Genetic Algorithms and Artificial Life

Study of algorithms based upon biological theories of evolution, and their application to machine learning and optimization problems. Genetic Algorithms, Classifier Systems, Genetic Programming, and other approaches to evolutionary computation are covered in detail. Recent work in the field of Artificial Life is also studied.

Prerequisite: Computer Science 95.407 or 95.417 or the equivalent.

Computer Science 95.540W1 (CSI5310)

Software Patterns

This course surveys current developments in software patterns, three-part rules expressing relations between software contexts, problems and solutions. Pattern categories discussed include architectural, design, analysis, refactoring, general-purpose, anti-patterns, and idioms. Students are required to apply existing patterns and to develop and defend new ones.

Prerequisites: Computer Science 95.304 or equivalent

Computer Science 95.541 (CSI5389/5789)

Electronic Commerce Technologies

Basic e-commerce models. Internet infrastructure and tools. TCP/IP, web servers, search engines. Cryptography. Public key infrastructure. Key management and certificate authorities. Secure Socket Layer and secure electronic transactions. Content presentation: XML. Open trading protocol. Intelligent mobile agents. Auctions and negotiations. Case studies.

Prerequisites: Computer Science 95.205 and 95.414

Computer Science 95.542

Wireless Networks and Protocols

Focus is on the link and network layer protocols of wireless networks; applications of wireless networks may be discussed. Topics may include: protocol implementation, mobile IP, resource discovery, wireless LANs/PANs, and Spreadspectrum. Precludes additional credit for 94.536.

Prerequisite: Computer Science 95.323 or equivalent.

Computer Science 95.543

Real-Time System Development

An advanced course in real-time OO system development that deals with modeling systems at different abstraction levels. A systematic and traceable modeling process is introduced. Topics include: modeling notations (including UML-RT), development process, design patterns, and system testing. Expect a substantial design project. Precludes additional credit for 94.586.

Prerequisite: Computer Science 95.514 or equivalent

Computer Science 95.544

Computer-Aided Program Verification

Automatic verification techniques for concurrent, reactive, and real-time programs. Possible topics: temporal logics, the basic model-checking algorithm, symbolic model checking, compositional techniques, exploiting abstraction and symmetry, models based on partial orders, model-checking for the mu-calculus, applications to communication protocols, computer security and digital circuits.

Prerequisite: Computer Science 95.404 or equivalent.

Computer Science 95.573F1 (CSI5163)

Algorithm Analysis and Design

Topics of current interest in the analysis and design of sequential and parallel algorithms for non-numerical, algebraic and graph computations. Lower bounds on efficiency of algorithms. Complexity classes. Also offered at the undergraduate level, with different requirements, as Computer Science 95.484, for which additional credit is precluded.

Prerequisite: Permission of the School.

Computer Science 95.574W1 (CSI5131)

Parallel Algorithms and Their Implementation

Multiprocessor architectures from an application programmer's perspective: programming models, processor arrays and hypercube multiprocessors, algorithmic paradigms, efficient parallel problem solving, limits of parallelism, software scalability and portability. Student projects in selected application areas: image processing, robotics, graphics, animation, etc. Programming experience on parallel processing equipment.

Prerequisite: Computer Science 95.484 or the equivalent.

Computer Science 95.582W1

Introduction to Information and Systems Science

An introduction to the process of applying computers in problem solving. Emphasis is placed on the design and analysis of efficient computer algorithms for large, complex problems. Applications in a number of areas are presented: data manipulation, databases, computer networks, queuing systems, optimization. (Also listed as Mathematics 70.582, Engineering 94.582, Information and Systems Science 93.582)

Computer Science 70/95.587F1 (CSI5104)

Formal Language and Syntax Analysis

Computability, unsolvable and NP-hard problems. Formal languages, classes of languages, automata. Principles of compiler design, syntax analysis, parsing (top-down, bottom-up), ambiguity, operator precedence, automatic construction of efficient parsers, LR, LR(O), LR(k), SLR, LL(k); syntax directed translation.

Prerequisite: Computer Science 95.302, or Mathematics 70.485 or 70.565, or the equivalent.

Computer Science 95.590F1, W1, S1 (CSI5140)

Selected Topics in Computer Science

Selected topics, not covered by other graduate courses, will be offered. Details will be available at the time of registration from the school.

Computer Science 95.591F1, W1, S1 (CSI5901)

Directed Studies (M.C.S.)

A course of independent study under the supervision of a member of the School of Computer Science.

Computer Science 95.592F1, W1, S1 (CSI5900)

Graduate Project (M.C.S./M.Sc.(ISS))

Computer Science 95.593F2, W2, S2 (CSI6900)

Intensive Graduate Project (M.C.S.)

A one or two session course. For M.C.S. non-thesis option students only. Not to be combined for credit with 95.592.

Computer Science 95.595F, W, S(CSI7999)

M.C.S. Thesis

Computer Science 70/94/95.598F, W, S

M.Sc. Thesis in Information and Systems Science

Computer Science 95.610F1 (CSI7131)

Advanced Parallel and Systolic Algorithms

This course is a continuation of 95.574.

Prerequisite: Computer Science 95.574.

Computer Science 95.614F1 or W1(CSI7314)

Advanced Topics in Object-Oriented Systems

Advanced object-oriented software engineering, in particular the issues of reuse and testing. Sample topics include: interaction modeling; class and cluster testing; traceability; design patterns and testing; the C++ standard template library. Students will carry out research.

Prerequisite: Computer Science 95.514 or permission of instructor.

Computer Science 95.661F1, W1, S1 (CSI7160)

Advanced Topics in the Theory of Computing

Computer Science 95.662F1, W1, S1 (CSI7170)

Advanced Topics in Distributed Computing

Computer Science 95.663F1, W1, S1 (CSI7161)

Advanced Topics in Programming Systems and Languages

Computer Science 95.664F1, W1, S1 (CSI7162)

Advanced Topics in Computer Applications

Computer Science 95.665F1, W1, S1 (CSI7163)

Advanced Topics in Computer Systems

Computer Science 95.691F1, W1, S1 (CSI7901)

Directed Studies (Ph.D.)

Computer Science 95.692F1, W1, S1 (CSI7900)

Graduate Project (Ph.D.)

Computer Science 95.699F, W, S (CSI9999)

Ph.D. Thesis