DCS Grad Courses

The use of logic as an aid to programming. Refinement theorems: by steps, by parts, by cases. Timing: real time, recursive time. Formal semantics of programming languages. Recursive definition and the least fixed-point construction. Semantics of data types; data refinement. Imperative programs, functional programs, parallel processes, communicating processes.

This course examines the current state-of-the-art for research and practice in requirements engineering (RE), and prepares students for advanced research in this field. Topics covered include: requirements elicitation; modeling and analysis; specification techniques; validation and negotiation of requirements; evolution of requirements over time and across product families; multi-disciplinary basis of RE; research methods in RE.

Compiler organization, compiler writing tools, use of regular expressions, finite automata and context-free grammars, scanning and parsing, runtime organization, semantic analysis, implementing the runtime model, storage allocation, code generation.

Prerequisite: Courses in data structures and programming languages. Solid knowledge of Java.

Temporal logic model checking allows us to decide whether a property stated in a temporal logic holds in a model. With its emphasis on partial verification using fully automated techniques, model checking has become a practical tool for reasoning about hardware and software. This course is aimed to serve as an introduction to the state of the art model checking algorithms and technology. Topics include symbolic, automata-theoretic, bounded and game-theoretic approaches to model checking; query-checking; abstraction and refinement; techniques for model checking software. The course will also give students hands-on experience with current model-checking tools.

This course discusses software engineering issues relating to the management of the software development organization. Special emphasis is placed on planning releases through the use of stochastic models balancing capacity and requirement. Additional topics include advanced concepts of release management, estimation techniques, applying a metrics program, applying process enhancement initiatives, and managing programming people.

This course covers topics in programming languages.

Software Development Tools and Practices:
This course is an introduction to software consulting practices. Students will be paired with clients whose problems require advanced knowledge of computer science to solve, and will then work under the direction of the course instructor to develop and deliver useful results. Topics will include requirements elicitation, scope negotiations, deployment concerns, and disaster recovery.

This course will explore the role of empiricism in software engineering (SE) research, and will prepare students for advanced research in SE by examining how to plan, conduct and report on empirical investigations. The course will cover all of the principle methods applicable to SE: controlled experiment, case studies, surveys, archival analysis, action research and ethnographies, and will relate these methods to relevant metatheories in the philosophy and sociology of science. The course will critically review published examples of work that used each of the principle methods, both from within SE and from other disciplines. The course will cover techniques applicable to each of the steps of a research project, including formulating research questions, theory building, data analysis (using both qualitative and quantitative methods), building evidence, assessing validity, and publishing.

Prerequisite: At least one graduate level course in software engineering

This is an MSc/PhD level course on high-performance packet switching computer networks. The course introduces the theory and practice of designing packet switches, such as Internet routers, Ethernet switches, and ATM switches. It consists of two parts which will be presented in an interleaved fashion. The first part will develop basic tools from queueing theory, stochastic analysis, and algorithms. The second part of the course will focus on packet switch architecutres: the evolution of switches and routers, and practical issues in this area.

Prerequisites: Basic undergraduate courses in algorithms, networking, and in probability theory are strongly recommended.

Course web site: http://www.cs.toronto.edu/~yganjali/courses/csc2203/

Principles of operating systems. The operating system as a control program and as a resource allocator. The concept of a process will be 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. Experimentation with a simple operating system using a concurrent programming language.

The emphasis of the course is on models for systems with uncertainty. We study the properties of various models and discuss how they can be applied to analyze system performance. Concepts covered include Poisson, renewal, and Markov processes. Case studies involve computer networks, computer systems, and examples from machine learning.

Prerequisite: Solid knowledge of basic probability theory.

The emphasis of this course is on concepts and issues underlying the design and implementation of the Internet. Issues discussed include: naming, routing, Internet topology, congestion control, mobility, applications, and network security.

Prerequisite: CSC458 or equivalent.

We study a number of fundamental problems that arise in distributed systems, such as mutual exclusion, consensus, reliable broadcast and multicast, and the management of replicated data.

Prerequisite: An undergraduate course in algorithms.

Recommended Preparation: An undergraduate course in operating systems or networks.

Seminar and discussion of a number of topics in operating system design and implementation, based on a collection of papers as class reading. Emphasis on multiprocessor and distributed operating systems. Case studies of contemporary operating systems. An independent course project and an oral student presentation required.

Recommended Preparation: CSC2204 (Operating Systems) or equivalent.

Broad overview of the issues involved in developing mobile and pervasive applications. Some topics to be covered include: wireless technologies, disconnected operation, power and bandwidth adaptation, location awareness and tracking, resource discovery, Mobile-IP, and ad-hoc routing. A research oriented group project and an oral presentation are required.

Recommended Preparation: Familiarity with operating systems and computer networks (CSC2204H and CSC2209H or equivalents).

The problem of sharing a broadcast communications channel among a set of intelligent stations under distributed control is examined. Multiple access protocols for satellite packet switching, ground radio packet switching, and local networks are described. Both the performance evaluation of protocols (i.e. throughput - delay tradeoffs and stability conditions) and asymptotic limits to performance as the number of stations grows very large are emphasized. The integration of performance models of distributed systems and the underlying local area network will be considered.

