University of Toronto

A.J. Bonner, B.Sc., M.S., Ph.D.

G.S. Graham, B.Sc., M.Sc., M.A., Ph.D.

A.D. Jepson, B.Sc., Ph.D.

C. Rackoff, B.S., M.Sc., Ph.D.

J. Sills, B.A., B.Ed.

*Discipline Representative*:

Professor A.D. Jepson, Room 4041, (905) 828-3813

*Office Hours*: By appointment

*Faculty Advisor*:

Professor G.S. Graham, Room 4003, (905) 828-5341

*Office Hours*: By appointment

Computer Science is concerned in the broadest sense with the study of computers and of applications of computers. Its development was stimulated by the use of computers in many areas, such as Engineering, Physics, Chemistry, Biology, Statistics, and business. Yet Computer Science involves much more than just developing techniques for these application areas.

Computer Science as a discipline encompasses a wide range of research interests. Examples are: the design and implementation of computer programming languages, the design and organization of complex computer systems, the efficient allocation and use of computer resources under various constraints, and the organization and management of vast quantities of data typical in many business applications. Computer Graphics is the study of the application of computers to the analysis and generation of pictorial information. Theoretical interests in Computer Science include the study of computability - what can and cannot be computed by machines; of complexity - the relative effort required to perform various computations; and of verification - the formal proof of the correctness of programs. Artificial Intelligence research in Computer Science is concerned with using computers to simulate intelligent behaviour, with the development of programs that can process pictorial and linguistic data, prove theorems, solve problems, etc. Numerical Analysis is concerned with the design, testing and analysis of numerical methods for solving computational problems in science and engineering. Course offerings in Computer Science are intended to serve a wide variety of students, ranging from those whose primary interest is in information processing, to those interested in applying computers to other fields.

Enrolment is restricted in all CSC programs (except the Minor). Consult the Calendar Supplement and the Department for details of how to apply. CSC148H is the standard first year course for students who plan to continue with further courses in Computer Science in later years. Recommended preparation for this course is CSC108H or the equivalent.

Balloting is required for all second year Computer Science courses. Consult the Department for details. For more information on the Programs obtain a copy of the Computer Science Undergraduate Student Handbook from Room 4037.

**NOTE**: No late registration is permitted in any CSC course after the first two weeks of classes. Students may change from higher-level to lower-level introductory courses until the end of the fifth week of term.

__I have completed the following courses:__

**CSC148H Introduction to Computer Science**

Abstract data types and data structures for implementing them. Linked data structures. Encapsulation and information-hiding. Object-oriented programming in a language such as Java. Specifications. Analyzing the correctness and efficiency of algorithms and programs using mathematical reasoning. Recursion. Recurrence relations for analyzing the efficiency of recursive code. [26L, 13T]

*Exclusion*: CSC139H,149H,150H

*Prerequisite*: Two OAC courses in Mathematics

*Recommended preparation*: CSC108H

**CSC209H Software Tools and Systems Programming**

Software development techniques, typically the UNIX environment. Particular emphasis on what happens in the system when programs run. Core topics: software utilities (e.g., pipes, filters), shell programming, system calls, signals, file processing, introduction to concurrency (e.g., synchronization, mutual exclusion, race conditions, producer-consumer problem), processes. Additional topics may include: scripting languages, Internet programming languages, network programming (e.g., sockets). [26L, 13T]

*Prerequisite*: CSC148H, 270H

**CSC228H File Structures and Data Management**

An introduction to techniques for storing, accessing, and managing long-term data in computer systems. Hardware and software aspects of data processing: processors, storage devices, communications, file I/O control. Techniques for organizing and managing files: serial files, direct files, indexed files, multikey files, integrated files, file systems. Introduction to data base management systems with emphasis on relational data base systems. [26L, 13T]

*Prerequisite*: CSC148H, 270H

**CSC238H Discrete Mathematics for Computer Science**

A rigorous treatment of certain aspects of discrete mathematics with applications to computer science. Emphasis will be placed on the basic properties and fundamental algorithms concerning integers (including induction, Euclidean algorithm, modular arithmetic), and on logic (including propositional and predicate calculus and simple formal theories). Application of these ideas will be made to topics such as program correctness, formal program verification, algorithms from graph theory, and elementary set theory. [26L, 13T]

*Prerequisite*: CSC148H

*Recommended Preparation*: MAT102H

**CSC258H Computer Organization**

Computer structures, machine languages, instruction execution, addressing techniques and digital representation of data. Computer system organization, memory storage devices, micro-programming. Block diagram circuit realizations of memory, control and arithmetic functions. There will be three laboratory periods in which students will conduct experiments with digital logic circuits. [26L, 9P, 13T]

*Prerequisite*: CSC148H

**CSC270H Fundamental Data Structures and Techniques**

Standard programming methods, with an introduction to C and C++. Use of classes to represent abstract data types. Graph representation and graph algorithms. Simulation: data structures and progam organization for event-driven models. Representation of floating-point numbers; introduction to numerical methods. Optimization using dynamic programming. Throughout the course, programming assignments stress both the proper use of abstract data types (lists, stacks, etc.) and approaches to writing larger, more complex programs. [26L, 13T]

