General Prerequisites

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

* COSC1030.03 completed

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

* Specific prerequisites may also apply

Taking more than two 2000-level computer science courses per term is not permitted.

COSC 2001.03

Introduction to Theory of Computation

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

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

The course will introduce the different theoretical models of computers. Topics covered may include the following.

* Finite automata and regular expressions. Practical applications eg. text editors

* Pushdown automata and context-free grammars. Practical applications eg. parsing and compilers.

* Turing machines. Turing machines as a general model of computers. Introduction to the halting problem and NP completeness.

Texts: Cohen, Introduction to Computer Theory.

Prerequisites: general prerequisites.

Course director: Section A Z. Stachniak

Section M X. Deng

COSC 2011.03

Fundamentals of Data Structures

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

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

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

This course discusses the fundamental data structures commonly used in the design of algorithms. At the end of this course, you will know about the classical data structures, and master the skills in the use of abstraction, specification and program construction using modules. Furthermore, you will be able to apply them effectively in the design and implementation of algorithms.

C++ will be used as the implementation language. No prior knowledge of C or C++ is assumed. At the end of the course you will be able to programme in C++ and understand the fundamentals of the object-oriented paradigm. You may not be an expert in C++ as some advanced and complicated features may not be taught or used. However, it is expected that you will be able to quickly learn these concepts on your own.

Topics covered may include the following.

* Review of primitive data types and abstract data type - arrays, stacks, queues and lists - used as an introduction to C++.

* Searching and sorting: implementation in C++. A mixture of review and new algorithms.

* Priority queues.

* Trees: threaded, balanced (AVL-, 2-3-, and/or B-trees), tries

7 Graphs: representations; transitive closure; graph traversals; spanning trees; minimum path; flow problems

Texts: t.b.a.

Prerequisites: general prerequisites.

Course director: Section A J. Liu

Section B t.b.a.

Section M J. Liu

COSC 2021.03

Computer Organization

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

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

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

Computers can be usefully viewed as having a structure organized into several levels, ranging from high-level programming languages such as Pascal or C to digital logic circuits. Each level provides specific resources for the programmer which are created by the structure at the next lower level. This course intends to provide students basic understanding of computers at the lowest levels of this structure. The ways in which data are represented in memory and transformed by machine instructions are explored.

The major functional blocks of a computer including main memory, control unit, ALU, input/output bus structures, interrupt system, DMA channels, and peripheral devices are studied. Some assembler programming and microprogramming will be required.

Texts: Patterson & Hennessy, Computer Organization & Design: The Hardware / Software Interface, Morgan Kaufmann, 1994.

Suggested Reading:

* Tanenbaum, A.S., Structured Computer Organization, 3rd ed., Prentice-Hall, 1990.

* Stallings, Wm., Computer Organization and Architecture, 2nd ed., Macmillan, 1990.

Prerequisites: general prerequisites.

Course director: t.b.a.

COSC 2031.03

C, UNIX and X Window System

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

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

1 The programming language C will be taught as a second programming language. The course assumes some programming experience - typically that obtained in the first-year computer science course. The emphasis will be on practical exploration of a particular strength of C, rather than its use as a general-purpose language. C is a tool-making tool for working at a low-level; it is a programming language designed for, and used in, the writing of utilities that access the primitives of the underlying machine architecture and the operating system. Unix components and the X Window System are written in C.

2 The Unix programming environment will be considered at both

a the command level (man 1): shells, utilities, filters, etc., and

b the system call (man 2) and standard library (man 3) levels.

The focus in [2b] is on some Unix operating system user-interface primitives, e.g. fork/exec, file descriptors, read/write, etc. The emphasis here, as in [1], is on practical exploration.

3 The X Window System will be presented practically, and at the level of the Xlib C-language library interface. The emphasis here also will be on practical exploration, but now with visual graphic feedback. There will also be some theoretical consideration of the protocol and server-client network-transparent architecture, and the X prime directive: "mechanism, not policy".

Students should note that this course has a substantial self-disciplined laboratory component.


* Kernighan and Ritchie, The C Programming Language.

* Kernighan and Pike, The Unix Programming Environment.

* Jones, Introduction to the X Window System.

Prerequisites: general prerequisites.

Course director: Section A A. Wallis

Section M A. Wallis