Prerequisite: CSC2209 (458) (Computer Networks) or equivalent, a previous course on probability.

Recommended Preparation: CSC2206 (Computer System Modelling) or equivalent.

A special topics graduate course covering modern Internet-scale systems, including topics such as peer-to-peer systems, clusters, web systems, content delivery networks, and Internet security.

Prerequisite: CSC458 and CSC469 or equivalent.

Issues involved in the numerical solution of initial value problems in ODEs. Error propogation and the design of robust numerical methods. Methods designed for stiff and non-stiff problems will be reviewed and the significant difficulties arising in each area identified. State-of-the-art software will be surveyed and critically evaluated. Difficulties associated with implicit equations, algebraic constraints, discontinuities and delay terms will also be considered.

Recommended References: (1) E. Hairer, S.P.N. Norsett & G. Wanner, Solving Ordinary Differential Equations I, Springer-Verlag, Berlin, 1987. (2) E. Hairer & G. Wanner, Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems, Springer-Verlag, Berlin, 1991. (3) L.F. Shampine, Numerical Solution of Ordinary Differential Equations, Chapman and Hall, New York, 1994.

Possible topics include: optimization along a line; steepest descent methods; Newton's method; quasi-Newton methods; conjugate gradient methods; variants of Newton's method for nonlinear least squares problems; projection methods for optimization subject to linear constraints; Lagrangian methods for optimization subject to nonlinear equality constraints; penalty function methods for optimization subject to nonlinear inequality constraints.

Recommended Preparation: The student should be familiar with Calculus for functions of several variables, linear algebra and numerical methods for linear and non-linear algebra (covered at a level similar to that in CSC350 and 351).

Computationally-intensive applications in science and engineering are implemented on the latest computers available, today composed of many processors operating in parallel. Parallel computer architectures; implementation of numerical algorithms on parallel architectures. Topics from: performance evaluation; scientific visualization; numerical methods; applications from science and engineering. Emphasis in numerical linear algebra and partial differential equations. For students in computer science, applied mathematics, science, engineering.

Prerequisite: a numerical analysis course (covering CSC350 and CSC351). Proficiency in a conventional programming language. A course on algorithm design and analysis.

Recommended References: (1) James M. Ortega, Introduction to Parallel and Vector Solution of Linear Systems, Plenum Press 1988. (2) Jianping Zhu, Solving Partial Differential Equations on Parallel Computers, World Scientific, 1994. (3) Ian Foster, Designing and Building Parallel Programs, Addison Wesley 1995. (4) Y. Saad, Iterative Methods for Sparse Linear Systems, PWS, 1996. (5) Vipin Kuman et al, Introduction to Parallel Computing, Benjamin/Cummings Publ. Co. 1994.

Exclusion: CSC2326H taken in 1989, 1991, or 1992.

Development and certification of numerical software. The analysis of error, stability, reliability, efficiency, robustness, portability and correctness of programs for numerical computations. Language facilities. Text: Webb Miller, The Engineering of Numerical Software, Prentice-Hall, 1984.

Prerequisite: a numerical analysis course (preferably covering CSC 350 and CSC 351). Proficiency in a conventional programming language.

Recommended References: Any introductory Numerical Analysis or Numerical Software Book, e.g., (1) Forsythe, Malcolm and Moler, Computer Methods for Mathematical Computations. (2) Kahaner, Moler, Nash, Numerical Methods and Software. (3) Johnson and Riess, Numerical Analysis. (4) Isaacson and Keller, Analysis of Numerical Methods. (5) Stoer and Bulirsch, Introduction to Numerical Analysis. (6) Health, Scientific Computing: An Introductory Survey.

Finite Difference and Finite Element methods for boundary value problems including 2-point boundary value problems and 2-dimensional problems. Convergence of methods. Efficiency of the solution of linear systems. Finite difference methods for initial value problems. Consistency, stability and convergence. Method of lines. Special topics of interest among domain decomposition, multigrid, FFT solvers.

Prerequisite: Calculus, Numerical Linear Algebra, Interpolation, proficiency in programming.

Recommended References: (1) Numerical Methods for Differential Equations, M.A. Celia, W.G. Gray, Prentice Hall, 1992. (2) Numerical Methods for Partial Differential Equations, Ames, W. F. , Academic Press, 1992 3rd edition. (3) Finite Elements (Vol I), E.B. Baecker, G.F. Carey and J.T. Oden, Prentice Hall, 1981. (4) Splines and Variational Methods, P.M. Prenter, Wiley & Sons, 1975. (5) A First Course in the Numerical Analysis of Partial Differential Equations, A. Iserles, Cambridge Univ. Pr, 1996.