*Exclusion*: CSC158H,160H

*Prerequisite*: CSC148H

*Corequisite*: MAT112Y/132Y/138Y

**CSC324H Principles of Programming Languages**

Alternative paradigms for programming, illustrated by particular programming languages. Students already familiar with the procedural approach of languages such as Turing or C will learn about functional programming (illustrated by Lisp or Scheme) and logic programming (illustrated by Prolog). Additional topics in principles of programming languages. [26L, 13T]

*Prerequisite*: CSC238H

**CSC350H Numerical Algebra and Optimization**

Floating-point arithmetic. The efficiency and stability of solution techniques for systems of linear equations and least squares problems, including LU- and QR-based methods. Eigenvalue and eigenvector calculations. Algorithms for optimization problems, including linear programming, and for systems of nonlinear equations. [26L, 13T]

*Exclusion*: CSC336H(G),ACT323H(G)

*Prerequisite*: CSC270H; MAT138Y, 222H/248Y

**CSC354H Discrete-Event Simulation and Modelling**

Simulation and mathematical analysis of models of queueing systems. Concentration on dynamic, stochastic, discrete-event systems. Simulation topics: selecting input probability distributions, generating random numbers and random variates, output data analysis for one or more system configurations, variance reduction techniques. Analysis topics: queueing characteristics, transient and steady-state behaviour, performance measures, the M/M/1 queue in detail, some non-Markovian queues. [26L, 13T]

*Prerequisite*: CSC270H; STA242Y/262Y/ (STA107H and either STA250H or STA257H).

**CSC364H Computability and Complexity**

Measuring algorithm performance. Techniques of efficient algorithm design: divide and conquer, greedy method, dynamic programming, graph traversal, change of representation. Introduction to complexity theory: models of computation, P, NP, polynomial time reducibility, NP-completeness. Introduction to theory of computation: Church's thesis, computable and noncomputable functions, recursive and recursively enumerable sets, universality, many-one reducibility. [26L, 13T]

*Prerequisite*: CSC238H

**CSC378H Data Structures and Algorithm Analysis**

Abstract data types such as priority queues and dictionaries. Advanced data structures for main memory resident information, such as binomial heaps, leftist trees, self-adjusting lists and balanced search trees. Algorithm analysis: worst case, average case, and amortized complexity. Introduction to lower bounds. Emphasis is given to problem solving and a theoretical treatment of the data structures. [26L, 13T]

*Prerequisite*: CSC270H, 238H, STA107H/257H

**MAT102H Introduction to Mathematical Proofs **

Introduction to logical notation and its use in various types of mathematical proofs. Applications to: sets,
functions, bijections, equivalence relations, products, finite and infinite sets, cardinality. This course is designed
to introduce students to abstraction and rigour; it is strongly recommended for all first year students who are
interested in specializing in Mathematics. [26L, 13T]

Exclusion: This course may not be taken for degree credit by any student who has taken or is currently enrolled in

any third year Mathematics course.

**MAT138Y Calculus **

Derivatives, integrals, the fundamental theorem of calculus, improper integrals and limits, a brief introduction to
sequences and series. Differential and integral calculus of several variables: partial differentiation, chain rule,
extremal problems, Lagrange multipliers, classification of critical points. Multiple integrals, Green's theorem and
related topics. This course is faster paced than the MAT132Y/232H sequence. [78L, 26T, 4P]

Exclusion: MAT112Y/132Y/232H

Prerequisite: OAC Calculus, OAC Algebra and Geometry

**MAT248Y Linear Algebra and Linear Programming **

Vector spaces, basis and dimension, quotient spaces, abstract linear transformations, matrices and changes of
basis, dual spaces, determinants, linear equations, eigenvectors, inner product spaces, reduction of normal
matrices, quadratic forms. Linear programming. Applications. [52L, 26T, 4P]

Exclusion: MAT222H

Prerequisite: MAT102H,138Y/232H

**STA107H (I) Introduction to Probability and Modelling
** A theoretical introduction to probability with emphasis on the construction of discrete probability models for
applications. Topics covered include randomness and aspects of its representation, random variables, Venn
diagrams, discrete probability distributions, expectation and variance, independence, conditional probability, the
central limit theorem and applications to the analysis of algorithms and simulating systems such as queues. [26L,
13T]

Exclusion: STA242Y,262Y,257H,352Y(G),ECO227Y

Prerequisite: OAC Calculus/MAT112Y

**STA257H Probability and Statistics I
** A calculus-based development of probability models. Topics include probability measures, distribution functions,
probability and density functions, random variables, conditional probability, expectation, convergence in
distribution, the Weak and Strong Laws of Large Numbers, the Central Limit Theorem and some distribution
theory. [26L, 13T]

Exclusion: STA242Y,255H(G),262Y,352Y(G), ECO227Y

Prerequisite: MAT132Y/138Y

NOTE: MAT232H is strongly recommended.

**CSC494H1/495H1 Computer Science Project**

TBA

