Calendar 2009/10
Course Descriptions
This chapter provides an archive of courses offered by UBC. For current course sections and schedules, please visit the online Course Schedule.
Computer Science, Faculty of Science
CPSC: Computer Science
Students with no previous exposure to computers may consider a more general introduction to computers and computer science provided by CPSC 101. Students who have credit for, or are currently registered in either of CPSC 110 or CPSC 111 or have Computer Science credit from another institution, may not take CPSC 100 or CPSC 101 or APSC 160 for credit in Science Programs. Students with sufficient background in the concepts presented in CPSC 111 and an advisor's approval are encouraged to challenge the CPSC 111 course for credit by taking an examination. Enrolment restrictions apply to certain CPSC courses. In order to register into CPSC 210, 211, 213, 221, 310, 313, and 320, students should have an overall average greater than or equal to a threshold set by the Department of Computer Science. Students who are currently in a CPSC program but are prevented from registering in any of these courses may not be able to continue in a CPSC program. Those students should consider transferring to another program. Additional fees are charged for some courses. For more information students are advised to contact the Department of Computer Science or visit the Computer Science undergraduate program website: (http://www.cs.ubc.ca/ugrad/program/index.html). For information on credit exclusion between CPSC and other courses, please consult the Faculty of Science Credit Exclusion List.
- CPSC 101 (4) Connecting with Computer Science
- Fundamentals of computer science and their connections with the arts, psychology, and biology. Historical, cultural, and gender perspectives of important contributions to the field will be discussed. No prior computing background required. [3-3-0]
Equivalency: WMST 201.
- CPSC 110 (4) Computation, Programs, and Programming
- Fundamental program and computation structures. Introductory programming skills. Computation as a tool for information processing, simulation and modeling, and interacting with the world. [3-3-0]
Prerequisite: Principles of Mathematics 12.
- CPSC 111 (4) Introduction to Computation
- Basic programming constructs, data types, classes, interfaces, protocols and the design of programs as interacting software components. [3-2-1]
Prerequisite: Principles of Mathematics 12
- CPSC 121 (4) Models of Computation
- Physical and mathematical structures of computation. Boolean algebra and combinations logic circuits; proof techniques; functions and sequential circuits; sets and relations; finite state machines; sequential instruction execution. [3-2-1]
Prerequisite: Principles of Mathematics 12.
Corequisite: One of CPSC 110, CPSC 111.
- CPSC 210 (4) Software Construction
- Design, development, and analysis of robust software components. Topics such as software design, computational models, data structures, debugging, and testing. [3-2-0]
Prerequisite: One of CPSC 110, CPSC 260.
- CPSC 211 (4) Introduction to Software Development
- Software design and the development of robust abstractions; design practices, data abstractions, inheritance, testing, concurrency and distributed computing. [3-2-0]
Prerequisite: One of CPSC 111, CPSC 260.
- CPSC 213 (4) Introduction to Computer Systems
- Software architecture, operating systems, and I/O architectures. Relationships between application software, operating systems, and computing hardware; critical sections, deadlock avoidance, and performance; principles and operation of disks and networks. [3-3-0]
Prerequisite: Either (a) all of CPSC 121, CPSC 211 or (b) all of CPSC 260, EECE 256, CPSC 211. CPSC 211 may be taken concurrently with case (b) only.
- CPSC 221 (4) Basic Algorithms and Data Structures
- Design and analysis of basic algorithms and data structures; algorithm analysis methods, searching and sorting algorithms, basic data structures, graphs and concurrency. [3-2-0]
Prerequisite: CPSC 211 and one of CPSC 121, MATH 220.
Corequisite: One of MATH 101, MATH 103, MATH 105, MATH 121.
- CPSC 260 (4) Object-Oriented Program Design
- Design and analysis of object-oriented programs, emphasizing data structures. Topics include: classes, interfaces, fundamental data structures, algorithmic complexity, basic debugging and testing techniques. [3-2-0]
Prerequisite: APSC 160.
- CPSC 298 (3) Co-operative Work Placement I
- Approved and supervised technical work experience in the computing industry for a minimum of 3.5 months. Normally taken during Winter Session of second year. Technical report required. Restricted to students admitted to the Co-operative Education Program in Computer Science.
- CPSC 299 (3) Co-operative Work Placement II
- Approved and supervised technical work experience in the computing industry for a minimum of 3.5 months. Normally taken during the summer following the second year. Technical report required. Restricted to students admitted to the Co-operative Education.
Prerequisite: CPSC 298.
- CPSC 301 (3) Computing in the Life Sciences
- Basic concepts, tools, and techniques for working with scientific data at larger scales, higher speeds, and lower costs that would otherwise be impossible. Applications and examples drawn from the life sciences. No prior computing background is required. Not for credit for students who have credit for any of the following: APSC 160, Computer Science AP, CPSC 110, CPSC 111, EOSC 211, or transfer credit equivalent to CPSC 111. [3-2-0]
Prerequisite: One of MATH 101, MATH 103, MATH 105, MATH 121, SCIE 001. And third-year standing or higher.
- CPSC 302 (3) Numerical Computation for Algebraic Problems
- Numerical techniques for basic mathematical processes involving no discretization, and their analysis. Solution of linear systems, including analysis of round-off errors; norms and condition number; introduction to iterative techniques in linear algebra, including eigenvalue problems; solution to nonlinear equations. [3-0-0]
Prerequisite: One of CPSC 111, CPSC 122, CPSC 126, CPSC 260 and all of MATH 200, MATH 221.
- CPSC 303 (3) Numerical Approximation and Discretization
- Numerical techniques for basic mathematical processes involving discretization, and their analysis. Interpolation and approximation, including splines and least squares data fitting; numerical differentiation and integration; introduction to numerical initial value ordinary differential equations. [3-0-0]
Prerequisite: One of CPSC 111, CPSC 122, CPSC 126, CPSC 260 and all of MATH 200, MATH 221.
- CPSC 304 (3) Introduction to Relational Databases
- Overview of database systems, ER models, logical database design and normalization, formal relational query languages, SQL and other commercial languages, transaction processing, concurrency control and recovery. [3-0-1]
Prerequisite: Either (a) one of CPSC 216, CPSC 252 and one of CPSC 220, EECE 320; or (b) CPSC 221 or (c) all of CPSC 260, EECE 320 and one of CPSC 211, EECE 310.
- CPSC 310 (4) Introduction to Software Engineering
- Specification, design, implementation and maintenance of large, multi-module software systems. Principles, techniques, methodologies and tools for computer aided software engineering (CASE); human-computer interfaces, reactive systems, hardware-software interfaces and distributed applications. [3-2-0]
Prerequisite: Either (a) all of CPSC 213, CPSC 221 or (b) all of CPSC 216, CPSC 219, CPSC 220 or (c) all of CPSC 211, CPSC 213, CPSC 260, EECE 320.
- CPSC 311 (3) Definition of Programming Languages
- Comparative study of advanced programming language features. Statement types, data types, variable binding, parameter passing mechanisms. Methods for syntactic and semantic description of programming languages. [3-0-1]
Prerequisite: Either (a) CPSC 221 or (b) all of CPSC 216, CPSC 220 or (c) all of CPSC 211, CPSC 260, EECE 320.
- CPSC 312 (3) Functional and Logic Programming
- Principles of symbolic computing, using languages based upon first-order logic and the lambda calculus. Algorithms for implementing such languages. Applications to artificial intelligence and knowledge representation. [3-0-0]
Prerequisite: Either (a) CPSC 221 or (b) all of CPSC 216, CPSC 220 or (c) all of CPSC 260, EECE 320.
- CPSC 313 (3) Computer Hardware and Operating Systems
- Instruction sets, pipelining, code optimization, caching, virtual memory management, dynamically linked libraries, exception processing, execution time of programs. [3-0-1]
Prerequisite: Either (a) all of CPSC 213, CPSC 221 or (b) all of CPSC 211, CPSC 213, CPSC 260, EECE 320.
- CPSC 314 (3) Computer Graphics
- Human vision and colour; geometric transformations; algorithms for 2-D and 3-D graphics; hardware and system architectures; shading and lighting; animation. (Consult the Credit Exclusion list within the Faculty of Science section of the Calendar.) [3-1-0]
Prerequisite: All of MATH 200, MATH 221 and either (a) one of CPSC 216, CPSC 221 or (b) all of CPSC 260, EECE 320.
- CPSC 317 (3) Internet Computing
- Computer networking, basic communication protocols, network infrastructure and routing. Common application-level protocols and principles associated with developing distributed applications. [3-0-1]
Prerequisite: CPSC 213 and either (a) CPSC 221 or (b) all of CPSC 211, CPSC 260, EECE 320.
- CPSC 319 (4) Software Engineering Project
- The design, implementation, and test of a large software system, using a team approach. [3-0-2]
Prerequisite: CPSC 310.
- CPSC 320 (3) Intermediate Algorithm Design and Analysis
- Systematic study of basic concepts and techniques in the design and analysis of algorithms, illustrated from various problem areas. Topics include: models of computation; choice of data structures; graph-theoretic, algebraic, and text processing algorithms. [3-0-1]
Prerequisite: Either (a) CPSC 221 or (b) one of CPSC 216, CPSC 260 and one of CPSC 220, EECE 320. In addition to above pre-requisites: either (a) 6 credits of 2nd Yr. MATH or STAT or (b) 3 credits of 2nd Yr. MATH or STAT with a grade of 72% or better.
- CPSC 322 (3) Introduction to Artificial Intelligence
- Problem-solving and planning; state/action models and graph searching. Natural language understanding Computational vision. Applications of artificial intelligence. [3-0-0]
Prerequisite: Either (a) CPSC 221 or (b) all of CPSC 216, CPSC 220 or (c) all of CPSC 211, CPSC 260, EECE 320.
- CPSC 340 (3) Machine Learning and Data Mining
- Models of algorithms for dimensionality reduction, nonlinear regression, classification, clustering and unsupervised learning; applications to computer graphics, computer games, bio-informatics, information retrieval, e-commerce, databases, computer vision and artificial intelligence. [3-0-0]
Prerequisite: One of MATH 221, MATH 223 and one of STAT 241, MATH 302, STAT 302 and either (a) CPSC 216 or (b) CPSC 221 or (c) all of CPSC 211, CPSC 260, EECE 320.
- CPSC 344 (3) Introduction to Human Computer Interaction Methods
- Basic tools and techniques, teaching a systematic approach to interface design, task analysis, analytic and empirical evaluation methods. [2-2-2]
Corequisite: CPSC 310.
- CPSC 349 (0) Honours Research Seminar
- Students will attend a series of research seminars presented by faculty members, produce a thesis proposal, and choose their honours thesis supervisor. Available to Honours students. Majors students with satisfactory standing may also be permitted to enrol. [1-0-0]
- CPSC 352 (4) Introduction to Software Engineering
- Specification, design, implementation and maintenance of large, multi-module software systems. Principles, techniques, methodologies and tools for software development. [3-2-0]
Prerequisite: CPSC 252.
Corequisite: EECE 320.
Equivalency: CPSC 310.
- CPSC 398 (3) Co-operative Work Placement III
- Approved and supervised technical work experience in the computing industry for a minimum of 3.5 months. Normally taken during the summer following the third year. Technical report required. Restricted to students admitted to the Co-operative Education Program in Computer Science.
- CPSC 399 (3) Co-operative Work Placement IV
- Approved and supervised technical work experience in the computing industry for a minimum of 3.5 months. Normally taken during the fall term of the fourth year. Technical report required. Restricted to students admitted to the Co-operative Education Program in Computer Science.
- CPSC 402 (3) Numerical Linear Algebra
- Investigation of the practical techniques of computational linear algebra. Orthogonal transformations and their application to the solution of linear equations, the eigenproblem, and linear least squares. Complete solution of the symmetric eigenproblem, including bisection and the QR method. Refinements of these techniques for sparse matrices. [3-0-0]
Prerequisite: CPSC 302 and one of MATH 307, MATH 223.
- CPSC 403 (3) Numerical Solution of Ordinary Differential Equations
- Investigation of practical computational methods for ordinary differential equations. Multistep and Runge-Kutta methods for initial value problems. Control of error and stepsize. Special methods for stiff equations. Shooting, finite difference, and variational methods for linear and nonlinear boundary value problems. [3-0-0]
Prerequisite: All of CPSC 303, MATH 316.
- CPSC 404 (3) Advanced Relational Databases
- Physical database design, file organization, indexing and hashing, multimedia issues, relational query processing and optimization. [3-0-0]
Prerequisite: CPSC 304 and one of CPSC 213, CPSC 218, EECE 259.
- CPSC 405 (3) Modelling and Simulation
- Numeric models of dynamic systems with emphasis on discrete stochastic systems. State description of models, common model components and entities. A thorough description of a common simulation language. Simulation using algebraic languages. Methodology of simulation: data collection, model design, analysis of output, optimization, validation. Elements of queuing theory and its relationship to simulation. Applications to models of computer systems. [3-0-0]
Prerequisite: Either (a) one of CPSC 216, CPSC 221, CPSC 252 or (b) CPSC 260; and either (a) STAT 241 or (b) STAT 200 and one of MATH 302, STAT 302.
- CPSC 406 (3) Computational Optimization
- Formulation and analysis of algorithms for continuous and discrete optimization problems; linear, nonlinear, network, dynamic, and integer optimization; large-scale problems; software packages and their implementation; duality theory and sensitivity. [3-0]
Prerequisite: MATH 340 and one of CPSC 302, CPSC 320.
- CPSC 410 (3) Advanced Software Engineering
- Specification, design, construction and validation of multi-version software systems. [3-0-0]
Prerequisite: Either (a) CPSC 310 or (b) all of EECE 310, EECE 315.
- CPSC 411 (3) Introduction to Compiler Construction
- A practical introduction to lexical analysis, syntactic analysis, type-checking, code generation and optimization. This will be used to design and implement a compiler for a small Pascal-like language. [3-0-0]
Prerequisite: CPSC 311 and one of CPSC 213, CPSC 218.
- CPSC 415 (3) Advanced Operating Systems
- Process synchronization and communication schemes, including message-passing and concepts of monitor and serializer. Virtual memory systems management and the problem of information sharing in such systems. The working set principle. Traps and interrupt handling. Elementary queuing theory and its application such as process scheduling, system balancing and load control. File systems and operating system design methodologies. [3-0-0]
Prerequisite: Either (a) one of CPSC 313, CPSC 315 or (b) EECE 315.
- CPSC 416 (3) Distributed Systems
- Concepts and design of distributed systems. Communication architecture and models for interprocess communication. Process migration, naming, distributed file systems, fault tolerance, and concurrency control. [3-0-0]
Prerequisite: All of CPSC 313, CPSC 317.
- CPSC 417 (3) Computer Networking
- Network protocols and architecture including internetworking, the Internet, layered communication protocols, routing, flow and congestion control, network performance, wired and wireless data communication. [3-0]
Prerequisite: All of CPSC 313, CPSC 317 and one of STAT 200, STAT 241.
- CPSC 418 (3) Advanced Computer Architectures
- Introduction to advanced processor architectures and taxonomical views; performance considerations. Introduction to parallel machine designs. Examination of pipeline organizations; pipelined ALU and control units; representative architectures. Exploratory non-Von Neumann architectural models including: object-oriented, tagged, capability, dataflow and RISC designs. [3-0-1]
Prerequisite: Either (a) CPSC 313 or (b) all of CPSC 315, CPSC 318.
- CPSC 420 (3) Advanced Algorithms Design and Analysis
- The study of advanced topics in the design and analysis of algorithms and associated data structures. Topics include algorithms for graph-theoretic; algebraic and geometric problems; algorithms on nonsequential models; complexity issues; approximation algorithms. [3-0-0]
Prerequisite: CPSC 320.
- CPSC 421 (3) Introduction to Theory of Computing
- Characterizations of computability (using machines, languages and functions). Universality, equivalence and Church's thesis. Unsolvable problems. Restricted models of computation. Finite automata, grammars and formal languages. [3-0-0]
Prerequisite: Either (a) CPSC 221 or (b) all of CPSC 216, CPSC 220 or (c) all of CPSC 260, EECE 320. CPSC 320 is recommended.
- CPSC 422 (3) Intelligent Systems
- Principles and techniques underlying the design, implementation and evaluation of intelligent computational systems. Applications of artificial intelligence to natural language understanding, image understanding and computer-based expert and advisor systems. Advanced symbolic programming methodology. [3-0-0]
Prerequisite: All of CPSC 312, CPSC 322.
- CPSC 424 (3) Geometric Modeling
- Introduction to curves and surfaces, in particular splines, subdivision surfaces, polgonal meshes. Principles and mathematical foundations for representing complex geometry for computer graphics and numerical simulations. Practical applications of different modeling techniques. [3-0-1]
Prerequisite: MATH 221 and one of MATH 227, MATH 317 and either (a) CPSC 216 or (b) CPSC 221 or (c) all of CPSC 211, CPSC 260, EECE 320.
Corequisite: One of CPSC 314, EECE 478.
- CPSC 425 (3) Computer Vision
- Introduction to the processing and interpretation of images. Image sensing, sampling, and filtering. Algorithms for colour analysis, texture description, stereo imaging, motion interpretation, 3D shape recovery, and recognition. [3-0-0]
Prerequisite: All of MATH 200, MATH 221 and either (a) CPSC 216 or (b) CPSC 221 or (c) all of CPSC 260, EECE 320.
- CPSC 426 (3) Computer Animation
- Motion in computer graphics for characters and their environments. Keyframing, inverse kinematics, particle systems, rigid body dynamics, contact and collision, controller-based active motion, motion capture. [3-0-0]
Prerequisite: One of CPSC 314, CPSC 414, EECE 478.
- CPSC 430 (3) Computers and Society
- Impact of computer technology on society; historical perspectives; social and economic consequences of large-scale information processing systems and automatic control; legal and ethical problems in computer applications. Computers and the individual: machine versus human capabilities, fact and fancy; problematic interface between man and machine. [3-0-0]
Prerequisite: 3 credits of Computer Science and at least third-year standing.
- CPSC 444 (3) Advanced Methods for Human Computer Interaction
- Design and evaluation methodologies and theories; formal models of the user including visual, motor, and information processing; advanced evaluation methods including laboratory experiments and field studies; HCI research frontiers. [2-2-2]
Prerequisite: All of CPSC 310, CPSC 344 and one of STAT 200, STAT 241.
- CPSC 445 (3) Algorithms in Bioinformatics
- Sequence alignment, phylogenetic tree reconstruction, prediction of RNA and protein structure, gene finding and sequence annotation, gene expression, and biomolecular computing. [3-0-0]
Prerequisite: CPSC 320 and six credits of BIOL beyond BIOL 111.
- CPSC 448 (3/6) c Directed Studies in Computer Science
- Open ordinarily to Honours students in Computer Science, with the permission of the department head. The course may consist of supervised reading, participation in a seminar, and one or more programming projects.
- CPSC 449 (6) Honours Thesis
- Under supervision of a faculty member, students investigate a research topic and prepare a thesis.
Prerequisite: CPSC 349.
- CPSC 490 (3) Student Directed Seminars
- Self-directed, collaborative studies, in a group-learning environment, initiated and coordinated by senior undergraduate students with the supervision of a faculty advisor. Course structure, enrolment and delivery methods will comply with the "Handbook for Student Directed Seminars". [3-0-0]
- CPSC 499 (3) Co-operative Work Placement V
- Approved and supervised technical work experience in the computing industry for a minimum of 3.5 months. Normally taken during the summer following the fourth year. Technical report required. Restricted to students admitted to the Co-operative Education Program in Computer Science.
- CPSC 500 (3) Fundamentals of Algorithm Design and Analysis
-
- CPSC 501 (3) Theory of Automata, Formal Languages and Computability
-
- CPSC 502 (3) Artificial Intelligence I
-
- CPSC 503 (3) Computational Linguistics I
-
- CPSC 504 (3) Data Management
-
- CPSC 505 (3) Image Understanding I: Image Analysis
-
- CPSC 506 (3) Complexity of Computation
-
- CPSC 507 (3) Software Engineering
-
- CPSC 508 (3) Operating Systems
-
- CPSC 509 (3) Programming Language Principles
-
- CPSC 510 (3) Multigrid and Multilevel Methods
-
- CPSC 511 (3) Implementation of Programming Languages
-
- CPSC 512 (3) Architecture and Control in Artificial Intelligence
-
- CPSC 513 (3) Integrated Systems Design
-
- CPSC 514 (3) Computer Graphics: Rendering
-
- CPSC 515 (3) Computational Robotics
-
- CPSC 516 (3) Computational Geometry
-
- CPSC 517 (3) Sparse Matrix Computation
-
- CPSC 519 (3) Logic Programming and Functional Programming
-
- CPSC 520 (3) Numerical Solution of Differential Equations
-
- CPSC 521 (3) Parallel Algorithms and Architectures
-
- CPSC 522 (3) Artificial Intelligence II
-
- CPSC 523 (3) Computational Linguistics II
-
- CPSC 524 (3) Computer Graphics: Modeling
-
- CPSC 525 (3) Image Understanding II: Scene Analysis
-
- CPSC 526 (3) Computer Animation
-
- CPSC 527 (3) Computer Communication Protocols
-
- CPSC 528 (3) Formal Techniques for Communication Protocols
-
- CPSC 529 (3) Definition of Programming Languages
-
- CPSC 530 (2-6) c Topics in Information Processing
-
- CPSC 531 (3-6) d Topics in Theory of Computation
-
- CPSC 532 (2-6) d Topics in Artificial Intelligence
-
- CPSC 533 (2-6) d Topics in Computer Graphics
-
- CPSC 534 (2-6) d Topics in Data Management
-
- CPSC 535 (2-6) d Topics in Simulation and Optimization
-
- CPSC 536 (2-6) d Topics in Algorithms and Complexity
-
- CPSC 537 (2-6) d Topics in Coding and Information Theory
-
- CPSC 538 (2-6) d Topics in Computer Systems
-
- CPSC 539 (2-6) d Topics in Programming Languages
-
- CPSC 540 (3) Machine Learning
-
- CPSC 541 (3) Computational Methods for Ordinary Differential Equations & Dynamical Systems
-
- CPSC 542 (2-6) d Topics in Numerical Computation
-
- CPSC 543 (3) Physical User Interface Design and Evaluation
-
- CPSC 544 (3) Human Computer Interaction
-
- CPSC 545 (3) Algorithms for Bioinformatics
-
- CPSC 546 (3) Numerical Optimization
-
- CPSC 548 (3) Directed Study
-
- CPSC 549 (6/12) c Master's Thesis
-
- CPSC 550 (3) Machine Learning II
- Prerequisite: All of CICS 505, CICS 510, CICS 515, CICS 518, CICS 520, CICS 525.
- CPSC 554 (2-6) d Topics in Human-Computer Interaction
-
- CPSC 564 (3) Data Mining
-
- CPSC 589 (3) M.Sc. Major Essay
-
- CPSC 590 (3) Research Methods in Computer Science
-
- CPSC 649 (0) Doctoral Dissertation
-