The efficient solution of large sparse systems, arising from the discretisation of PDE problems, approximation problems or other science and engineering problems. Recent developments in the area of Numerical Linear Algebra, including the basic iterative solvers, acceleration techniques, such as semi-iteration and conjugate gradient, and applications to PDEs such as Schwarz splitting methods, domain decomposition methods, multigrid schemes and FFT methods.

Prerequisite: Calculus, Numerical Linear Algebra, Interpolation, some knowledge of PDEs, proficiency in a programming language, preferably MAT LAB or FORTRAN.

Recommended References: (1) Y. Saad, Iterative methods for Sparse Linear Systems, PWS, 1996. (2) L.A. Hageman and D.M. Young, Applied Iterative Methods, Academic Press, 1981. (3) D.M. Young, Iterative Solution of Large Linear Systems, Academic Press, 1971. (4) R.S. Varga, Matrix Iterative Analysis, Prentice Hall, 1962. (5) W. Hackbusch, Iterative Solution of Large Sparse Systems of Equations, Springer Verlag, 1994. (6) J.M. Ortega, Introduction to Parallel & Vector Solution of Linear Systems, Plenum Press, 1988.

The topics include a review of initial value methods, shooting methods, collocation and finite difference methods. A presentation of one or more particular areas of difficulty, such as singular perturbation problems, bifurcation problems, or parameter fitting, will be included. Issues of software implementation will be discussed.

This course covers topics in numerical analysis.

The first and main part of the course will be an introduction to complexity theory, discussing models of computation, time and space classes, reductions, randomization, complexity hierarchies, tradeoffs. The second part will contain some recent results pertaining to fundamental issues in complexity theory.

Computable functions, Church's thesis, unsolvable problems, recursively enumerable sets. Predicate calculus, including the completeness, compactness and Lowenheim-Skolem theorems. Formal theories and the fundamental results of Gödel, Church and Tarski.

Possible Preparatory Reading: H.B. Enderton: A Mathematical Introduction to Logic.

The study of regular, deterministic, context free, context sensitive and recursively enumerable languages via generative grammars and corresponding automata (finite state machines, pushdown machines and Turing machines). Topics include complexity bounds for recognition, language decision problems and operations on languages.

Prerequisite: Some knowledge of computability theory is recommended.

Possible Preparatory Reading: (1) Chapters 7 and 8 of Hopcroft and Ullman. (2) Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company.

The goal of creating programs or computers that learn from experience is one of the most intriguing problems in computer science. It is of practical value, since we want programs that will adapt to change, that can adapt to the needs of their users, and that can find useful information in extremely large amounts of data. It is also closely connected to understanding human perception, since humans are the ideal model of how we would like many of these types of programs to act. In this course, we will study mathematical frameworks and foundations of machine learning. These mathematical models should capture key aspects of machine learning systems. A good framework will allow us to study problems and algorithms, allowing us to analyze the algorithms with respect to different measures, such as runtime efficiency, and accuracy. We will analyze how hard it is to learn various problems and will mathematically analyze general issues such as Occam's Razor. Most of the course will focus on the problem of concept learning. Given data (for example, pictures of hippos and other zoo animals), we want to be able to learn from this data to classify future examples (new unlabelled pictures) well. This seems like a restricted form of learning, but it turns out that most methods for other kinds of learning end up solving this sort of problem at their core.

Relational databases are finite relational structures, and most commonly used query languages are logics over such structures. Well known complexity classes can be defined by logical means over finite graphs. Regular and star-free languages can be defined by logical means over finite strings. What is common to these examples is the study of expressiveness of logics over finite structures, known as finite model theory. The course introduces basic techniques of finite model theory (games, locality, 0-1 laws) and their applications in database query languages (relational calculus, datalog), complexity theory (logical descriptions of classes such as P, NP, PH), and language theory.

Rigorous definitions of security for pseudo-random generators, digital signature schemes, secure hash families, and public-key encryption.. Methods (including number-theoretic conjectures) for constructing these secure cryptographic primitives. Methods for using secure primitives to achieve secure session-key exchange and secure sessions.

Connections between logic and automata, in particular between monadic second order logic and various finite state machines, date back to the late 1950s. They helped prove major results about automata and also led to some of the most powerful techniques for proving decidability. More recently, they found applications in a variety of areas, most notably formal methods (automata-based systems such as SPIN have been extremely successful) and databases, where they guide the design of many XML features. The course covers the basics of the logic/automata connections, and looks into several CS applications.

Prerequisite: Knowledge of logic and theory of computation.

We will study notions of complexity, which were pioneered in theoretical computer science, as applied to traditional topics in theoretical and applied mathematics, such as Hilbert's Nullstellensatz, Newton's method, linear programming, Julia sets and Mandelbrot sets.

Triple systems have their origins in algebraic geometry, statistics, and recreational mathematics. Although they are the simplest of combinatorial designs, the study of them encompasses most of the combinatorial, algebraic, and algorithmic techniques of combinatorial design theory. Topics to be covered: Fundamentals of design, existence of triple systems; enumeration; computational methods; isomorphism and invariants; configuration theory; chromatic invariants; resolvability; directed, Mendelsohn, and mixed triple systems.