This half-course involves a significant project in any area of Computer Science. The
project may be undertaken individually or in small groups. The course is offered by
arrangement with a Computer Science faculty member.

*Prerequisite:* Three 300-level Computer Science half-courses, a CGPA of 3.00 (2.50
for students in a CSC program), and permission of the Undergraduate Coordinator

**CSC340H1 Information Systems Analysis and Design 26L, 13T**

Theory, tools and techniques of information systems analysis
and design. Topics include: theory of systems and organizations; structured analysis and
design; user interface design.

*Prerequisite:* CSC228H; CGPA 3.0

**CSC418H1 Computer Graphics 26L, 13T**

Identification and characterization of the objects
manipulated in computer graphics, the operations possible on these objects, efficient
algorithms to perform these operations, and interfaces to transform one type of object to
another. Display devices, display data structures and procedures, graphical input, object
modelling, transformations, illumination models, primary and secondary light effects;
graphics packages and systems. Students, individually or in teams, implement graphical
algorithms or entire graphics systems.

*Prerequisite:* CSC336H/350H/
351H/364H/
378H, proficiency
in C; MAT223H/240H;
CGPA 3.0

**CSC434H1 Data Management Systems 26L, 13T**

Concepts, approaches, and techniques in data base management
systems (DBMS): data and information management; logical models of data bases: relational,
network, and hierarchical DBMS's; operational requirements; implementation considerations;
DBMS architecture; data base design.

*Prerequisite:* CSC228H, 378H
; CGPA 3.0

*Recommended preparation:* Proficiency in C

**CSC468H1 Operating Systems 26L, 13T**

Principles of operating systems. The operating system as a
control program and as a resource allocator. The concept of a process is central:
synchronization, mutual exclusion, deadlock. Additional topics include memory management,
file systems, process scheduling, and protection. Some treatment of multiprocessor issues,
such as threads and scheduling. Case studies from systems such as Unix and Mach.

*Prerequisite:* CSC258H, 209H
/knowledge of concurrent programming; CGPA 3.0

**CSC384H1 Introduction to Artificial Intelligence**

(formerly CSC484H) 26L,
13T

A broad introduction to the sub-disciplines of AI. Core topics: search methods, game
playing and rule-based systems. Overview of: natural language understanding, knowledge
representation, reasoning, planning, vision, robotics, learning and neural networks.
Assignments provide practical experience, both theory and programming, of the core topics.
LISP or Prolog programming is required for at least one assignment.

*Exclusion:* CSC484H

*Prerequisite:* CSC324H; CGPA 3.0

**CSC401H1 Natural Language Computing 26L, 13T**

Introduction to techniques involving natural language and
speech in applications such as information retrieval, extraction, and filtering;
intelligent Web searching; spelling and grammar checking; speech recognition and
synthesis; and multi-lingual systems including machine translation. N-grams, POS-tagging,
semantic distance metrics, indexing, on-line lexicons and thesauri, markup languages,
collections of on-line documents, corpus analysis. PERL and other software.

*Prerequisite:* CSC209H/228H, STA107H/220H/250H/257H; CGPA 3.0

*Recommended preparation:* MAT223H/240H is strongly recommended

**CSC407H1 Software Architecture and Design 26L, 13T**

An introduction to the development of the system-level
architectures and class-level object-oriented designs for software systems. Special
emphasis on the study of architecture and design patterns: the core of solutions to
commonly occurring design problems. Representations of design/architecture (with emphasis
on the use of UML as a class-level design notation), architectural assessment, product
lines, architecture extraction, and re-factoring. There is no major project, but there is
a series of smaller design and architecture exercises requiring some programming. A
knowledge of UML as used for requirements analysis and a working knowledge of both the C++
and Java languages is assumed.

*Prerequisite:* CSC340H, 378H; CGPA 3.0

**CSC408H1 Software Engineering 26L, 13T**

The structure and unique characteristics of large software
systems. The software process and software project management including project planning,
risk management, staffing and organizational issues. Review of requirements analysis and
specification. Software development techniques, version control, configuration management,
system construction tools. Software system testing and quality assurance. Software
maintenance and product delivery strategies. A course project is used to illustrate
software engineering techniques.

*Prerequisite:* CSC340H, 378H; CGPA 3.0

*Recommended preparation:* Proficiency in C; some of CSC209H/300H/318H/407H

**CSC318H1 The Design of Interactive Computational Media
26L, 13T**

User-centred design of interactive systems; methodologies,
principles, and metaphors; task analysis. Interdisciplinary design; the role of graphic
design, industrial design, and the behavioural sciences. Interactive hardware and
software; concepts from computer graphics. Typography, layout, colour, sound, video,
gesture, and usability enhancements. Classes of interactive graphical media;

direct manipulation systems, extensible systems, rapid prototyping tools. Students work on
projects in interdisciplinary teams.

Enrolment limited, but non-computer scientists welcome.

*Prerequisite:* Any CSC half-course; CGPA 3.0

*Recommended preparation:* CSC300H provides useful
background for work in CSC318H, so if you plan to take CSC300H then you should do it before CSC318H