This course covers many of the most important aspects of graph theory, including the development and analysis of algorithms for problems which arise in applications of graph theory.

Topics include minimum spanning tree, shortest path problems, network flow with applications to bipartite matching, general matching, alanarity testing, graph colorability, etc. Attention will be given to the mathematical theory that supports the algorithms presented. Depending on the year and instructor, a treatment of topics such as perfect graphs, randomized algorithms, average case analysis or algorithms, the class of #P and algorithms for enumeration problems, and algorithms designed for a parallel computer may be covered.

This course will deal with the problem of optimizing linear functions in linear or other convex domains, and application to the theory of algorithms, mainly the approximation of NP-hard problems. We will first investigate the algebraic and geometric foundations of linear programming (LP), and then turn to study the algorithmic approaches. We will present the famous and commonly used Simplex-Method, and the first polynomial algorithm for the problem-the Ellipsoid algorithm. Another, less algorithmic path we will take is studying the concept of Duality and the Duality-theorem in LP. This is possibly the most fundamental theorem in the theory of optimization, and provides an extremely efficient tool for many optimization problems.

We will discuss few of the applications of the theorem, such as Von Neumann minmax principle in game-theory, Yao's minmax principle and the "Primal-Dual" algorithmic paradigm. We will then discuss positive-semi-definite programming and how it can be solved using the Ellipsoid algorithm. The last part of the course will deal with methods of approximating NP-hard problems using the convex optimization tools we established in the earlier parts.

Algebraic theory that underlies symbolic and algebraic manipulation by computer. Chinese Remainder and interpolation theory, fast algorithms for computations with integers, polynomials and power series. Newton and Hensel iteration, polynomial and integer gcd algorithms, factorization of polynomials, the fast Fourier transform, solving systems of polynomial equations, Gröbner bases. The Maple computer algebra system.

Recommended: At least one undergraduate algebra course.

Required Reading: K.O. Geddes, S.R. Czapor and G.Labahn, Algorithms for Computer Algebra, Kluwer,1992.

Advanced topics in combinatorial theory chosen from a variety of areas, including enumeration, combinatorial identities, generating functions, graphs, and difference nets.

The topics discussed in this course vary from year to year.

This graduate course will cover some exciting algorithms that have been developed to analyze genomic and functional data, including Genome comparison and assembly, gene prediction, localization of regulatory elements in the genome, and analysis and comparison of biological networks. While the emphasis of the class will be on discrete algorithms, we occasionally will talk about probabilistic models (such as HMMs), and the interplay between discrete and probabilistic models. The course is intended for computer science graduate students, and all of the required biology will be explained in the class. Students in biological and related sciences with a strong computational background are encouraged to participate.

Grading: The basic requirements for the class will be a course project (40% of the grade), three homework assignments (45% total), and reading/class participation (15%).

Expected Background: Students should be familiar with algorithms (at least CSC 373 level), basic probability theory.

This course will emphasize combinatorial and probabilistic techniques in complexity theory. The specific topics change over time during the First-session; the focus was optimal and approximate scheduling algorithms.

The probabilistic method is one of the most important proof techniques in combinatorics. Generally speaking, it involves novel applications of probability theory to prove theorems which, on the surface, do not appear to have anything to do with probability.  This method was pioneered by Erdos in the 1940's when he proved the existence of graphs with certain properties by showing that a randomly constructed graph would have those properties with positive probability.

This course will provide an introduction to the basic tools of the probabilistic method, including: the first moment method, the second moment method, the Lovasz Local Lemma, concentration bounds and the semi-random method, along with algorithmic aspects of these tools. We will also present some of the more important applications of the technique.

Prerequisite:
A basic background in graph theory, such as that provided by CSC 2410.

This seminar based course will begin (first two weeks) with an introduction to three open problems in computational biology followed by a few background lectures on relevant biology. We will then transition to tackling two or three of the presented problems as a group. We will read appropriate grounding literature on all three projects and then explore solutions through the proposal of ideas from various computational subdisciplines. Students in the class are encouraged to consider how their research areas can be used in tackling these problems. The topics this year include: choice of synonymous 'words' in gene coding, geometric feature identification in protein structure, and computer aided drug discovery. These problems are most likely to manifest as challenges in machine learning, machine vision, computational geometry, statistics, and of course computational biology. Although a formal background in biology is not required, students with a more recent exposure to biology or computational biology (i.e. CSC2417/CSC2418) will have an easier time grasping key biological relevance. Contact instructor if you're unsure.

Convex optimization is a form of non-linear optimization that includes linear programming and least squares as special cases. Like linear programming and least squares, convex optimization has a fairly complete theory, very efficient algorithms, and a wide range of applications. Application areas include computer science, engineering, statistics, finance, economics and operations research.

This course is an introduction to the theory, algorithms and applications of convex optimization. The goal is to give students a working knowledge of the subject, i.e., the ability to recognize, formulate, and solve convex optimization problems. Topics covered will be selected from the following: convex sets and functions, linear and quadratic optimization, geometric and semidefinite programming, strong and weak duality, algorithms for constrained and unconstrained problems, interior point methods, and applications.

Prerequisites: Good knowledge of linear algebra and vector calculus, and a willingness to program in Matlab. Prior exposure to linear programming and basic probability would be helpful, but is not necessary. Mathematical maturity will be assumed.

Text: Boyd and Vandenberghe, Convex Optimization. Freely available on the Web.

Lectures: T4-5:30 in BA1210, and F2-3:30 in BA1240. Note: Most lectures will be only 1 hour in length; however, we will sometimes need an extra half hour.

Course web site: http://www.cs.toronto.edu/~bonner/courses/2008f/csc2600/

The goal of creating programs or computers that learn from experience is one of the most intriguing problems in computer science. It is of practical value, since we want programs that will adapt to change, that can adapt to the needs of their users, and that can find useful information in extremely large amounts of data. It is also closely connected to understanding human perception, since humans are the ideal model of how we would like many of these types of programs to act. In this course, we will study mathematical frameworks and foundations of machine learning. These mathematical models should capture key aspects of machine learning systems. A good framework will allow us to study problems and algorithms, allowing us to analyze the algorithms with respect to different measures, such as runtime efficiency, and accuracy. We will analyze how hard it is to learn various problems and will mathematically analyze general issues such as Occam's Razor. Most of the course will focus on the problem of concept learning. Given data (for example, pictures of hippos and other zoo animals), we want to be able to learn from this data to classify future examples (new unlabelled pictures) well. This seems like a restricted form of learning, but it turns out that most methods for other kinds of learning end up solving this sort of problem at their core.

Computational linguistics and the understanding of language by computer. Possible topics include: augmented context-free grammars; chart parsing, statistical parsing; semantics and semantic interpretation; ambiguity resolution techniques; discourse structure and reference resolution. Emphasis on statistical learning methods for lexical, syntactic and semantic knowledge.

Prerequisite: Familiarity with basic probability theory; Proficiency in C++, Java, or Python.

Possible Preparatory Reading: Jurafsky, Daniel and Martin, James H., Speech and Language Processing, 2nd edition, Pearson, 2008.

Representing knowledge symbolically in a form suitable for automated reasoning, and associated reasoning methods: first-order logic, entailment, the resolution method, Horn clauses, procedural representations, production systems, object-oriented systems, description logics, inheritance networks, defaults and probabilities, abductive explanation, the representation of action, planning. Emphasis on how reasoning can be kept tractable.

Prerequisite: A course in AI, a course in mathematical logic, and working knowledge of LISP/SCHEME and PROLOG.

Introduction to vision, visual processes, and image understanding. Scene lighting and reflectance models. Camera system geometry and image acquisition. The robust estimation of edges, lines, and regions. Perceptual organization. View-based image models. Image matching and feature-based correspondence. Estimation of motion and visual tracking. Multi-view geometry. Projective and metric reconstructions. Object recognition.

Introduction to probability as a means of representing and reasoning with uncertain knowledge. Qualitative and quantitative specification of probability distributions using probabilistic graphical models such as factor analysis, hidden Markov models, logistic regression. Algorithms for inference and probabilistic reasoning with graphical models including belief propagation and junction trees. Statistical approaches and algorithms for learning probability models from empirical data, including the EM algorithm and iterative scaling. Examples will be given of applications of these models in various areas of artificial intelligence and machine learning.

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. Python software.

This will be a course on algorithms and techniques for solving constraint satisfaction problems (CSPs). We start with an introduction to the formalism, and an examination of the range of problems that can be encoded as CSPs. Then we will examine systematic algorithms for solving CSPs. These algorithms are all built around backtracking, an algorithm that has been around for at least 100 years. We will examine a number of improvements to the generic backtracking algorithm, including the algorithms that are in use in various commercial systems. The famous Davis-Putnam algorithm is another instance of a backtracking algorithm, and we will examine it and some of the techniques used in the best performing DP implementations. Finally, we will look at the problem of finding all solutions and how it relates to Bayesian Inference. The course will involve a mixture of the theoretical (some lower bounds, algorithms, data structures) and the practical (modeling, empirical evaluation of algorithms, implementations).

Basic methods for classification, regression, clustering, time series modeling, and novelty detection. These algorithms will include K-nearest neighbours, naïve Bayes, decision trees, support vector machines, logistic regression, generalized additive models, K-means, mixtures of Gaussians, hidden markov models, principal components analysis, factor analysis and independent components analysis. Methods of fitting models including stochastic gradient and conjugate gradient methods, the Expectation Maximization algorithm and Markov Chain Monte Carlo. The fundamental problem of overfitting and techniques for dealing with it such as capacity control and model averaging. All the basic algorithms will be implemented in Matlab, but prior knowledge of Matlab is not required.

An introduction to the principal mathematical models of sentence structure used in computational linguistics today. Topics include: string matching and similarity, string and tree transducers, extended context-free formalisms, tree-adjoining grammar, substructural logics, discourse representation calculi, typed feature structures, and topological models. Parsing, algorithmic complexity, algebraic properties, and formal equivalence will be discussed. A basic knowledge of logic, formal language theory and graph theory is required. Some familiarity with syntactic theory will be helpful, but is not required.

Prerequisite: Computational Linguistics (CSC2501) or permission of the instructor.

An introduction to working with speech in natural language processing systems. Topics include: articulatory and acoustic phonetics, prosody and information structure, introduction to digital signal processing of speech, automated speech recognition, text-to-speech synthesis, language models, dialogue modeling and dialogue systems.

CSC2511H/401H1 is recommended (but not required) as a prerequisite.

An introduction to the study of meaning, its formal representation, its derivation from natural language syntactic structures, and its combination through inference with knowledge about the world. Topics may include: introduction to philosophy of language, compositionality, categorial grammar, quantification and plurality, underspecification, lexical semantics, word-sense disambiguation, lexical choice and nuances of meaning, calculating semantic distance, semantic interpretation in natural language processing systems, and reasoning with the event calculus in natural language.

A computational lexicon is a highly structured repository of the rich syntactic and semantic knowledge about individual words in a natural language processing system. Two key issues will be the focus of this seminar course: the representation of lexical information, and its automatic acquisition.

Topics will include the organization of meaning and syntax in the lexicon; the interface between lexical semantics and its syntactic realization; the predicate argument structure of verbs; corpus-based approaches to automatic lexical acquisition and semantic/syntactic annotation of words; linking of statistical models to linguistic models of lexical properties; unsupervised learning of lexical relations; resolution of lexical ambiguities in natural language processing. Research papers will primarily focus on relevant research in computational linguistics, but we will also discuss work in linguistic and cognitive models of the human lexicon, and ways in which the engineering and cognitive approaches can inform each other.

This course explores issues in computer vision from the standpoint of three-dimensional object modeling and recognition. A variety of current object modeling schemes are contrasted, including object-centered vs. viewer-centered models, physical vs. geometrical models, deformable vs. rigid models, and geometrical vs. functional models. Recognition algorithms including constrained search, alignment, geometric hashing, and appearance-based recognition are presented and evaluated in the context of particular object recognition tasks. Given a recognition task, a set of criteria for the selection of a suitable object model and recognition algorithm are discussed, including feature robustness, indexing power, search complexity, reliance on pose determination, and model coverage. Current recognition algorithms will be evaluated with respect to these criteria.

Prerequisite: CSC484 or equivalent, and CSC2503.

Preparatory Reading: (1) Vision, Marr, W.H. Freeman, 1982. (2) Computer Vision Systems, ed. by Hanson and Riseman, Academic, 1978. (3) Fundamentals of Sensation and Perception, Levine and Shefner, Addison-Wesley, 1981.

A seminar-style course in which recent research papers in computational linguistics and natural language processing are read and discussed. Students take turns choosing the topics and the papers, presenting the material, and leading the discussions. Topics may include anything of current interest in computational linguistics.

Possible Preparatory Reading: Recent issues of Computational Linguistics, and recent proceedings of conferences of the Association for Computational Linguistics.

Prerequisite: CSC2501(485) or CSC2511 (401), or permission of instructor. Students with a background in interdisciplinary areas that intersect with computational linguistics are welcome.

This course takes a unified approach to computer graphics and computer vision. Vision (image analysis) and graphics (image synthesis) are studied formally as mutually converse problems. The course explores physics-based models and associated computational methods for tackling these problems. The emphasis will be on modeling and estimating the shapes and motions of rigid and deformable objects using mathematical physics, variational methods, and numerical simulation with finite-difference, finite-element, and multiscale algorithms. Graphics topics will include the modeling and animation of flexible objects in simulated physical worlds, force driven interaction, and constraint satisfaction methods. Vision topics will include regularization theory, visible-surface representations, active models, and multisensory fusion. Finally, the course will investigate some advanced applications in artificial life, including the modeling of humans and other autonomous agents in virtual worlds.

Prerequisite: CSC2503, 2504, or permission of instructor.

The course will focus on the theory and implementation of dynamical systems that the Cognitive Robotics Group has been developing over the last seven years. This includes a broad range of topics whose primary interest is to artificial intelligence, but that also impacts on other branches of computer science, including databases, programming languages, computer animation and simulation. There are also important connections with discrete event control theory. Topics include: the situation calculus, the frame problem, deductive planning, time and concurrency, reactive systems, cognitive robotics, GOLOG (a situation calculus-based programming language for describing complex behaviors). The course will cover a subset of the material in the text.

Prerequisite: A solid background in first order logic. A familiarity with programming in Prolog (or a willingness to learn on your own) is also necessary, since some assignments rely on this.

A seminar on the foundations of theoretical knowledge representation in AI. The emphasis will be on the compromises involved in providing a useful but tractable representation and reasoning service to a knowledge-based system. The topics may vary from year to year, but could include: formal models of knowledge and belief, systems of limited reasoning, languages of limited expressive power, defaults and exceptions, meta-level representation and reasoning.

Prerequisite: CSC2502 and CSC2404.

A seminar on sequential decision making under uncertainty, covering a number of models and computational methods for their solution. Topics will include: basics of probabilistic inference and decision theory, fully- and partially-observable Markov decision processes, reinforcement learning. The course may also cover some introductory topics in multiagent decision making (primarily game-theoretic models). An emphasis will be placed on AI-style representation (e.g., Bayesian networks) and computational (e.g., decomposition, function approximation) techniques.

This course will cover learning algorithms for networks of neuron-like processors. Topics will include: The backpropagation algorithm and some pattern recognition applications; ways to make backpropagation converge faster and generalize better; Mixtures of Experts; Autoencoder networks and their relationship to other dimensionality-reduction methods; The EM algorithm for learning simple directed belief nets; Gibbs sampling and variational methods for learning intractable directed belief nets. Variational Bayesian methods; Hopfield networks and Boltzmann machines; Contrastive Divergence learning for Energy-Based models; Fast, greedy algorithms for learning deep belief nets; Echo-state networks for modelling time series.

Prerequisite: Some knowledge of calculus and linear algebra.

This course will explore recent advances and emerging areas of computer vision. The course will involve a mix of lectures, assignments, seminars, and student presentations. In 2006/07 the course will focus on the detection, estimation, and recognition of human pose and motion in digital video. Topics covered will include pose detection and estimation, face detection and biometrics, motion estimation and visual tracking, multi-object trackling, event detection and activity recognition, and the analysis of scene dynamics.

Prerequisite: CSC2503.

An advanced graduate seminar covering a topic in computational linguistics. The material will draw on research readings, and the format will emphasize class discussion. See the course web site for information on the current topic.

Prerequisite: CSC2501 or 2511 or permission of the instructor.

This course will explore how Bayesian statistical methods can be applied to problems in machine learning. I will talk about the theory of Bayesian inference, methods for performing Bayesian computations, including Markov chain Monte Carlo and variational approximation, and ways of constructing Bayesian models, particularly models that are appropriate for the high dimensional problems that often arise in fields such as bioinformatics. Exercises in the course will deal both with theoretical issues and with practical aspects of applying software for Bayesian learning to real data.

Prerequisite: Some basic knowledge of probability will be assumed.

Topic: Automated Planning and Reasoning about Action

CSC2542 is a seminar course that will explore recent advances in knowledge representation and reasoning. The course will draw predominantly on research readings. The format of the course will be a mix of class lectures, seminars, and student paper presentations. A course project will make up a significant part of a student's course mark.

In Winter 2009, the topic being covered is "Automated Planning and Reasoning about Action". Automated planning is a branch of AI that concerns the generation of a set of actions, with temporal and other constraints on them, for execution by some agent or agents. Planning is an active area of research that is central to the development of intelligent agents and autonomous robots. Planning is one task within the broader research area of reasoning about action and change that also includes tasks such as diagnosis and narrative understanding.

 

This course introduces the basic concepts and algorithms of modern 3D computer graphics. Topics include colour representation, display devices, optics and imaging, representations of curves and surfaces, geometric transformations, clipping, visibility, local illumination, global illumination, sampling, and graphics hardware. Students will implement algorithms and generate images and animations.

Text: Course notes and Peter Shirley, Fundamentals of Computer Graphics.

Prerequisite: Proficiency in C/C++, and preferably C++. There are some concepts in class and in the homework that are easier to deal with in an object-oriented setting.

Geometric issues relevant to computer graphics are covered: algorithms for convex hulls, Voronoi diagrams, and arrangements, design and analysis tools such as duality and reductions, and useful constructions such as Plucker coordinates. Representations of curves and surfaces are covered, including implicit and parametric objects. Uniform, non-uniform, and rational polynomial representations and wavelets are introduced.

CSC428H/2514 is the department's second course in Human Computer Interaction. It builds on the department's first course in HCI, CSC318, and what students learned there about interface design through task analysis, usability testing and iterative design. While the focus in 318 was largely on the design process, this second course will focus more on the underlying models of human-computer interaction, rigorous evaluation, and research frontiers. Topics to be discusses include, but are not limited to: Models of HCI from the human and device perspectives; Evaluation methodologies; Experimental Design; Analysis techniques; State-of-the-art and future user interfaces; Research directions.

Recommended Preparation: A course each in Psychology & Statistics.

Prerequisite: CSC318.

Non-photorealistic rendering (NPR) is an area of computer graphics that focuses on enabling a wide variety of expressive styles for digital art. In photorealism, NPR is inspired by artistic styles such as painting, drawing, technical illustration and animated cartoons. NPR has appeared in movies and video games in the form of "toon shaders," as well as in architectural illustration and experimental animation.

The goal of this course is to study the state-of-the-art in NPR and to develop new insights as to how art and illustration can be modeled as computational processes. We will read both seminal and recent papers in NPR. We will also read a few sources from beyond the field, such as from art and neuroscience. Assignments will require implementing the fundamental tools of NPR (processing images and 3D surfaces) and a final project will explore other directions.

Prerequisites: CS grads or instructor permission; computer graphics; some enthusiasm for art, animation, comics, cartoons, etc.

This course will focus on advanced algorithms and architecture for image synthesis. Algorithms for higher level modeling primitives, shading models, antialiasing, and stochastic modeling will be studied. Designs for high performance display systems, particularly raster displays, will also be studied. Various high-performance raster systems will be used as case studies, and the course will include implementation projects on one or more of them.

Possible Preparatory Reading: Proceedings of recent SIGGRAPH Conferences.

The topics discussed in this course vary from year to year.

The primary focus of this course is on kinematic and dynamic techniques for character animation. Topics include physical modeling and simulation, motion planning, control and learning algorithms, locomotion, motion trajectory optimization, scripting languages, motion capture, and motion editing. Students will implement algorithms and interactive animation tools and then use these to produce motion for animations.

This course presents a comprehensive overview of the important issues, research results, literature, and open questions on the subjects of computer-supported cooperative work (CSCW) and the design of effective groupware. CSCW is coordinated activity such as problem solving or communication that is carried out by a group of collaborating individuals and that is aided by computer technology. The multi-user software supporting CSCW is sometimes known as groupware. Topics will include a historical perspective on CSCW; group exercises designed to elicit some of the key issues in group interaction and cooperative work; behavioural foundations from the psychology of groups, the sociology of organizations, and the study of media; case studies in cooperative work; technical foundations from video, telecommunications, networking technology, distributed systems, and windowing environments; research reviews of approaches to the design and implementation of asynchronous groupware, synchronous groupware, electronic meeting and decision rooms, and media spaces; observation and evaluation methods and results; and research issues and unsolved problems.

Prerequisite: CSC2514 or permission of instructor.

Exclusion: CSC2524 from 1989-1995.

This course serves as an introduction to topics in Hypermedia Research. The course will consider the structure, design, deployment, evaluation and role of Hypermedia in digital knowledge integration and delivery across heterogeneous environments. Topics will include major themes in Hypermedia: open hypermedia systems; adaptive and adaptable hypermedia; hypertext; collaborative hypermedia; mark up languages (SGML, XML), web-based hypermedia, protocols and standards; spatial hypertext; time in hypermedia, desktop visualization, digital libraries; evaluative and design issues for hypermedia systems; collaborative hypermedia; hypermedia as media.

We will also consider Hypermedia's intersections with other technologies, such as databases, GUI design, machine learning, information retrieval, and computational linguistics, as well as effects on evolving social infrastructures, such as virtual organizations and digital copyright.

While interdisciplinary in approach, this course presumes a background in computer science, course work in human factors in engineering, software design, human-computer interaction are assets.

Students from graduate studies in other disciplines with related qualifications may apply for permission from the instructor.

Knowledge media are systems incorporating computer and communications technology that enhance human thinking, creativity, communication, collaboration, and learning. Examples include the Web, email, instant messaging, knowledge management systems, digital libraries, collaborative virtual environments, video conferencing environments, and webcasting systems.

This course reviews the emerging field of knowledge media design, and the use of digital media for communications, collaboration, and learning.

This course is intended to teach conceptual modeling notations and how to use them. The bulk of the course is dedicated to the introduction of modeling languages and their features. These include the Unified Modeling Language (UML), CLASSIC, and KAOS. UML is an object-oriented modeling language, for modeling all aspects of a software system. CLASSIC is a description-based knowledge representation language which supports a tractable form of inference. KAOS is a formal requirements modeling language for specifying goals, entities, relationships, actions and agents.

In addition to covering these in detail, the course reviews the history of conceptual modeling, early modeling languages (ER Model, SADT,...) and covers more advanced topics, such as ontologies, metamodeling, modeling intentions and social settings. The lecture part of the course ends with presentations of on-going research.

Introductory graduate level course on data management. The course builds on topics covered in undergraduate courses on database design (CSC443) and database internals (CSC343). The purpose of the course is to prepare students for research in data management by covering seminal papers on topics such as query optimization, query processing algorithms, buffer management and database performance. It also covers topics such as parallel database architectures, object relational databases, benchmarking and advanced indexing and searching. This course is a basic requirement for any graduate student with interests in data management. Undergraduate students with interest in this course should see the instructor.

Prerequisites: CSC343 and CSC443 or permission of the instructor.

The use, management and theory of databases, especially relational databases. Topics to be selected from the following: the relational model: relations, operations on relations, relational algebra and calculi; defining and manipulating data: SQL, embedded SQL, Query-by-Forms, database applications programming; query optimization: indices, algebraic optimization, hypergraph representation of queries, optimization algorithms; transaction management: concurrency, serializability, deadlocks, transaction protocols, time stamps, crash recover; design theory for relational databases: functional dependencies, normal forms, decomposition of relations; security and integrity of data; distributed databases.

Prerequisites: The course assumes familiarity with basic concepts of computer science, mathematics, and programming.