Register

Undergraduate Computer Science Courses

The University of Waterloo offers a wide range of Computer Science courses. 

Click the link below to jump to each category:

CS 100
CS 200
CS 300
CS 400

CS 105: Introduction to Computer Programming 1

General description

This course introduces practical computer programming to students who don’t have previous programming experience. Students learn programming concepts by creating interactive visualizations, simple games, and image processing effects. They also explore fundamental imperative programming language concepts, such as variables, conditionals, loops, functions, events, and arrays. Students learn general skills, such as coding style, modular design, testing, and debugging. In addition, they explore media computation topics, such as two-dimensional graphics drawing, human input, animation, and image processing.

Logistics

Audience

  • Students in the Global Business and Digital Arts (GBDA) program
  • Fine Arts – Studio majors taking the Digital Art Specialization
  • Students interested in learning how to program

Normally available

  • Fall

Related courses

  • Successors: CS 106
  • Conflicts: CS 115, CS 135, CS 145, CS 137, and other courses in introductory computer science

For official details, see the UW calendar.

Software/hardware used

Typical reference(s)

  • Daniel Shiffman, Learning Processing (second edition), Morgan Kaufmann

Required Preparation

At the start of the course, students should be able demonstrate a basic understanding of mathematical concepts. No programming background is expected.

Learning objectives

At the end of the course, students should be able to

  • Write interactive programs that draw shapes and respond to mouse and keyboard input using the Processing programming language
  • Understand and apply concepts, such as variables, conditionals, loops, functions, and arrays
  • Read simple pieces of code to explain their function, trace code execution, and identify related errors

Typical syllabus

Introduction (3 hours)

  • What is an algorithm? What is code?
  • Code syntax and syntax errors

Drawing and attributes (3 hours)

  • Two-dimensional coordinates, drawing functions, commenting practices, the concept of sequential control flow
  • Drawing attributes and the concept of program state
  • Colour representation and hexadecimal numbers

Interaction and variables (3 hours)

  • Draw loop and the concept of program events
  • Variable declaration and initialization, variable types, and the concept of computer memory

Conditionals (3 hours)

  • Boolean logic and relational expressions
  • If-then-else statements
  • Numeric representation and binary numbers
  • Bounds detection for hit testing

Loops (6 hours)

  • While loop and for loop
  • Variable scope
  • Remapping variables
  • Nested loops

Functions (3 hours)

  • Writing custom functions, function parameters, return values
  • Variable shadowing

Arrays (4.5 hours)

  • Arrays, array elements, indexing
  • Array operation idiom

Objects and program design (4.5 hours)

  • Using classes and objects for program encapsulation
  • Modularity, testing, and debugging

Images, video, and libraries (6 hours)

  • Loading and displaying images, image pixels
  • Image processing and computational complexity
  • Video capture and processing
  • Using libraries, e.g., loading and playing sounds
 
 

 

CS 106: Introduction to Computer Programming 2

General description

This course, together with its predecessor CS 105, offers a comprehensive introduction to practical computer programming to students who don’t have previous programming experience. While the main theme of CS 105 is to develop basic skills in imperative programming (variable declarations, control flow, defining functions, basic object-oriented programming), in CS 106 we explore more general applications of programming in contexts of interest to visual artists and designers.

Logistics

Audience

  • Required by students in the GBDA program and available to students from other programs

Normally available

  • Winter

Related courses

  • CS 105

For official details, see the UW calendar.

Software/hardware used

  • Processing programming environment

Typical reference(s)

  • Shiffman, Daniel, Learning Processing 2nd edition, Morgan Kaufmann

Required preparation

At the start of the course, students should be able to

  • Declare variables in an imperative programming language and read and modify the values of those variables
  • Write simple control flow structures, such as if statements, while loops, and for loops
  • Write simple helper functions that capture repeated sub-computations
  • Declare arrays and read and write elements in them
  • Produce simple interactive sketches that draw shapes and respond to mouse and keyboard input

Learning objectives

At the end of the course, students should be able to

  • Use strings and perform basic text processing operations
  • Write programs that use basic user interface elements (buttons, sliders) and that support direct manipulation of simple shapes (circles, rectangles)
  • Write a short recursive function
  • Write programs that read data from external files and/or the internet and that store data in external files
  • Use libraries to parse tabular data (CSV) and general tree-structured data (JSON)

Typical syllabus

Processing recap (3 hours)

  • Review of programming concepts from CS 105, in terms of the basic structure of the Processing language: types, declarations, expressions, statements, and functions

Arrays (3 hours)

  • High-level operations on arrays, including appending, concatenation, and removal
  • Built-in array manipulation functions

Strings (3 hours)

  • String class
  • Working with characters and strings
  • String comparisons
  • Printing and displaying text

Input and output (3 hours)

  • Loading files in various formats (text, images, illustrations) into Processing and writing files

Advanced shapes (3 hours)

  • Drawing fancy shapes with beginShape() and endShape() using the PShape class

User interfaces (3 hours)

  • Model-view-controller architecture
  • Direct manipulation interfaces
  • User interface toolkits
  • ControlP5 library in Processing

Geometric context (3 hours)

  • Use of translate(), rotate(), and scale() to modify a program’s coordinate system
  • Building a hierarchy of transformations using pushMatrix() and popMatrix()
  • Order of operations

Recursion and fractals (3 hours)

  • Iterated function systems as a demonstration of recursion

Randomness and noise (3 hours)

  • Random() function in detail
  • Pseudorandomness
  • Applications of randomness
  • Introduction to noise()

Text processing (3 hours)

  • Decomposing text into tokens
  • Regular expressions
  • Unicode
  • Working with dates and times

Structured data processing (3 hours)

  • Dealing with table-structured (CSV) and tree-structured (JSON) data
  • Processing live data acquired from web APIs
  •  

 

 

CS 115: Introduction to Computer Science 1

General description

  •   This course introduces students to key concepts in the field of Computer Science through the use of a functional programming language.

Logistics

Audience

  •   1A students in the Faculty of Mathematics
  •   Students interested in pursuing a Computer Science minor
  •   Students interested in learning more about Computer Science

Normally available

  •   Fall, Winter, and Spring

Related courses

  • Predecessors: None
  • Successors: CS 116
  • Co-requisites: None
  • Conflicts: CS 135, CS 145, CS 137, and other courses in introductory computer science

For official details, see the UW calendar.

Software/hardware used

  •   Racket programming language
  •   DrRacket programming environment

Typical reference(s)

  •   M. Felleisen, R. Findler, M. Flatt, S. Krishnamurthi, How To Design Programs, MIT Press (First edition)

Required preparation

At the start of the course, students should be able to

  •   Demonstrate a basic understanding of mathematical concepts, including functions

No programming background is assumed.

Learning objectives

At the end of the course, students should be able to

  •   Given a clear and concise statment of a problem or task, write a program from scratch of up to fifty lines of properly-formatted, tested, and documented Racket code to solve the problem or carry out the task
  •   Use elementary data structures, such as lists and trees, in programs
  •   Use abstract list functions in programs

Typical syllabus

An introduction to functional progamming (24 hours)

  •   Basics of Racket: function application and definition in mathematics and in Racket, formal grammar and syntax, the substitution model, primitive data types (numbers, strings, characters, Boolean)
  •   Conditional expressions, including nested conditionals
  •   Design recipe for moving from problem description to code that processes data
  •   Structures and their semantics in the substitution model
  •   Lists of primitive types, lists of structures, and nested lists
  •   Structural recursion on lists and integers and on two recursive values using the design recipe

Data abstraction (7.5 hours)

  •   Basic dictionaries (number keys and string values) implemented using association lists and binary search trees
  •   Binary trees and general trees
  •   Applications, including the evaluation of arithmetic and Racket expressions (involving the use of mutual recursion)

Functional abstraction (4.5 hours)

  •   Functions as values, including parameters to other functions
  •   Abstract list functions (with a focus on map, filter, foldr, and build-list)
  •   Local definitions for both constants and functions
  •   Scope
  •   Lambda

 


CS 116: Introduction to Computer Science 2

General description

  •   CS116 continues the development started in CS115, transitions to imperative programming, and introduces important issues in Computer Science.

Logistics

Audience

  •   1B students in the Faculty of Mathematics
  •   Students interested in pursuing a Computer Science minor
  •   Students interested in learning more about Computer Science

Normally available

  •   Fall, Winter, and Spring

Related courses

  • Predecessors: CS 115, CS 135
  • Successors: CS 136, CS 230, CS 234, CS 330
  • Co-requisites: None
  • Conflicts: CS 137, CS 138

For official details, see the UW calendar.

Software/hardware used

  •   Python programming language
  •   WingIDE programming environment or alternate

Typical reference(s)

  •   A. Downey, Think Python: An Introduction to Software Design, O’Reilly Media

Required preparation

At the start of the course, students should be able to

  • Given a clear and concise statment of a problem or task, write a program from scratch of up to fifty lines of properly-formatted, tested, and documented Racket code to solve the problem or carry out the task
  • Use elementary data structures, such as lists and trees, in programs
  • Use abstract list functions in programs

Learning objectives

At the end of the course, students should be able to

  •   Given a clear and concise statement of a problem or task, write a program from scratch of up to a hundred lines of properly-formatted, tested, and documented Python code to solve the problem or carry out the task
  •   Use higher-order functions to improve the readability and efficiency of programs
  •   Use various forms of recursion (structural, accumulative, generative) in programs
  •   Use various forms of iteration (for, while) in programs
  •   Describe the basic memory model for mutation of basic types, lists, and objects in Python
  •   Distinguish between constant, linear, quadratic and exponential running times of algorithms
  •   Explain the relative advantages and disadvantages of lists and dictionaries
  •   Write useful Python programs using console and file input and output for practical tasks

Typical syllabus

Introduction to imperative programming (15 hours)

  •   Common features of imperative languages
  •   Basics of Python: assignment and introduction to mutation, basic console output and keyboard input, basic program structure, defining and using functions
  •   Relating concepts from Racket to Python: lists of basic types, if statements, including nested conditionals; basic structural recursion; abstract list functions and lambda
  •   Basic Python memory model, including lists

More advanced concepts from imperative programming (15 hours)

  •   Additional forms of recursion: accumulative and generative
  •   Iteration: bounded (for loop), guarded (while loop); simple and nested iteration; applications, including linear and binary search algorithms
  •   Investigating several sorting algorithms
  •   Dictionaries
  •   Basic use of classes (in comparison to Racket structures), introduction to object-oriented principles in Python, and mutation of objects
  •   Functions as parameters: extending the design recipe to include polymorphism
  •   File input and output: basic and structured file processing, basic exception handling (try-except block)
  •   Additional topics, possibly including programming with real world data, web pages, etc.

Issues in Computer Science (6 hours)

  •   Basic introduction to run-time analysis and simple run-time classes (constant, logarithmic, linear, linearithmic, quadratic, exponential) through studied algorithms
  •   Discussion of design issues related to data structures (for example, choosing between lists and dictionaries) and effects on complexity and memory requirements
 
 

 

CS 135 Designing Functional Programs

 

Objectives

This course covers the principles of program design and the fundamentals of computation through functional evaluation.

Intended Audience

CS 135 is for students who would prefer a more conceptual treatment of introductory computer science in a simple language that is educationally effective but not commercially relevant. While the course is designed to be taken by those with no prior programming experience, students with prior experience will also find it relevant, due to its unusual focus. It is suitable for both CS majors and non-majors.

Related Courses

Antirequisites: CS 115, 121, 122, 123, 125, 131, 132, 133, 134, 137, 138, 145, CHE 121, CIVE 121, ECE 150, GENE 121, PHYS 139, SYDE 121

Successor: CS 136.

Hardware and Software

Used in course: Programs are written in subsets of the language Scheme. Student labs are equipped with the DrRacket integrated development environment running on networked personal computers. Versions for Windows, Mac OS, Unix/X and Linux are freely downloadable for use on computers owned by students.

References

How To Design Programs by Felleisen, Findler, Flatt, and Krishnamurthi, MIT Press, 2003. This book is available in its entirety on the Web, though students are encouraged to purchase a physical copy.

I-Clicker RF Response Remote (Required) .

Schedule

Three hours of lecture per week, plus a tutorial. Available in Fall and Winter.

Outline

Simple Forms of Data (3 hours)

Numbers, arithmetic, function definition and composition, design recipes, conditional expressions, symbols.

Structured Data (3 hours)

Structure definitions, constructors, selectors, data definitions, type predicates, functions for mixed data.

Syntax and Semantics (1.5 hr)

Vocabulary and grammar of the beginning student language.

Arbitrarily Large Data: Lists (6 hours)

Definition of lists, designing functions to process and produce lists, recursive definition of natural numbers, recursive data definitions.

Non-Linear Structures (6 hours)

Multi-clausal recursive data definitions, trees, mutually referential data definitions, design methods for complex data, iterative refinement, multiplexing.

Abstraction Through Local Definitions (9 hours)

Encapsulation, block structure, binding, functional abstraction, filters, polymorphism, generic functions, parametric data definitions, functions as data, functions that produce functions, anonymous functions, abstract list and tree functions (definition and use).

Generative Recursion (6 hours)

Generative versus structural recursion, backtracking algorithms, accumulators and accumulative recursion.

History of Computer Science (1.5 hours)

Babbage, Hilbert, Godel, Church, Turing. Early development of electronic computers and programming languages. History of concepts covered in this course.

 

 

 

CS 136 Elementary Algorithm Design and Data Abstraction

 

Objectives

This course examines elementary data structures and algorithms using the functional and imperative paradigms of computation, and discusses issues surrounding the effective use of programming languages in “real-world” environments.

Intended Audience

CS 136 is for Mathematics students who have taken CS 135.

Related Courses

Prerequisites: Full-time degree registration in the Faculty of Mathematics; CS 116 or at least 60% in CS 135 or CS 145 taken fall 2011 or later.

Antirequisites: CS 134, 137, 138, 145 taken fall 2010 or earlier.

Hardware and Software

Programs are to be written in Scheme and C. Student labs are equipped with the DrScheme integrated development environment running on networked personal computers. Versions for Windows, Mac OS, Unix/X and Linux are freely downloadable for use on computers owned by students. C programs will be compiled using Clang/LLVM in the RunC environment. gedit is recommended for use as an editor.

References

C Programming: A Modern Approach, 2nd edition by K.N. King (W.W. Norton & Company).

How To Design Programs by Felleisen, Findler, Flatt, and Krishnamurthi, MIT Press, 2001. This book is available in its entirety on the Web, though students are encouraged to purchase a physical copy.

Lecture slides will be made available online.

Schedule

Three hours of lecture per week, plus a one-hour tutorial.

Outline

Mutation, interaction, and encapsulation (7.5 hours)

Mutation of identifier-value bindings in Scheme. Sequencing of statements. Basic I/O in Scheme. State encapsulation (primitive objects). Semantics of structure and list mutation in Scheme. Box-and-pointer diagrams.

The memory model and introduction to C (7.5 hours)

The memory model. Variable declaration, assignment and infix expressions in C. Basic I/O in C. Compilation. Pointers, addresses, garbage collection, and memory reuse in Scheme. Modelling functions, procedures, and recursion in C. The limits of recursion in C. Loop constructs.

Efficiency (7.5 hours)

O-notation. Analysis of simple programs in Scheme and C. Logarithmic-time list operations. Vectors/arrays in Scheme and C and their uses. Linear and binary search. Hash tables and their uses. Pointers and strings in C.

Memory management (6 hours)

Structures in C. Memory allocation and deallocation. Lists and queues in C. Safety and usability issues.

Abstract data types (6 hours)

Information hiding in Scheme. A module system. Libraries. Definition and implementation of ADTs. Separate compilation in C. Overview of approaches to abstraction and code reuse in other languages (Java, C++, ML, Haskell).

History of Computer Science (1.5 hour)

History of concepts covered in this course.

 

 

 

CS 137 Programming Principles

 

Objectives

This course introduces software engineering students to elementary data structures, and to the functional programming paradigm.

Intended Audience

Level 1A Software Engineering undergraduates. It is assumed that students have experience developing well-structured, modular programs.

Related Courses

Antirequisites: CS 115, 135, 136, 145, CHE 121, CIVE 121, ECE 150, GENE 121, PHYS 239, SYDE 121

Successor: CS 138.

Hardware and Software

Used in course: An integrated development environment (IDE) for C++ (such as xCode for Mac OS X).

References

C Programming: A Modern Approach 2nd ed. Author: K.N. King

Schedule

Three hours of lecture per week, plus a two-hour lab and a one-hour tutorial. Normally available in Fall only.

Outline

Introduction and review (6 hours)

Review of hardware and software, problem solving and programming, including declarations, selection and looping constructs, I/O.

Subprograms (6 hours)

Functions. Scoping. Parameter passing, by value and by reference. Top-down design. Programming with stubs.

Structured Data (7.5 hours)

Arrays. Structures. Arrays of structures. Multidimensional arrays. Appropriate choice of data structures. String processing and tokenization.

Recursion (3 hours)

Introduction to recursive procedures and functions.

Analysis (1.5 hours)

Introduction to O-notation, space and time efficiency, and complexity.

Sorting Algorithms (4.5 hours)

Algorithm design and efficiency, through discussion of of elementary sorting algorithms (insertion sort, selection sort) and advanced sorting algorithms (mergesort, quicksort, heapsort).

Pointers and Dynamic Structures (6 hours)

Introduction to pointers, memory allocation and deallocation, singly and doubly-linked lists.

History of Computer Science (1.5 hours)

Babbage, Hilbert, Godel, Church, Turing. Early development of electronic computers and programming languages. History of concepts covered in this course.

 

 

CS 138 Introduction to Data Abstraction and Implementation

Objectives

This course introduces Software Engineering students to elementary data structures and their implementation, and to the object-oriented programming paradigm.

Intended Audience

Software Engineering undergraduates who have taken SE 1A. It is assumed that students have experience programming in an imperative language such as C or C++.

Related Courses

Prerequisite: CS 137

Antirequisites: CS 116, 135, 136, 145, 146

Successor: CS 241.

Hardware and Software

Used in course:

  1. The UNIX operating system, the Bash shell, and command-line tools such as the g++ compiler.

References

  1. Absolute C++, 6th edition, by Walter Savitch and Kenrick Mock. Pearson.

Schedule

Three hours of lecture per week, plus a one-hour tutorial. Normally available in Winter only.

Outline

Introduction (3 hours)

Operating system and Unix concepts, programming language concepts.

Introduction to C++ concepts (3 hours)

C++ basics, basic types, IO, use of simply library elements (string, vector).

ADT and their implementations as linked structures (12 hours)

The stack, queue, and priority and queue ADTS; the linked list, sorted linked list; Trees, binary trees, binary search trees; the C/C++ memory model: pointers vs references, stack vs freestore; implementing and travesing linked structures; recursion and stack frams; recursive vs iterative solution to ADTs; space and time complexity of solutions; simple testing and debugging strategies.

Object-based computing (9 hours)

Interface vs implementation; class definitions, instantiation, object construction and destruction; object vs pointers to objects; interface design and abstraction, responsibility allocation; the adapter design pattern.

Introduction to object-oriented programming (9 hours)

Introduction to inheritance and its implementation in C++; introduction to generics, type parameterization, and C++ templates; the template method design pattern; use of generic data containers and the Standard Template Library; design heuristic and strategies for object-oriented programming.

CS 146: Elementary Algorithm Design and Data Abstraction (advanced version)

(Emphasized text represents additional material not found in CS 136.)

Goals

  • To familiarize students with key concepts in introductory computer science from an imperative perspective and to contrast this with the functional perspective taken in CS 145;
  • To allow students to complete the CS portion of their Math core requirements and, if desired, to continue on to second-year core courses in CS;
  • To provide top students with appropriate challenges and enrichment and to explore topics in greater depth than possible in CS 136.

Logistics

Intended for 1B students in the Faculty of Mathematics. Normally available Winter.

Related courses (see calendar for official details)

Predecessors: CS 145 with a grade of at least 75%.

Successors: CS 246, CS 245, CS 251.

Conflicts: CS 116, 136, 137, 138, 145 taken fall 2010 or earlier.

Software used: Racket (dialect of Scheme), Unix-like development environment (Linux, OS X, Cygwin), C compiler.

Typical Reference(s)

C Programming: A Modern Approach (second edition) by K.N. King (W.W. Norton & Company).

The C Programming Language (second edition) by B. Kernighan and D. Ritchie (Prentice-Hall).

Required preparation

A mark of 75% or greater in CS 145. Students who complete CS 145 with a mark of less than 75% may apply for instructor consent to take CS 146. Students who complete CS 135 with an outstanding record may also apply for instructor consent. Prior experience in imperative programming (in particular using C or C++) will be considered in such requests, but will not be the main criterion; aptitude is still of primary importance.

Learning objectives

At the end of the course, students should have the ability to:

  • given a clear and concise statement of a problem or task, write a program from scratch of up to two hundred lines of properly-formatted and documented C code to solve the problem or carry out the task;
  • use elementary data structures such as lists and trees in such programs, with proper attention to explicit allocation and deallocation of memory;
  • be able to write programs in both Scheme and C that obtain input from external sources and/or send output to external sources (interaction, files, redirected files) and whose I/O behaviour conforms to precise specifications;
  • analyze the running time and space requirements of such programs and describe examples of data that demonstrate that the analysis cannot be improved.

Typical syllabus

Introduction to C and elementary mutation in Scheme

Command-line interfaces. The memory model. Variable declaration, assignment and infix expressions in C. Basic I/O in C. Compilation. Mutation of identifier-value bindings in Scheme. Modelling functions, procedures, and recursion in C. Loop constructs. Algorithm analysis in C. File I/O in C and Scheme. Program organization and testing methods.

Memory management

Structures in C. Memory allocation and deallocation. Mutable structures, sharing, and garbage collection in Scheme. Space analysis in C and Scheme.

Mutable ADTs

Mutable lists, queues, deques, and trees in C. Time-space tradeoffs among mutable and immutable ADT implementations.

Low-level abstractions

Pointer arithmetic in C. Arrays in C and vectors in Scheme. Search, sorting, and graph algorithms revisited. Strings in C. Elementary hashing. Bitwise operations. Processing binary data. Libraries in C and Scheme.

Implementing high-level abstractions

Interpreting Scheme in C. Compiling Scheme to C. Compiling to virtual machines.

CS 200: Concepts for Advanced Computer Usage

General description

This course examines important concepts underlying major personal computer application categories and the application of those concepts to problem solving. Students discover how to efficiently use word processing, graphics, and database applications and they develop some basic intra/inter-application scripting skills. The course also covers some basic system administration.

Logistics

Audience

  • Non-CS majors with significant computer experience who wish to deepen their understanding of computers and how to use them effectively and efficiently.

Normally available

  • Fall and Spring

Related courses

  • Pre-requisites: Not open to Computer Science students

For official details, see the UW calendar.

Software/hardware used

  • Macintosh computers are used in the labs
  • Students are encouraged to use their own computer for assignments
  • *Most of the software used in the course runs on both Macintosh and Windows computers

Typical reference(s)

  • R. Williams, The Non-Designers Design Book, 4th ed., Peachpit Press, 2015
  • R. Williams, The Mac is not a Typewriter, 2nd ed., Peachpit Press, 2003
  • Recommended: J. Niederst, Learning Web Design, 3rd ed., O’Reilly & Associates, 2003
  • Recommended: Eric Meyer, CSS Pocket Reference 4th ed., O’Reilly Media Inc., 2011

Required preparation

At the start of the course, students should be able to

  • Use standard application software

Learning objectives

At the end of the course, students should be able to

  • Use effective strategies for exploring an application’s interface to better understand how to use new applications
  • Properly format and design visually appealing and professional documents
  • Write simple scripts to automate repeated tasks
  • Use database management software to manage and interpret large amounts of data
  • Effectively manage personal files through strategic back ups
  • Explain the difference between pixel and vector graphics and design simple images
  • Write HTML and CSS code to create functional and visually appealing web pages
  • Use named styles in a variety of applications to more efficiently create visual consistency

Typical syllabus

Methodology (3 hours)

  • Techniques for efficiently learning and using applications and for diagnosing problems

System administration (3 hours)

  • Booting
  • System extensions
  • File systems and file system maintenance
  • File system organization
  • Security and access control
  • Backup disciplines

Structured word processing (3 hours)

  • Character versus paragraph styles
  • Conditional text
  • Good graphical design

Vector and pixel graphics (6 hours)

  • Colour models
  • Half-toning and dithering
  • Image manipulation, layers and masks
  • Vector object properties and named graphical styles
  • Bezier curves

Networking and the internet (3 hours)

  • Web site structure, design, and security
  • HTML
  • CGIs
  • Cascading style sheets
  • Good graphical design

Scripting (6 hours)

  • Intra-application scripting
  • System-level inter-application scripting
  • Programming in the small
  • Debugging

Relational databases (9 hours)

  • Table and form design
  • Data validation
  • Referential integrity
  • Indices
  • Client/server databases
  • Serving the web from a database
  • SQL

Social media (3 hours)

  • Usage
  • Ethics
  • Privacy
  • Usefulness
 
 

 

CS 230: Introduction to Computers and Computer Systems

General description

This course introduces hardware and software concepts used in computer systems. Specific topics include machine-level programming, memory organization, and basic I/O mechanisms.

Logistics

Audience

  • 2nd-year students with an interest in Computer Science
  • Not open to Computer Science students

Normally available

  • Winter

Related courses

  • Predecessors: One of CS 116, 136, 138, 146, not open to Computer Science students
  • Successors: CS 338, CS 436
  • Conflicts: CS 241, CS 251

For official details, see the UW calendar.

Software/hardware used

  • UNIX, MIPS Simulator

Typical reference(s)

  • D. Patterson, J. Hennessy, Computer Organization and Design, 4th ed., Morgan Kaufmann

Required preparation

At the start of the course, students should be able to

  • Follow programs written using imperative control flow
  • Write simple imperative programs using lists, iteration, and array indexing for both read and write (mutable memory model)
  • Use basic algebra, calculus, and probability (for performance analysis)

Learning objectives

At the end of the course, students should be able to

  • Write short machine- and assembly-language programs to perform simple data manipulation
  • Describe data representations used by computer hardware at the bit level, operate on these representations, and compute their values
  • Explain some simple processor implementation optimization techniques, in particular pipelining, and how differences in code ordering can impact performance for processors using these optimizations
  • Compare basic memory and I/O architectures and how they can impact performance
  • Compare various forms of multiprocessing computing platforms
  • Explain the basic functionality and components of an operating system

Typical syllabus

Introduction (2 hours)

Assembly language (8 hours)

  • Fundamental operation and components of a computer
  • Registers vs. memory / control flow / indirection
  • Build process, declarations, assembler directives
  • Stacks, subroutines, arrays

Data representation and arithmetic (4 hours)

  • Binary representation of integers, bit operations
  • Other representations: ASCII, UTF8, strings, floating point

Compiling and linking (4 hours)

  • Assembler: opcodes and symbol table
  • Linker: import/export symbols, relocation
  • Compiler: control flow & arithmetic expressions

Basic processor design (4 hours)

  • Datapath, pipelining, hazards

Memory and I/O devices (6 hours)

  • Caching and virtual memory
  • Secondary storage
  • I/O mechanisms: programming, interrupt, DMA, parallel vs. serial, etc.

Multiprocessing (6 hours)

  • Basic concurrency concepts: synchronization and mutual exclusion
  • Scalar vs. superscalar processing
  • Hardware threading
  • Distributed parallel systems

Operating systems (2 hours)

  • Brief overview of components
 
 

 

CS 231: Algorithmic Problem Solving

General description

This course introduces various algorithmic and heuristic techniques that can be employed to solve a wide variety of problems using a computer. Students learn both the advantages and the pitfalls of translating a real-world problem into a formal specification, and consider the subsequent steps of choosing one or more paradigms, analyzing the algorithms, and implementing them. Specific paradigms taught include exhaustive search, divide and conquer, greedy, and dynamic programming approaches. Students who successfully complete the course can use these approaches to design and develop efficient programs for a wide variety of applications.

Logistics

Audience

  • Students wishing to understand how choices made in program design can significantly affect performance and how to make these choices
  • Students doing the Computer Science minor or Computing option.
  • Highly recommended for students in Information Management and similar fields and for those in the Mathematics/Teaching plan
  • Not open to Computer Science majors and SE and CFM students (take CS 341 instead)

Normally available

  • Spring

Related courses

  • Predecessors: One of CS 116, 136, 138, 146. Students who have taken introductory computer courses outside the Math Faculty should consult a CS advisor to determine if they are prepared for this course.
  • Successors: CS 234, CS 338, CS 370, CS 431 and CS 487.
  • Conflicts: CS 341

For official details, see the UW calendar.

Software/hardware used

  • Python (Note: Students should check which version of Python will be used in class.)

Typical reference(s)

  • Anany Levitin, Introduction to the Design and Analysis of Algorithms, 3rd ed., Pearson, 2011.

Required preparation

At the start of the course, students should be able to:

  • Use and follow mathematical reasoning and notation; in particular, work comfortably with simple predicate logic, functions, and elementary probability.
  • Describe basic quadratic sorting algorithms, such as Selection Sort or Insertion Sort.
  • Given a simple, well-specified computational task, write a program in a high-level imperative language (e.g., Python, C, or Java) and generate appropriate test cases. Use as appropriate simple types, built-in compound types and control idioms, such as selection, iteration, and recursion. These programs should not require more than a single routine, possibly together with a small number of additional helper routines.
  • Define and write programs that work with recursively defined structures, such as binary trees.

Note: The course uses Python for its programming examples and assignments. Students will be expected to have background in an imperative programming language; materials detailing Python syntax will be provided.

Learning objectives

At the end of the course, students should be able to

  • Describe the steps taken in solving a real-world problem on a computer.
  • Explain and use the concepts of asymptotic running time, order notation, worst-case, average-case, and best-case complexity, and lower and upper bounds. Given a simple algorithm written in pseudocode, determine and informally justify its asymptotic running time, as expressed in order notation.
  • Describe situations in which the greedy paradigm is applicable and situations in which it yields an efficient algorithm. Given a simple problem, be able to form a greedy algorithm, and, when appropriate, form an example input that shows its inefficiency.
  • Describe situations in which divide-and-conquer can be applied and those in which it is unsuitable. Given a suitable problem, form an algorithm that uses divide-and-conquer and analyze it using recurrence relations.
  • Describe situations in which dynamic programming can be used. Given a suitable problem, form and analyze a dynamic-programming algorithm.
  • Explain various methods for exploring the search space, including exhaustive search, backtracking, and branch-and-bound. Given a simple problem, form an algorithm using one of these methods and informally analyze the asymptotic running time, as expressed in order notation.
  • Explain the notions of hardness, reduction, and lower bounds.
  • Explain how various approaches, such as approximation algorithms and heuristics, can be used on hard problems.
  • Write, test, and debug programs in the Python language that incorporate the ideas described above.

Typical syllabus

Basic concepts (7 hours)

  • Steps: real-world problem, formal statement, algorithms, analysis, implementation, testing
  • Types of problems: decision, search, optimization, constraint-satisfaction, counting, enumeration
  • Analysis of time and space requirements using asymptotic notation; solution of recurrence relations
  • Python language review: basic data types, functions, branching, iteration, recursion, classes

General approaches (18 hours)

  • Exhaustive search
  • Greedy algorithms
  • Divide-and-conquer
  • Dynamic programming
  • Backtracking
  • Branch-and-bound

Hardness (3 hours)

  • Lower bounds
  • NP-completeness

Beyond hardness (5 hours)

  • Fixed-parameter algorithms
  • Randomized algorithms
  • Approximation algorithms
  • Heuristics
  • On-line algorithms
 
 

CS 234: Data Types and Structures

General description

This course introduces widely used and effective methods of data organization, focusing on data structures, their algorithms, and the performance of these algorithms.

Students learn how the choice of a data structure affects the performance and usability of applications, e.g., in web browsing and searching, computer databases, data analysis, text processing, etc. Specific topics include lists, stacks, queues, sets, maps, priority queues, trees, and graphs, together with general algorithmic techniques, such as sorting, searching, and other transformations on data. Students who successfully complete the course can use these tools to design and develop efficient programs for a wide variety of applications.

Logistics

Audience

  • Students wishing to understand how choices made in program design can significantly affect performance and how to make these choices
  • Students doing a Computer Science minor
  • Highly recommended for students in Information Management and similar fields and for those in the Mathematics/Teaching plan
  • Computer Science majors and SE and CFM students should take CS 240 instead

Normally available

  • Fall, Spring

Related courses

  • Predecessors: One of CS 116, 136, 138, 145 taken fall 2010 or earlier, 146; Not open to Computer Science students. The initial topics in CS 234 will present some material new to those coming out of CS 116 (but covered in CS 136) and some material new to those coming out of CS 136 (but covered in CS 116). Students who have taken introductory computer courses outside the Math Faculty should consult a CS advisor to determine if they are prepared for this course.
  • Successors: CS 338
  • Co-requisites: None
  • Conflicts: CS 240

For official details, see the UW calendar.

Software/hardware used

  • Python (Note: Students should check which version of Python will be used in class.)

Typical reference(s)

  • Rance D. Neśaise, Data Structures and Algorithms Using Python, Wiley, 2010

Required preparation

At the start of the course, students should be able to

  • Use and follow mathematical reasoning and notation; in particular, work comfortably with simple predicate logic, functions, and elementary probability.
  • Describe basic quadratic sorting algorithms, such as Selection Sort or Insertion Sort.
  • Given a simple, well-specified computational task, write a program in a high-level imperative language (e.g., Python, C, or Java) and generate appropriate test cases. Use as appropriate simple types, built-in compound types and control idioms, such as selection, iteration, and recursion. These programs should not require more than a single routine, possibly together with a small number of additional helper routines.
  • Define and write programs that work with recursively defined structures, such as binary trees.

Note: The course uses Python for its programming examples and assignments. The necessary syntax and idiom will be presented at the start of the course as a review for those who know Python and an explanation for those who don’t. Experience in other common imperative languages, such as C or Java, will suffice.

Learning objectives

At the end of the course, students should be able to

  • Describe several common computer applications where the choice of data structure can make the difference between efficient usability and complete non-functionality. For each application, describe one data structure appropriate to the application and one structure inappropriate to the application (although appropriate in some other context).
  • Explain the concept of “asymptotic run time” and the effects of logarithmic, linear, quasi-linear, quadratic, cubic, and exponential run times. Given a simple algorithm, determine and informally justify its asymptotic run-time, as expressed in order notation.
  • Explain the benefits of abstraction and representation independence.
  • Explain the concept of Abstract Data Type (ADT). Define several different ADTs (e.g., Stack, Queue, Priority Queue, and Map), and give a sample application for each. Explain the complexity of some common implementations of these ADTs. Given a well-specified computational problem, determine which (if any) would assist the solution.
  • Explain how external memory differs from internal memory, and describe how this difference affects the performance of a program. Give several examples of real-world tasks requiring external memory, and describe a structure and algorithm appropriate for each.
  • Explain and justify the best- and worst-case behaviours of simple quadratic sorting algorithms, as well as Mergesort, Heapsort, Quicksort, and at least one non-comparison-based algorithm. Select the appropriate algorithm for a given set of circumstances. Apply sorting-based techniques to algorithmic problems, such as elimination of duplicates.
  • Describe data structures and algorithms for efficient traversals of graphs (networks) and computations of minimum spanning trees.
  • Explain how specialized data structures can lead to efficient solutions to problems. Illustrate this principle by describing algorithms and data structures for a particular real-world problem (e.g., text compression, processing geometric data, etc.).
  • Write, test, and debug programs using the above structures and algorithms in the Python language or another imperative language known to or subsequently learned by the student. (At the instructor’s discretion, students may be allowed to code partially in a language other than in Python. Regardless of such permission, students may be tested on the Python language in assignments and/or exams.)

Typical syllabus

Basic concepts (12 hours)

Note: Each student should find some parts of this material as new and some as review depending on their background.

  • Python language: basic data types, functions, selection, iteration, recursion, strings, association lists, console I/O, and file I/O
  • Runtime of an algorithm: worst-case, best-case, and average-case
  • Asymptotic analysis and order notation
  • Definition and examples of abstract data types
  • Arrays and linked lists

Sorting algorithms (3 hours)

  • Review of Selection Sort and Insertion Sort
  • Mergesort
  • Quicksort
  • Non-comparison-based sorting algorithms (e.g., Bucket Sort, Radix Sort)
  • The worst-case, best-case, and average-case complexity of these algorithms
  • Selecting an appropriate algorithm for a specific application

Stacks, queues, and priority queues (4 hours)

  • Stacks and queues
  • Priority Queue ADT and simple implementations
  • Heaps and Heapsort
  • Application to problems, such as selection

Map (or Dictionary) ADT (9 hours)

  • Map ADT and simple implementations
  • Linear search and binary search
  • Self-organizing lists
  • Balanced search trees (e.g., 2-3-4 trees)
  • Searching in external memory
  • Hashing: key-indexed search, simple hash functions, and collision-resolution strategies
  • Example applications

Graphs (5 hours)

  • Adjacency list and matrix representations
  • Depth-first and breadth-first traversals of graphs
  • Minimum spanning trees as a case study of algorithms and data structures

Minimum spanning trees as a case study of algorithms and data structures (3 hours)

  • A case study in selecting, designing, and implementing data types for a real-world problem (e.g., text compression/retrieval, geometric data, etc.)
 
 

 

CS 240: Data Structures and Data Management

General description

This course introduces widely used and effective methods of data organization, focusing on data structures, their algorithms, and the performance of these algorithms. Specific topics include priority queues, sorting, dictionaries, and data structures for text processing.

Students will learn to

  • Analyze, apply, and use various data structures and data-management techniques in a variety of applications
  • Perform rigorous complexity analyses of simple algorithms and data structures, which includes writing correct mathematical proofs on inductively-defined structures and solving simple recurrence relations
  • Compare different data-structuring techniques from the point of view of time, memory requirements, etc.
  • Select a good data structure to solve a specific algorithmic problem
  • Apply data structures correctly and efficiently in one or more high-level programming languages, including C++

Logistics

Audience

  • 2B Computer Science students

Normally available

  • Fall, Winter, and Spring

Related courses

  • Predecessors: CS 245 (logic) or SE 212; CS 246 or 247 (programming); any of STAT 206, 230, 240 (probability)
  • Successors: Most third-year CS major courses
  • Conflicts: Other courses that seriously consider efficiency and correctness of fundamental data structures and their algorithms

For official details, see the UW calendar.

Software/hardware used

  • UNIX, C++

Typical reference(s)

  • R. Sedgewick, Algorithms in C, 3rd ed, Parts 1-4. Addison Wesley

Required preparation

At the start of the course, students should be able to

Analytical:

  • Define and explain order notation; perform complexity analyses of simple algorithms
  • Define “abstract data type” or ADT; explain the utility of this concept
  • Perform basic computations of discrete probability and expectation
  • Use mathematical induction on recursively defined structures, including finding simple errors in inductive arguments
  • Prove simple properties of program fragments correct through the use of pre-conditions and post-conditions for loops and recursive calls

Computational and algorithmic:

  • Design, implement, test, and debug C++ programs to solve problems requiring hundreds of lines of code
  • Define the ADTs for stacks and queues; write efficient implementations in C/C++
  • Describe tree structures, including binary search trees and multi-way trees; use these structures in C/C++ programs
  • Describe basic sorting algorithms (including Quicksort) and implement them in C/C++
  • Explain the notion of a hash table (students don’t have to describe the algorithms or their efficiency)

Learning objectives

At the end of the course, students should be able to

  • Perform rigorous asymptotic analyses of simple algorithms and express the result using order notation; compare algorithms based on their asymptotic complexity; and prove formal results involving order notation
  • Apply the priority-queue ADT to solve various application problems, implement a priority queue using heaps, and analyze the complexity of common implementations of heap operations
  • Develop best-, worst- and average-case analyses of sorting algorithms, including Quicksort, and explain the ramifications of these analyses in practice; explain the basic principles of randomized algorithms and their potential advantages, specifically in the case of Quicksort; explain the difference between comparison-based sorting and non-comparison-based sorting algorithms, and when and why the latter may run faster; and apply sorting-based techniques to algorithmic problems, such as elimination of duplicates
  • Develop bounded-height search trees that accommodate efficient (i.e., O(log n)) implementations of search, insert, and delete; evaluate which search tree techniques are best suited to various application scenarios (e.g., B-trees are useful for large-scale data structures stored in external memory)
  • Explain the advantages and disadvantages of various hashing techniques; identify the best hashing techniques to use in a particular application scenario; and recognize when hashing techniques are preferable to other dictionary implementations
  • Design data structures for real-world data (where keys are often inherently multidimensional) in such a way that common operations (including range search) can be implemented efficiently
  • Design special data structures that can efficiently store and process words and strings, and select and apply a suitable technique for data compression in a specific application scenario

In addition to the above language-independent skills, students should be able to apply (code, debug, and test) any of the above structures and algorithms in C++, using appropriate design methodologies and language features. Students should be prepared to transfer these abilities to other languages (once learned).

Typical syllabus

Introduction and review (3 hours)

  • Basic computer model: the random-access machine
  • Runtime of an algorithm: worst-case, best-case, and average-case
  • Asymptotic analysis, order notation, growth rates, and complexity

Stacks, queues, and priority queues (3 hours)

  • Review of stacks and queues
  • Priority queue ADT and simple implementations
  • Heaps and Heapsort
  • Using heaps to solve the selection problem

Sorting and analysis of randomized algorithms (5 hours)

  • Quicksort (non-randomized): worst-case, best-case, and average-case complexity
  • Randomized quicksort and its analysis; application to selection and its analysis
  • Lower bound on comparison-based sorting
  • Non-comparison-based sorting algorithms (e.g., Counting Sort and Radix Sort)

Search trees (5 hours)

  • Dictionary ADT and simple implementations
  • Binary search trees (insert and delete operations and analysis)
  • Balanced search trees (insert and delete operations and analysis; instructors will normally choose two or more AVL trees, 2-3 trees, red-black trees, etc.)
  • 2-3-4 trees and B-trees (search, insert, and delete operations and analysis)

Hashing (5 hours)

  • Key-indexed search, simple hash functions
  • Collision resolution: chaining and open addressing
  • Complexity of search, insertion, and deletion
  • Extendible hashing

Range search and multidimensional dictionaries (5 hours)

  • Range search in a binary search tree
  • Data structures for orthogonal range search: quad trees, Kd-trees, range trees

Algorithms and data structures for text processing (8 hours)

  • Dictionaries for text strings: radix trees, tries, compressed tries, suffix tries
  • String matching algorithms: brute force, finite automata, the Knuth-Morris-Pratt algorithm
  • Text compression: Huffman codes, Lempel-Ziv B, Burrows-Wheeler Transform (BWT)
 


CS 246: Object-Oriented Software Development

General description

This course introduces students to basic UNIX software development tools and object-oriented programming in C++ to facilitate designing, coding, debugging, testing, and documenting medium-sized programs. Students learn to read a specification and design software to implement it. Important skills are selecting appropriate data structures and control structures, writing reusable code, reusing existing code, understanding basic performance issues, developing debugging skills, and learning to test a program.

Logistics

Audience

  • 2A Computer Science students

Normally available

  • Fall, Winter, and Spring

Related courses

  • Predecessors: CS 136 or 138 (with at least 60%), CS 145 (before Fall 2011), or CS 146 (programming in C)
  • Successors: CS 240 and CS 241 (and then most CS upper-year courses)
  • Co-requisites: Courses that develop strong programming skills and the ability to use tools to create software

For official details, see the UW calendar.

Software/hardware used

  • Unix, C++

Typical reference(s)

  • C++ Primer (5th edition), by Stanley B. Lippman, Josée Lajoie and Barbara E. Moo, Addison-Wesley, 2012.
  • Absolute C++ (6th edition), by Walter Savitch and Kenrick Mock, Pearson, 2015.

Required preparation

At the start of the course, students should be able to:

  • Design, implement, test, and debug C programs to solve problems requiring less than a hundred lines of code using types, variables, arrays, structures, loops, conditionals, procedures, functions, and dynamic memory
  • Explain basic properties of the C memory model: bytes vs. words, memory as an array, run-time stack and stack frames, memory allocation on the heap vs. automatic allocation on the stack, pointers as memory addresses

Learning objectives

At the end of the course, students should be able to:

  • Design, implement, test, and debug C++ programs to solve problems requiring hundreds of lines of code, making appropriate use of
  •  
    • types, variables, arrays, strings, and dynamic memory; loops, conditionals, and other control structures; structures, unions, and enumerations; procedures and functions; the preprocessor; formatted and unformatted I/O
    • classes, objects, overloading, and single inheritance
    • a subset of the STL, including vector, list, and map
    • assertions and exceptions
    • basic software development tools, including makefiles, a shell, a revision control system, and a debugger
    • test suites for unit testing, white and black box testing
    • structured programming, incremental development
    • interface design, abstractions, information hiding, cohesion and coupling
    • a subset of UML to specify classes, objects and relationships between them
    • a selection of design patterns, including adapter and template
  • Explain the following properties of the memory model used in C++, including their impact on time and space efficiency when designing code: bytes vs. words, memory as an array, run-time stack and stack frames, memory allocation on the heap vs. automatic allocation on the stack, pointers as memory addresses, the representation of objects in memory
  • Define and explain at an elementary level basic software-engineering concepts, including the water-fall model and other development methodologies

Typical syllabus

Shell (4 hours)

  • File system, pattern matching, quoting, shell/system commands, file permission, redirection, shell programming

C++ (16 hours)

  • Declarations, expressions, control structures, structured programming, preprocessor, I/O, dynamic allocation, objects, overloading, inheritance, templates, STL, separate compilation

Unix tools (8 hours)

  • Compiler, debugging and the debugger (e.g., GDB), code management (e.g., make), version control (e.g., SVN)

Software engineering (8 hours)

  • Development process, design (UML), language selection, patterns, testing

CS 247: Software Engineering Principles

General description

This course introduces systematic methods for designing, coding, testing, and documenting medium-sized programs. Major topics include abstraction, modularity, software modeling, object-oriented programming and design, generic programming, and testing and debugging.

Logistics

Audience

  • 2B Software Engineering students

Normally available

  • Spring

Related courses

  • Predecessors: CS 241, Software Engineer students only
  • Successors: CS 457 and most 3rd year CS major courses
  • Co-requisites:
  • Conflicts:

For official details, see the UW calendar.

Software/hardware used

  • UNIX, C++, Java

Typical reference(s)

  • Bruce Eckel, Chuck Allison, Thinking in C++ Volumes 1 and 2, Prentice Hall, 2003

Required preparation

At the start of the course, students should be able to

  • Demonstrate knowledge learned in CS 137/138 and CS 241 by being able to program in C/C++ (structures, strings, procedural abstractions, pointers, addresses, recursion). No knowledge of object-oriented programming is assumed.
  • Explain container Abstract Data Types (lists, stacks, queues, trees) as they were used in CS 138 and CS 241.
  • Write functional specifications (pre / post conditions) as they were used in CS 138.

Learning objectives

At the end of the course, students should be able to

  • Design and implement data abstractions (ADTs, polymorphic objects, generic functions) in C++
  • Critique designs with regards to cohesion, coupling, generality, robustness, information hiding
  • Create software designs that are modular, general, robust, flexible
  • Express software designs and behaviour using basic UML models
  • Express the structure of an OO program as a class model
  • Express the state of a dynamic data structure as an object model
  • Express interactions between objects using a sequence diagram
  • Develop and test programs incrementally
  • Test and debug programs systematically
  • Use simple software tools effectively, including makefiles, gdb, version control

Typical syllabus

Module Design (12 hours)

  • ADT design, function and operator overloading
  • Modules and interfaces
  • Namespaces
  • Interface specification

Object-Oriented Design and Programming (12 hours)

  • Composite objects
  • OO design principles and patterms
  • Multiple inheritance and mixins

Software Engineering and Tools (5 hours)

  • UML modelling
  • Incremental development (make)
  • Testing and debugging (gdb)
  • Version control (e.g., svn)

Generic Programming (5 hours)

  • STL algorithms
  • Iterators
 


CS 251: Computer Organization and Design

General description

This course enables students to develop an accurate mental model of the architecture and organization of physical computers and it introduces them to theoretical and practical concepts relevant to the structure and design of modern digital computers. The course also helps students understand and predict the behaviour and performance of computer programs executing on real machines.

Logistics

Audience

  • 2B Computer Science students
  • Students in the Digital Hardware option should take ECE 222 or 223 instead of CS 251

Normally available

  • Fall, Winter, and Spring

Related courses

  • Predecessors: CS 136, 138, 145 (before Fall 2011), or 146 (imperative programming and the basic memory model)
  • Successors: CS 350, CS 370, CS 450 (and then many upper-year CS courses)
  • Co-requisites: Taking CS 241 along with CS 251 works well
  • Conflicts: Courses that explore the basics of computer hardware

For official details, see the UW calendar.

Typical reference(s)

  • D. Patterson, J. Hennessy, Computer Organization and Design, 5th ed., Morgan Kaufmann, 2014
  • D. M. Harris, S. L. Harris, Digital Design and Computer Architecture, 2nd edition, 2013

Required preparation

At the start of the course, students should be able to

  • Understand the imperative programming model: use array indexing for both read and write (mutable memory model); follow programs written using imperative control flow
  • Use basic algebra, calculus, and probability
    • Algebra is used for combinational design, where Boolean formulas need to be manipulated according to a set of axioms and theorems
    • Calculus is used for some aspects of performance analysis, e.g., limits are taken to predict theoretically obtainable speedup in parallel computers (Amdahl’s law)
    • Basic probability theory is assumed when average-case performance is computed using a weighted average of probabilities, e.g., computing average clocks per instruction, cache-miss penalties, and average disk rotational latencies

Learning objectives

At the end of the course, students should be able to

  • Design simple combinational and sequential hardware at the logic gate level in order to implement simple algorithms and computations, such as addition, multiplication, and data-path control for processors
  • Describe number systems used by computer hardware, including IEEE floating point and two’s complement, at the bit level, including being able to
    • Operate on these number representations and compute their values
    • Explain the limits of these representations, including rounding error and overflow conditions
  • Explain how machine language is executed by hardware, and describe a simple processor architecture for executing a RISC machine language
  • Explain some simple processor implementation optimization techniques, in particular pipelining, and how differences in code ordering can impact performance for processors using these optimizations, including being able to
    • Analyze performance of a code sequence executing on a pipelined architecture
    • Reorganize (given) code in order to improve performance on a pipelined architecture
  • Explain basic cache and virtual-memory architectures, and how they can impact performance, including being able to
    • Analyze a memory-access trace relative to these architectures in order to predict performance
    • Compute average-case performance given miss probabilities and miss penalties
    • Identify specific cases (such as loop index ordering) that can impact performance, and reorganize such code to improve performance
  • Describe a basic multicore and multiprocessor architecture and explain the key factors that will affect performance and scalability of programs written for these architectures

Typical syllabus

Introduction (2 hours)

  • Overview of computer organization
  • Measuring performance

Digital logic design (6 hours)

  • Gates, truth tables, and logic equations
  • Combinational logic and basic components
  • PLAs and ROMs
  • Memory elements
  • Finite-state machines (informally)

Data representation and manipulation (6 hours)

  • Signed and unsigned integer representations
  • Addition and subtraction
  • Using (informal) finite-state machines to control datapaths
  • Multiplication
  • IEEE floating-point representation

Basic processor design (5 hours)

  • Basic processor datapaths
  • Processor design using single-cycle control
  • Processor design using multi-cycle control

Pipelining (5 hours)

  • Pipelined datapaths
  • Data hazards, branch hazards, load-use hazards

Input/Output (3 hours)

  • Buses and bus arbitration
  • Storage (disks)
  • Interrupts
  • Point-to-point (routed) networks
  • Networks and clusters

Memory Hierarchies (3 hours)

  • Caches: direct-mapped, fully-associative, set-associative
  • Virtual memory
  • Page tables and TLBs

Multi-processing (3 hours)

  • Multi-processor systems and core processors
  • Synchronization and locking
  • Cache consistency

CS 341 Algorithms

Watch a video introduction to this course on YouTube.

Objectives

To study efficient algorithms, effective algorithm design techniques and approaches to handling situations in which no feasible algorithms are known. The course is intended to give the student experience in program design and to emphasize both pragmatic and mathematical aspects of program efficiency.

Intended Audience

CS 341 is a required course for all CS major academic plans and is normally completed in a student’s 3B term. A course in algorithms and algorithm design is considered essential for all Computer Science graduates. CS 234 is available for students in other plans and covers a subset of the topics of this course and CS 240.

Related Courses

Prerequisites: CS 240 and (MATH 239 or 249); Computer Science students only.

Antirequisites: SE 240, SYDE 423.

Cross-listed as: CM 339

Successors: CS 466.

References

Introduction to Algorithms, 3rd ed., by T. Cormen, C. Leiserson, R. Rivest, and C. Stein, McGraw-Hill, 2009.

Schedule

3 hours of lectures per week. Normally available in Fall, Winter and Spring.

Notes

  1. Programs and written assignments are an important component of this course.

Outline

Introduction and Analysis of Algorithms (6 hours)

Review of previously encountered algorithm design approaches including divide and conquer. Solution of basic recurrence relations arising in such methods. The notions of average case and worst case behaviours.

Algorithm Design Techniques (15 hours)

A systematic study of design methods including greedy algorithms, dynamic programming, approaches to exploring graphs, backtracking, and branch and bound. Application of these techniques to a variety of problems commonly occurring in practice. Implementation of some examples and discussion of related issues.

Undecidability and Intractability (15 hours)

Algorithmically reducing one problem to another as a means of developing algorithms and proving lower bounds. The undecidability of the halting problem. Proving other problems undecidable via reductions. Reductions between decision and optimization problems. The idea of polynomial time and its independence of many machine models. The classes P and NP and their relationship. Polynomial reducibility and NP-Completeness. A selection of NP-hard problems and proofs of this status.

 

CS 343: Concurrent and Parallel Programming

Watch a video introduction to this course on YouTube.

This course introduces advanced control-structures with an emphasis on concurrency and writing concurrent programs at the programming-language level. Programming techniques and styles are examined to express complex forms of control flow, such as multi-level loop exit, exceptions, coroutines, and concurrency.

Logistics

Audience

  • CS major students planning to do advanced programming
  • Required for SE majors

Normally available

  • Fall and Winter

Related courses

  • Pre-requisites: CS 350 or SE 350

For official details, see the UW calendar.

Software

  • UNIX, C++

Typical reference(s)

  • Course notes

Required preparation

At the start of the course, students should be able to

  • Recognize programs written using iteration and recursion
  • Write advanced imperative programs using arrays and lists for a mutable memory model
  • Use advanced object-oriented programming features in C++ including inheritance, templates, and separate compilation

Learning objectives

At the end of the course, students should be able to

  • Explain complex forms of control flow at a fundamental level
  • Select appropriate forms of control flow for a given problem
  • Synthesize algorithms and use patterns involving multiple threads
  • Compose and debug medium-sized programs involving exceptions, coroutines, and concurrency

Typical syllabus

Advanced control flow (3 hours)

  • Multi-exit loops, multi-level exits, exceptions (termination/resumption)

Coroutines (4 hours)

  • Multiple stacks, context switching
  • Semi and full coroutines

Concurrency (3 hours)

  • Threading models, concurrent systems, speedup
  • Ready queue, thread states, interrupts
  • Start, synchronize, and communicate among threads

Mutual exclusion (4 hours)

  • Software and hardware solutions for critical sections
  • Atomic data structures

Locks (4 hours)

  • Spinning and blocking locks and implementations
  • Basic lock, binary and counting semaphore, barrier
  • Lock programming: baton passing and split binary semaphores
  • Bounded buffer and readers/writer problems

Concurrency errors (3 hours)

  • Race condition, starvation, live-lock, synchronization and mutual exclusion deadlock
  • Examine deadlock prevention, avoidance and recovery

High-level concurrency (8 hours)

  • Conditional critical regions, monitors, tasks
  • Internal and external synchronization in mutex objects
  • Rendezvous, futures and client/server

Other concurrency approaches (3 hours)

  • Concurrent programming languages: Ada, Java, Go, Actors, Linda, OpenMP, pthreads, C++11

Optimization (2 hours)

  • Sequential and concurrent execution models
  • Corruption: memory, cache, registers, execution order

Distributed environments (2 hours)

  • Distributed communication: sockets
  • Message-passing, MPI
  • Remote procedure/method call
  1. Cheriton School of Computer Science 
 
 

CS 348 | SCS | UW

Revised March 3, 2015

CS 348: Introduction to Database Management

Watch a video introduction to this course on YouTube.

General description

This course covers the basic concepts and elements of database management by providing a “classic” introduction to the relational data model and its languages. The course also covers database design methodology.

Students gain experience using and building applications on top of a state-of-the-art commercial DMBS by completing several assignments. Students also gain hands-on experience with commercial database management systems (DBMS) by writing application programs using the commercial DBMS query languages. The main course topics are data models, architecture of database systems, data definition and manipulation languages, database design methods, and the theory of data dependencies and relational normalization.

Logistics

Audience

  • CS major students

Normally available

  • Fall, Winter, and Spring

Related courses

  • Pre-requisites: SE 240 or CS 240
  • Successors:
  • Anti-requisites: CS 338, CS 448, ECE 456

For official details, see the UW calendar.

Software/hardware used

  • A database management system, currently DB2 on Linux labs

Typical reference(s)

  • Database System Concepts, 6th edition, Avi Silberschatz, Henry F. Korth, and S. Sudarshan (required)
  • Database Management Systems, 3rd ed., Ramakrishnan & Gehrke, (optional)

Required preparation

At the start of the course, students should be able to

  • Program using a high-level programming language, such as C/C++/Java
  • Demonstrate a fundamental understanding of data structures

Learning objectives

At the end of the course, students should be able to

  • Explain the principles of relational database management systems
  • Develop data models by constructing Entity-Relationship models from specifications and map them to relational tables in Boyce-Codd Normal Form
  • Interact with database management systems by means of their languages (in particular SQL), and other interfaces, such as ODBC and JDBC
  • Use and build database application programs

Typical syllabus

Introduction (2 hours)

  • Data as a fundamental asset and what it means to manage persistent data
  • Differences between file management and database management in terms of functionality and interface

Relational database systems (6 hours)

  • Fundamentals of relational databases, relational calculus, relational algebra, integrity issues

Database design (7 hours)

  • Database design methodology
  • Logical data modeling by Entity-Relationship modeling, mapping ER models to relational models, relationship to UML models
  • Normalization of relational schema

SQL and interfaces (7 hours)

  • SQL DDL, SQL DML, QBE

Database application development (5 hours)

  • Embedded SQL, concept of transactions, principles of access granularity, ODBC, JDBC

Database tuning (3 hours)

  • Database indexes, role of indexes in efficient database application development

Database administration (3 hours)

  • Views and view management
  • Database security and authorization

Current topics (6 hours)

  • Distributed databases, data warehouses, data mining
 
 

CS 349: User Interfaces

Watch a video introduction to this course on YouTube.

General description

This course introduces contemporary user interfaces, including the basics of human-computer interaction, the user interface design/evaluation process, and the architectures within which user interfaces are developed. Students implement and evaluate portions of typical user interfaces in a series of programming assignments.

Logistics

Audience

  • CS major students interested in modern user interfaces

Normally available

  • Fall, Winter, and Spring

Related courses

  • Predecessors: CS 241 and (MATH 115 or 136/146)
  • Successors: CS 449

For official details, see the UW calendar.

Software/hardware used

  • C++
  • Java
  • Linux
  • Virtual machines (such as VirtualBox)

Typical reference(s)

  • D. Olsen, Building Interactive Systems, Course Technology, 2009

Required preparation

At the start of the course, students should be able to

  • Develop object-oriented software in languages such as C++

Learning objectives

At the end of the course, students should be able to

  • Design, implement, and test interfaces for a variety of targets, such as Android, Java (e.g., with Java Swing), or X Windows

Typical syllabus

Event architecture (4 hours)

  • Abstractions for user input focusing on the event abstraction
  • Lowest level user interface control structure (the event loop with message passing)

Design patterns (4 hours)

  • Model-view-controller and related design patterns for designing user interface architectures

Components and interactor trees (4 hours)

  • How interfaces are constructed from components
  • Construction of an interface from interacting components

Algorithms for user interaction (4 hours)

  • Design and implementation of algorithms for interactive systems to handle undo, layout, multithreading, and data transfer (e.g., clipboard, drag-and-drop)

2D graphics (4 hours)

  • 2D graphics algorithms for rendering and interaction with graphics and text

People and the human-machine interface (6 hours)

  • Theory and methods for designing interfaces to match human abilities and needs (specific topics include perception, visual design (e.g., Gestalt principles), input and output devices, accessibility, and internationalization)

UI specification (4 hours)

  • Methods for specifying the visual and interaction design of user interfaces

Special topics (6 hours)

  • Past, present, and future of interactive computing and implications for the design and implementation of user interfaces
  • Design for specific platforms (e.g., mobile, web), touch and multitouch interaction, and scripting facilities

CS 350: Operating Systems

General description

This course introduces operating systems, what they do, how they are used, and how they are implemented.

Logistics

Audience

  • 3A or 3B CS major students

Normally available

  • Fall, Winter, and Spring

Related courses

  • Pre-requisites: CS 240, 241, 246, (CS 251 or ECE 222)
  • Successors: CS 343 and many of the 4th year CS major courses
  • Anti-requisites: ECE 254, MTE 241, SE 350

For official details, see the UW calendar.

Software/hardware used

  • C programming language

Typical reference(s)

  • Operating Systems: Three Easy Pieces, Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau, Arpaci-Dusseau Books, 2014

Required preparation

At the start of the course, students should be able to

  • Use sequential programming skills
  • Understand computer organization
  • Write, test, and debug programs of a moderate size

Learning objectives

At the end of the course, students should be able to

  • Extend complex programs written by others
  • Choose appropriate data structures and algorithms to solve a variety of programming problems
  • Select and use suitable editors and development environments (to some extent) and use the tools provided as part of the programming process
  • Test if a program runs properly and correct faults by debugging
  • Explain the main components of modern operating systems and construct simple implementations of those components
  • Produce prose of a technical nature
  • Demonstrate awareness of fundamental trade-offs in algorithm design, including time versus space
  • Create correct concurrent programs of moderate complexity
  • Explain the concepts of threads and processes and address spaces
  • Describe memory management (as related to operating systems) and virtual memory
  • Discuss issues related to processor scheduling
  • Explain how file systems work and how they interact with disk drives
  • Describe how operating systems work and how applications interact with devices
  • Explain how processes can communicate within the same machine

Typical syllabus

Operating system introduction (2 hours)

  • Roles of an operating system
  • Three views of an operating system (application, system, and implementation)
  • Operating system interaction with devices

Multi-programming (7 hours)

  • Processes and threads, system calls, context switching
  • Managing processor time
  • Types of scheduling, scheduling algorithms

Concurrency (6 hours)

  • Principles of concurrency
  • Mutual exclusion and semaphores
  • Deadlock detection and prevention

Memory management (8 hours)

  • Virtual addressing and address translation
  • Principal of locality, spatial locality, and temporal locality
  • Virtual memory management: segmentation, paging, caching strategies
  • Load control, swapping, and thrashing

Device management (3 hours)

  • Physical structure and properties of devices
  • Device control and interaction, blocking, buffering, disk scheduling, DMA

File systems (5 hours)

  • File naming, types, and logical organization
  • Space allocation and management
  • File system interfaces
  • Implementation strategies

Interprocess communication (5 hours)

  • Terminology and issues
  • Message passing functionality, pipes, sockets, signals, shared memory, and other communication mechanisms

CS 360 Introduction to the Theory of Computing

Watch a video introduction to this course on YouTube.

General description

This course introduces the theoretical foundations of Computer Science.

Logistics

Audience

  • CS major students and especially students interested in graduate school

Normally available

  • Fall, Winter, and Spring

Related courses

  • Pre-requisites: CS 240 or SE 240, CS 241, MATH 239/249 or CO 103, CS 245 or SE 112/212
  • Successors: CS 462
  • Anti-requisites: CS 365

For official details, see the UW calendar.

Software/hardware used

  • None

Typical reference(s)

  • Introduction to Automata Theory Languages & Computation, 3rd ed., Hopcroft, Motwani, & Ullman, Prentice Hall, 2009

Required preparation

At the start of the course, students should be able to

  • Describe what a proof is
  • Create proofs by induction

Learning objectives

At the end of the course, students should be able to

  • Describe how a real computer can be modeled mathematically by a theoretical computer in many different ways
  • Explain what a formal language is and how it corresponds to a computational decision problem
  • Describe regular languages in two different ways (automata and regular expressions)
  • Describe context-free languages in two different ways (grammars and pushdown automata)
  • Prove languages regular and non-regular, context-free and non-context-free, recursive and non-recursive, recursively enumerable and non-r.e.
  • Describe the Church-Turing thesis
  • Explain what nondeterminism is and how it is used
  • Explain what a Turing machine is and create simple Turing machines to solve problems
  • Describe the fundamental limits to computation (computable versus uncomputable)

Typical syllabus

Finite automata (10 hours)

  • Deterministic and non-deterministic finite automata and their equivalence
  • Equivalence with regular expressions
  • Closure properties
  • Pumping lemma and applications

Context-free grammars (10 hours)

  • Definitions
  • Parse trees
  • Pumping lemma for CFLs and applications
  • Normal forms
  • Sketch of equivalence with pushdown automata

Turing machines (9 hours)

  • Designing simple TMs
  • Variations in the basic model (multi-tape, multi-head, non-determinism)
  • Church-Turing thesis and evidence to support it through the study of other models

Undecidability (7 hours)

  • Undecidability of the halting problem
  • Reductions to other problems
  • Reduction in general
 
 

CS 370: Numerical Computation

Watch a video introduction to the course on YouTube.

General description

This course introduces students to the basic algorithms, software environments, and applications of scientific computing. Simple but realistic examples are used to motivate the study of numerical methods.

Logistics

Audience

  • CS major students and students pursuing a CS minor
  • Students interested in a career in computational support of engineering or scientific applications, such as CAD/CAM, graphics, or finance

Normally available

  • Fall, Winter, and Spring

Related courses

  • Predecessors: (One of MATH 118, 119, 128, 138, 148), (One of MATH 114, 115, 106/125, 136, 146), (One of CS 234, 241, 246); Not open to General Mathematics students
  • Successors: CS 475, 476
  • Anti-requisites: AMATH 242/341/CM 271/CS 371, CS 335, 337, ECE 204, 304

For official details, see the UW calendar.

Software/hardware used

  • MATLAB

Typical reference(s)

  • Numerical Computing with MATLAB, Cleve Moler, SIAM, 2004
  • Course notes

Required preparation

At the start of the course, students should be able to

  • Program in a high-procedural programming language and use control instructions, such as loops and conditional statements, basic datatypes, and simple data structures, such as arrays
  • Perform basic mathematical computations and have knowledge of
    • limits and derivatives, Taylor series, curves, and other basic concepts encountered in calculus
    • matrix operations, inverse, products, Gaussian elimination
    • complex arithmetic and trigonometric functions

Learning objectives

At the end of the course, students should be able to

  • Explain the principles of floating point number systems and the concepts of chopping, rounding, machine precision, and error of floating point arithmetic
  • Analyze stability and conditioning of simple numerical problems
  • Use MATLAB built-in functions and graphing capabilities of 1D and 2D data
  • Implement efficient code using vectorization
  • Compute polynomial and spline interpolants and apply splines to curve drawing in two and three dimensions
  • Use numerical algorithms to solve ordinary differential equations and understand and apply methods to analyze the stability and efficiency of these methods
  • Design simple procedures using FFT based algorithms for applications, such as signal and image processing and data compression
  • Solve linear equations in a floating point environment taking into consideration error propagation and measures of conditioning
  • Give examples of the issues involved in a large scale linear algebra computation (e.g., Google Page Rank)

Typical syllabus

Floating point numbers (3 hours)

  • Floating point numbers, propagation of round off, stability of recursions

Interpolation (6 hours)

  • Interpolation: Vandermonde matrix, Lagrange interpolation, cubic splines, B splines
  • Example application: scalable fonts

Ordinary differential equations (9 hours)

  • Forward, backward, modified Euler, local truncation error, stability, global error
  • Example application: pursuit problems, SIR disease propagation model

Discrete Fourier analysis (9 hours)

  • Fourier series, FFT algorithm (butterfly)
  • Example application: JPEG, image and signal processing, MP-3

Numerical linear algebra (9 hours)

  • LU decomposition, pivoting, condition number, QR decomposition
  • Example application: Google Page Rank
 
 

CS 371: Introduction to Computational Mathematics

Watch a video introduction to the course on YouTube.

General description

This course introduces computational mathematics through an in-depth study of the properties of numerical algorithms.

Logistics

Audience

  • CS major students and students pursuing a CS minor
  • Students interested in both mathematics and computer science and interested in the computational aspects that one would encounter when solving various mathematical or scientific problems

Normally available

  • Winter and Spring

Related courses

  • Predecessors: (One of CS 116, 134, 136, 138, 145 taken fall 2010 or earlier, CS 146), MATH 235 or 245, 237, or 247; Not open to General Mathematics students
  • Successors: CS 473, 475, 476
  • Anti-requisites: CS 335, 337, 370, ECE 204
  • Conflicts: AMATH 242/341, CM 271

CS 371 may be substituted for CS 370 in any degree plan or for prerequisite purposes

For official details, see the UW calendar.

Software/hardware used

  • MATLAB

Typical reference(s)

  • Numerical Analysis, 9th ed., R. Burden and J. Faires, Brooks Cole
  • Course notes

Required preparation

At the start of the course, students should be able to

  • Program in a high-procedural programming language and use control instructions, such as loops and conditional statements, basic datatypes, and simple data structures, such as arrays
  • Use limits and derivatives, Taylor series, curves, max/min of multivariate functions, partial derivatives, other basic concepts encountered in calculus, and multi-dimensional integration
  • Use matrix operations, inverse, products, etc., Gaussian elimination, eigenvalues, and eigenvectors

Learning objectives

  • Explain the principles of floating point number systems and the concepts of chopping, rounding, machine precision, and error of floating point arithmetic
  • Analyze stability and conditioning of numerical problems
  • Solve nonlinear equations using iterative methods and analyze convergence of various methods
  • Use MATLAB built-in functions and graphing capabilities of 1D and 2D data
  • Implement efficient code using vectorization
  • Use the principles of polynomial interpolation to derive and apply splines
  • Use numerical methods to integrate one dimensional functions and analyze the efficiency of these methods
  • Give examples of the concept of data representation using different basis functions, Fourier basis, and the FFT algorithm
  • Use alternate representations in applications, such as tomographic reconstruction and filtering
  • Solve linear equations in a floating point environment taking into consideration error propagation and measures of conditioning
  • Explain the computational and mathematical issues involved in a large scale linear algebra problem (e.g., sparse matrix solving)

Typical syllabus

Floating point number systems (3 hours)

  • Floating point numbers, propagation of round off, stability of recursions

Polynomial interpolation (4 hours)

  • Interpolation: Lagrange and cubic spline

Nonlinear equations (4 hours)

  • Fixed point, Newton iteration Analysis of convergence, rate of convergence

Numerical linear algebra (11 hours)

  • LU decomposition, pivoting, condition number, sparse matrices, iterative methods, analysis of convergence of iterative methods, power method for eigenvectors, Google Page Rank, analysis of convergence of the power method, sparse matrices and graphs

Discrete Fourier analysis (11 hours)

  • DFT pair, sampling theorem, aliasing, FFT algorithm, slice theorem, Radon Transformation, filtered backprojection for CT image reconstruction

Numerical integration (3 hours)

  • Midpoint, trapezoidal, Simpson’s rule, error analysis, Gaussian quadrature, Monte Carlo

CS 436: Networks and Distributed Computer Systems

General Description

An introduction to principles, algorithms, protocols, and technology standards used in computer networks and distributed systems. Specific topics include resource management, naming and routing, and reliability.

Logistics

Intended for 3rd- or 4th-year students with an interest in Computer Science. Not open to Computer Science students. Normally available Winter.

Related courses (see calendar for official details)

Predecessors: One of CS 230, 241, 246 or 251; not open to Computer Science students.

Conflicts: CS 454, 456, ECE 428, 454.

Hardware/Software used: UNIX, any programming language.

Typical References

James F. Kurose and Keith W. Ross, Computer Networking: A Top-Down Approach,Addison-Wesley.
Andrew S. Tanenbaum and Maarten Van Steen. Distributed Systems: Principles and Paradigms, Prentice Hall.

Required preparation

At the start of the course, students should have the ability to

  • Use basic algebra, calculus, and probability (for performance analysis).
  • Write simple imperative programs using lists, iteration, and array indexing for both read and write (mutable memory model).
  • Describe data representations used by computer hardware at the bit level, operate on these representations, and compute their values.
  • Explain the basic build process for computer software.
  • Compare basic memory and I/O architectures, and how they can impact performance.
  • Exemplify basic functionality and components of an operating system.

Learning objectives

At the end of the course, students should have the ability to:

  • Recall, explain, and compare transmission media and access control schemes.
  • Recall, explain, and compare addressing and message forwarding paradigms, including path computation.
  • Recall, summarize, and exemplify connection management and reliable message transmission.
  • Recall, explain, and compare naming and name resolution techniques, including mobility.
  • Recall, summarize, and exemplify contemporary network protocols and techniques.
  • Recall, summarize, and explain security/privacy concepts in network protocols and distributed systems
  • Recall, explain, and compare high-level communication services and distribution services.
  • Compare how existing distributed applications utilize services.

Typical syllabus

Physical and data link layer (6 hours)

media types, encoding, error correction, medium access control

Network layer (6 hours)

hierarchical addressing, forwarding, routing algorithms

Transport layer (6 hours)

reliable data transfer, connection management, rate control

Naming and mobility (3 hours)

indirect naming, name resolution, transparency, handover

High-level services (6 hours)

RPC, message queueing, clocks & synchronization, replication

Security and Privacy (3 hours)

confidentiality, integrity, availability

Operations and applications (3 hours)

email, web, multimedia

 

CS 442: Principles of Programming Languages

Watch a video introduction to this course on YouTube.

General description

This course examines foundational issues in contemporary programming languages, including abstraction mechanisms, operational semantics, type systems, and extensibility.

Logistics

Audience

  • Fourth year CS majors

Normally available

  • Winter

Related courses

  • Pre-requisites: CS 240; Computer Science students only

For official details, see the UW calendar.

Software/hardware used

  • Standard UNIX environment with open-source language interpreters and compilers

Typical reference(s)

  • B. Pierce, Types and Programming Languages, The MIT Press, 2002

Required preparation

At the start of the course, students should be able to

  • Write efficient, readable programs from scratch, in several programming languages, that manipulate standard data structures (e.g., lists, trees)
  • Reason about the correctness and efficiency of such programs
  • Prove theorems about discrete mathematical structures (e.g., functions, relations, the natural numbers) using standard techniques (e.g., contradiction, induction)

Learning objectives

At the end of the course, students should be able to

  • Write efficient, readable programs from scratch in several new programming languages
  • Define and implement (via interpreters written in these new programming languages) operational semantics for extensions of the lambda calculus distilling features from said languages
  • Define typing rules for these extensions compatible with the type systems provided by said languages and implement type checking and type inference algorithms based on these rules
  • State and prove relevant theorems (e.g., progress, preservation) about type systems

Typical syllabus

Untyped lambda calculus and dynamically-typed languages (9 hours)

  • Grammar and reduction rules
  • Binding, scope, and substitution
  • Reduction strategies (eager vs. lazy evaluation)
  • Confluence and normalization
  • Simulating common programming language features (Booleans, natural numbers, lists, recursion)
  • Programming languages based on untyped lambda calculus (e.g., Lisp, Scheme, Racket)
  • Techniques for efficient interpreters (environments, closures, stores)

Typed lambda calculus and statically-typed languages (9 hours)

  • Typing rules and type-checking algorithms
  • Strong normalization and its implications
  • Recovering expressibility through extensions
  • Progress and preservation theorems
  • Type inference algorithms
  • Programming languages based on typed lambda calculus (e.g. SML, OCaml, Haskell)

Polymorphism (9 hours)

  • Types of polymorphism
  • Parametric polymorphism and its use in ML
  • System F
  • Higher-kinded polymorphism and its use in Haskell

Other topics (9 hours)

Topics chosen by the instructor to extend and/or complement the above. Possible choices include, but are not limited to:

  • Metaprogramming (e.g., macros)
  • Non-standard flow of control (e.g., continuations)
  • Object-oriented programming
  • Logic programming
  • Recursive types
  • Existential types and modules
  • Dependent types and certified programming
 
 

 

CS 445: Software Requirements Specification and Analysis

Watch a video introduction to this course on YouTube.

General description

This course introduces students to the requirements definition phase of software development. It discusses processes, models, and notations, and processes for software requirements elicitation, identification, analysis, modeling, representation, specification, and validation. An important component is a group project: the software requirements specification of a large software system.

Logistics

Audience

  • CS major students, usually taken in the second term of third year. This course benefits students with an interest in software engineering, software development, and development of large software systems.

Normally available

  • Fall and Winter

Related courses

  • Prerequisites: CS 350; Computer Science students only
  • Antirequisites: SE 463
  • Related courses: CS 446, CS 447
  • Cross-listed as: CS 645, ECE 451

For official details, see the UW calendar.

Software/hardware used

  • MagicDraw
  • Word processor, such as MS Word or LaTeX

Typical reference(s)

  • Requirement Engineering, A. van Lamsweerde, Wiley; Applying UML and Patterns, 2nd ed., C. Larman, Prentice Hall
  • UML Distilled, 2nd ed., M. Fowler, Addison-Wesley
  • Requirements Analysis and Systems Design, L. Maciaszek, Addison-Wesley
  • Mastering the Requirements Process, S. Robertson and J. Robertson, Addison-Wesley
  • Exploring Requirements: Quality Before Decision, D. Gause and G. Weinberg, Dorset House
  • Managing Software Requirements, A Unified Approach, D. Leffingwell and D. Widrig, Addison Wesley

Required preparation

At the start of the course, students should be able to

  • Write programs

Learning objectives

At the end of the course, students should be able to

  • Elicit, identify, analyze, model, represent, specify, and validate requirements for a software-intensive system to be built
  • Divide the world in which a software-intensive system sits into the system to be built, its environment, and the interface between the system and the environment
  • Write a domain model and a use case model for a software-intensive system
  • Write a user’s manual and a software requirements specification (SRS) for a software-intensive system

Typical syllabus

Introduction (3 hours)

  • Overview of the software development process and life cycle models. Requirements: identification, representation, validation, analysis; related standards and CASE tools.

Software development groups (3 hours)

  • Project discussion, including group management, member duties and group dynamics.

Requirements elicitation (2 hours)

  • Methods for obtaining requirements from various sources.

Informal notations for behavioural requirements (10 hours)

  • Overview of notations and presentation of case studies: entity relationship models, data flow diagrams and structured analysis, SDL, and UML.

Formal notations for behavioural requirements (6 hours)

  • Classification of requirements specification notations; relationship to application characteristics. Specification of control, functional, and data requirements.

Non-behavioural requirements (2 hours)

  • Specification of maintainability, safety, reliability, performance, etc.

Requirements validation (5 hours)

  • Methods for validating a requirements specification: active reviews, scenarios and threads, executable specifications, automated analysis, formal verification.

Cost estimation (3 hours)

  • Estimating duration and cost of project: CPM graphs, Gantt charts, milestones, algorithmic cost models, expert judgement, Delphi estimates.

Other topics (2 hours)

  • Relationship between requirements and design specifications; estimation of resources, cost, and schedules for a large software project.
 
 

 

CS 446 Software Design and Architectures

Watch a video introduction to this course on YouTube.

Objectives

To introduce students to the software design process and its models. Representations of design/architecture. Software architectures and design plans. Design methods. Design state assessment. Design quality assurance. Design verification. Group design and implementation of an application.

Intended Audience

CS 446 is a course for CS major students and is normally taken in a student’s 4A term. This course is one of three that form the basis for the software engineering option. This option will be for students specializing in the development of large software systems. Students from other plans in Computer Science may elect to enrol in this course.

Related Courses

Prerequisites: CS 350; Computer Science students only.

Antirequisites: CS 430, SE 464.

Related courses: CS 445, CS 447.

Cross-listed as: ECE 452.

Hardware/Software

Used in Course: C/C++, Tcl/Tk.

Assumed Background: UNIX, SDT, Rose, C/C++. Familiarity with graphical user interface tools would be an asset.

References

Schedule

3 lecture hours, 1 tutorial hour, and 1 discussion hour (for project group meetings). Normally available in Winter and Spring.

Outline

Introduction (1 hour)

Why design? Input, output, and constraints of the design process. Types of design. Relationship to software quality and evolution. Design in more mature implementation technologies.

Software Design Process Models (3 hours)

Design as search. Design spaces. Design state, goal structure, generative design operations, early quantitative evaluations, control of design process. Basic models of design (transformational, plan/architecture driven). Relationship to other life-cycle activities.

Architecture/Design Representations (9 hours)

What should be represented (structure, behaviour)? Informal representations of design, examples of design notations. Formal representation of design. Domain specific architecture descriptions. Role of standards, reference architectures. Design documentation.

Design Plans/Architecture (9 hours)

Review of small/medium scale plans (data structures, programming language structures, concurrency). Plans/architectures for common types of software systems (translators, embedded, real-time, user interface).

Design Strategies and Methods (6 hours)

Design strategies. Selected methods: object modeling technique, structured design, real-time, user interfaces. Methods for design with off-the-shelf components.

Design Assessment (3 hours)

Assessment dimensions and factors affecting their relative importance. Design tradeoffs. Evolvability/understandability criteria. Design complexity metrics. Assessment strategies (analytical, simulation, rapid prototyping), example: response time/throughput estimation.

Design Quality Assurance and Verification (3 hours)

Design reviews, scenarios and test cases, testing of executable design representations. Verification of properties.

 

 

CS 447 Software Testing, Quality Assurance, and Maintenance

Objectives

To introduce students to systematic testing of software systems, software verification, symbolic execution, software debugging, quality assurance, measurement and prediction of software reliability, project management, software maintenance, software reuse, reverse engineering.

Intended Audience

CS 447 is a course for CS major students, and is normally taken in a student’s 4B term. This course is one of three that form the basis for the software engineering option. Students from other plans in Computer Science may elect to enrol in this course.

Related Courses

Prerequisites: CS 350; Computer Science students only.

Antirequisites: SE 465.

Related courses: CS 445, CS 447.

Cross-listed as: ECE 453.

Hardware/Software

Used in Course: Rational Rose, SDL, X-Runner, ITEX.

Assumed Background: Strong familiarity with UNIX, C/C++ and Tcl/Tk.

References

Software Testing, by Paul C. Jorgensen, CRC Press, 1995. Course notes.

Schedule

3 lecture hours, 1 tutorial hour, and 1 discussion hour (for project group meetings). Normally available in Winter.

Notes

  1. The Course Project builds on CS 446.

Outline

Introduction (2 hours)

Overview of the maintenance and testing activities within the software life cycle. Brief introduction to project related CASE tools and necessary background.

Software Maintenance (12 hours)

Major maintenance activities. Estimating maintenance costs and productivity. Predicting maintainability with software quality metrics. Economics and expectations of software reengineering. Principles of software reuse and reverse engineering techniques.

Project Management (3 hours)

Cost estimation. Project scheduling. Specification of work units.

Quality Assurance (4 hours)

Introduction, examination of various quality/complexity metrics. Software availability. Measurement and prediction of software reliability.

Non-execution based testing (5 hours)

Software verification, correctness proofs, symbolic execution, walkthroughs, inspections.

Testing in the Small (5 hours)

Testing strategies, including unit level, path and dataflow testing, domain testing, decision tables, and state-based testing. Coverage metrics. Impact of object-oriented testing. Effort, efficiency, and effectiveness concerns.

Testing in the Large (5 hours)

Integration (decomposition based, bottom-up, top-down, call graph based, path based, MM paths and atomic system functions). Validation and system testing (data, action, port, event and thread testing, structural and functional approaches, operational profiles). TTCN test suites.

 

CS 448 Database Systems Implementation

Watch a video introduction to this course on YouTube.

Objectives

The objective of this course is to introduce students to fundamentals of building a database management system (DBMS), in particular a relational one. It focuses on the database engine core technology by studying topics such as storage systems (data layout, disk-based data structures), indexing, query processing algorithms, query optimization, transactional concurrency control, logging and recovery. It complements CS348 by looking at the internals of relational DBMSs.

Intended Audience

This is a second course on databases that focuses on DBMS internals. It is a project-oriented course that will provide the students, upon successful completion, with an appreciation of the intricacies and complexities of a DBMS and enable them to be able to design and implement the major components of it. The course objective will be achieved by focusing on three fundamental sub-objectives:

  1. To understand the fundamentals of storage systems and disk-based data structures;
  2. To understand the process of query processing and optimization; and
  3. To learn the implementation of transactions.

Complementary to the above objectives, the course has a training component where the students will gain experience, within the context of a number of assignments, in building components of a DBMS and incorporating them into an open source system such as MySQL or PostgreSQL. The lectures may be complemented by guest lectures on real-life DBMS implementation issues given by colleagues from industry (Sybase, IBM Canada, Microsoft and others).

CS 448 is a course for CS major students, and is normally taken in a student’s fourth year. This course will be of interest to students whose area of expertise includes large software systems. CS 338 is available for students in other plans.

Related Courses

Prerequisites: CS 348 and (CS 350 or SE 350). Computer Science students only.

References

Database Management Systems, 3rd ed., by R. Ramakrishnan and J. Gehrke, McGraw-Hill, 2003. Course notes are required (may be made available via the web).

Schedule

3 hours of lectures per week. Normally available in Winter.

Outline

Review of relational database systems (3 hours)

Fundamentals of relational databases, relational calculus, relational algebra, integrity issues.

Storage Management (9 hours)

Data layout, buffer systems, file management, indexing techniques (tree-based and hashing).

Query Processing and Optimization (13 hours)

Query processing methodology, view expansion, query translation, implementation of relational operators, external sorting, cost-based query optimization.

Transaction Management (12 hours)

Transaction models, concurrency control algorithms, database recovery.

Meta-data Management (2 hours)

Implementation of catalogs and integrity constraints.

 

CS 449: Human Computer Interaction

Watch a video introduction to this course on YouTube.

Goals

Human-Computer Interaction teaches the fundamental issues that underlie the creation and evaluation of usable and useful computational artifacts. Over the term, students will learn how to design novel computational artifacts that enable a well-defined user group to achieve specific goals more effectively than via current means. More specifically, students will learn and directly apply:

  • Rapid ethnography and contextual design techniques to identify a well-defined user group’s needs
  • Rapid, user-centered design techniques, including low-fidelity, high-iteration prototyping practices (e.g., paper-based prototyping and Wizard-of-Oz studies)
  • Evaluation methods for measuring how a design compares to existing methods of accomplishing a task.

Students will also be introduced to major threads of HCI research.

Logistics

Related courses
Prerequisites: CS 240 241; Level at least 3B; Computer Science students only.
Successors: CS 349
Conflicts: SYDE 348
Calendar description
Hardware/software used: N/A.

Typical references:
Contextual Design, by Beyer and Holtzblatt
Interaction Design, by Preece, Rogers, and Sharp
Human-Computer Interaction, by Dix, Finley, Abowd and Beale
Designing the User Interface: Strategies for Effective Human-Computer Interaction, by Shneiderman and Plaisant

Required Preparation

The primary requirement for this course is experience in school, managing projects, and working. In particular, time management and communication skills (written, oral, and visual) are essential for success in this course. Thus, students with 3+ years of experience with courses at Waterloo (especially project-based courses), and experience with co-op positions, should fare well.

Learning Objectives

By the end of the course, students should have the ability to:

  • Conduct in-situ interviews and observations of end-users
  • Analyze qualitative data to produce models of users and their work practices
  • Use rapid prototyping practices to design novel computational artifacts, where the designs may be situated in traditional desktop computing contexts and/or off-the-desktop computing paradigms (e.g., mobile computing, wall-based displays, tabletop systems, etc.)
  • Evaluate their designs using expert evaluation techniques (e.g., cognitive walkthroughs), experimental methods, and/or discount evaluation methods (e.g., heuristic evaluation, Wizard-of-Oz evaluation)
  • Describe current trends in HCI research

Typical Syllabus

  1. Introduction to, and history of, HCI
    Hours: 3
    Goals:
  • Ability to identify the primary luminaries relevant to HCI, as well as their visions (e.g., Vannevar Bush and his Memex; Ivan Sutherland and the Sketchpad; Douglas Engelbart and his system for augmenting human intelligence)
  • Articulate the primary concerns of HCI practitioners: Understanding users and their needs within a sociocultural context; design; prototyping; and evaluation
  1. Data gathering
    Hours: 6
    Goals:
  • Describe the human rights and ethics issues in doing work with human subjects; know how to obtain informed consent; know when institutional approval is needed for human subjects research
  • Articulate the strengths and weaknesses of both quantitative and qualitative methods of describing humans and human activity
  • Ability to plan and conduct semi-structured interviews using common practices of qualitative researchers
  • Ability to plan and conduct in-situ observations
  1. Data analysis
    Hours: 6
    Goals:
  • Ability to convert data collected from field studies into one or more of Contextual Design’s five models (flow, sequence, artifact, cultural, physical)
  • Ability to develop and apply coding schemes to qualitative data
  • Ability to extract, and articulate, design requirements from collected data
  1. Design and prototyping
    Hours: 9
    Goals:
  • Ability to differentiate between interaction design, interface design, and interface element design
  • Ability to create both horizontal and vertical designs
  • Ability to create low-fidelity, interactive prototypes using techniques such as paper-prototyping, storyboarding, role-playing, and video prototyping
  • Ability to hold and participate in design critiques
  1. Evaluation
    Hours: 6
    Goals:
  • Describe the differences, relative merits of quantitative vs. qualitative, naturalistic vs. experimental evaluations
  • Ability to form and execute an evaluation plan, identifying specific measures and goals of the evaluation
  • Ability to apply discount usability evaluations to interface designs and prototypes, functioning applications, including Wizard-of-Oz prototyping and heuristic evaluation
  • Articulate elements of good experimental design
  1. Topics in HCI research
    Hours: 6
    Goals:
  • Ability to identify major movements in HCI research, and their motivations, philosophies, and goals
  • Articulate the current state of an area well enough to know what has been tried, what has been successful, what hasn’t, and why. For example: Speech interfaces, their limitations and successes
 
 

CS 450: Computer Architecture

Watch a video introduction to this course on YouTube.

General description

This course provides students with an appreciation of modern computer design and its relation to system architecture, compiler technology, and operating system functionality. The course focuses on design that is based on the measurement of performance and its dependency on parallelism, efficiency, latency, and resource utilization.

Logistics

Audience

  • CS major students. Mostly taken in fourth year. Students who are interested in computer hardware or work with logic designers to specify application specific processors will find this course valuable.

Normally available

  • Winter

Related courses

  • Pre-requisites: (CS 245 or SE 212) and (CS 350 or ECE 354 or MTE 241 or SE 350); Computer Science students only
  • Anti-requisites: ECE 429

For official details, see the UW calendar.

Software/hardware used

  • UNIX, Verilog Simulator

Typical reference(s)

  • M. Dubois, M. Annavaram, and P. Stenström, Parallel Computer Organization and Design, Cambridge Press, 2012
  • Course notes

Required preparation

At the start of the course, students should be able to

  • Describe a simple processor architecture for executing a RISC machine language
  • Explain basic cache and virtual-memory architectures, and how they can impact performance

Learning objectives

At the end of the course, students should be able to

  • Code a simulatable specification for a simple multi-cycle processor
  • Explain the structure of statically and dynamically scheduled pipelines
  • Evaluate the performance of software executed on statically and dynamically superscalar pipelines
  • Appreciate use and limits of instruction-level, data-level, and thread-level parallelism
  • Describe memory coherency and consistency protocols

Typical syllabus

Digital hardware design (6 hours)

  • Transistors, digital logic, hardware description languages

Instruction set architecture (3 hours)

  • Instruction types and mixes, addressing, RISC vs CISC, exceptions, Flynn’s taxonomy

Scalar pipelines (3 hours)

  • Data dependencies, local and global scheduling, performance

VLIW pipelines (6 hours)

  • Local scheduling, loop unrolling, software pipelining, trace scheduling, data speculation, deferred exceptions, predicated execution, IA64

Dynamic pipelines (9 hours)

  • Dynamic scheduling, register renaming, speculative loads, prefetching, speculative execution, trace caches

Thread-level parallelism (6 hours)

Multiprocessors, synchronization, cache coherency, memory consistency, chip multiprocessors, simultaneous multithreading, transactional memory

Data-level parallelism (2 hours)

  • GPGPU structure and programming models
 
 

CS 452: Real-Time Programming

Watch a video introduction to this course on YouTube.

General description

Students design and implement a real-time multi-tasking operating system using the tools and techniques of real-time programming for embedded systems. Implementation uses cross-compilation for an ARM-based system-on-chip. The operating system then supports an application program involving process control, data acquisition, and communication.

Logistics

Audience

  • CS major students. Usually taken in fourth year. This course benefits students interested in applied computer science, operating systems, or control and calibration.

Normally available

  • Winter and Spring*

*Enrollment may be limited due to lab room capacity.

Related courses

  • Pre-requisites: CS 350 or SE 350; Computer Science students only

For official details, see the UW calendar.

Software/hardware used

  • GCC cross-compiler for ARM
  • Technologic, TS-7200 development boards

Typical reference(s)

Required preparation

At the start of the course, students should be able to

  • Write programs in C.*

*Students develop programs to run on an Intel microcomputer system. Programs are written and cross-compiled on a host computer running UNIX and downloaded for execution on the microcomputer system. No prior knowledge of the Intel architecture is assumed and documentation is provided.

Learning objectives

At the end of the course, students should be able to

  • Design and implement moderate sized (~10K LOC) application programs
  • Design, implement, and use debugging tools for multi-tasking programs, particularly critical races
  • Program in assembly language directly on the hardware
  • Participate in and maintain a pleasant social environment in the laboratory
  • Work effectively as part of a team
  • Create and perform an effective demo

Typical syllabus

Real-time systems (2 hours)

  • Introduction to real-time systems
  • Definition of the concept of a process

Concurrency and CPU multiplexing (3 hours)

  • Review of concurrency and CPU multiplexing
  • Implementation of a simple application using the concept of cyclic execution to provide concurrency

Real-time operating system (12 hours)

  • Implementation of a simple but powerful real-time operating system kernel providing support for multiple processes, inter-process communication and synchronization via message passing, and interrupts

Process structuring techniques (9 hours)

  • Design of those parts of the operating system that provide services to application programs
  • Stereotypical task capabilities: servers, clients, workers
  • Task structuring for application programs
  • Pathologies: deadlock, performance problems
  • Debugging

Application (6 hours)

Students design and implement an application, running on their operating system, that controls several trains doing independent tasks while sharing a single track. Students gain knowledge of the following:

  • Calibration, building a computational model that maps accurately onto train kinematics
  • Real-time fault tolerance, building algorithms that maintain time consistency in the presence of hardware faults
  • Sensor attribution, assigning sesor reports to the correct real-world entity
  • Mutual exclusion in an unreliable world

Other topics (6 hours)

  • Other approaches to the design of real-time systems
  • Language support for real-time concurrent systems: Golang
  • Type-safe communication
  • Multiprocessors, scheduling
 
 

CS 454 Distributed Systems

Objectives

This course provides an introduction to the fundamentals of distributed computer systems, assuming the availability of facilities for data transmission. The structure of distributed systems using multiple levels of software is emphasized.

Intended Audience

CS 454 is a course for CS major students and is normally completed in the fourth year.

Related Courses

Prerequisites: CS 350 or SE 350; Computer Science students only. CS 456 is not a prerequisite, but it is useful to be familiar with the information it provides about the underlying facilities assumed in this course.

References

Distributed Systems – Principles and Paradigms,2nd Edition, by A.S. Tanenbaum and M. van Steen, Prentice Hall, 2002. (Required)

Distributed Systems – Concepts and Design, 4rd ed., G. Coulouris, J. Dollimore, and T. Kindberg, Addison Wesley, 2001.(Optional)

Schedule

3 hours of lectures per week. Normally available in Winter, and Spring.

Notes

  1. Assignments are weighted heavily in computing final marks and include significant implementation work.

Outline

Fundamentals of Distributed Algorithms (10 hours)

Clock synchronization, partial order of events, election algorithms, agreement algorithms, distributed shared memory, process synchronization.

File and Directory Systems (6 hours)

Naming and name resolution; name, directory, and file servers; caching.

Distributed databases (3 hours)

Locking and concurrency control, deadlock handling, stable storage, two-phase commit.

Security and Protection (3 hours)

Encryption, public and private keys, authentication, privacy.

Distributed Services (6 hours)

File transfer, electronic mail, World-Wide Web.

Examples of Distributed Systems (8 hours)

Some of: Mach, Amoeba, OSF DCE, CORBA, DCOM.

 

CS 456 Computer Networks

General description

This course introduces the fundamentals of network architectures and protocols and focuses on protocols used in the Internet.

Logistics

Audience

  • CS major students. Usually taken in fourth year

Normally Available

  • Fall, Winter, and Spring

Related courses

  • Pre-requisites: CS 350 or ECE 354; Computer Science students only
  • Anti-requisites: CS 436, ECE 358, 428For official details, see the UW calendar

Software/hardware used

  • Standard Linux environment with open-source programming language interpreters and compilers
  • Secure shell (ssh) and secure copy (scp)

Typical References

  • Computer Networking, a Top-Down Approach Featuring the Internet (6th edition),by James F. Kurose and Keith W. Ross, Addison-Wesley, 2012.

Required preparation

At the start of the course, students should be able to:

  • Write, test, and debug programs of moderate size in preferred programming language
  • Describe basic components and explain basic properties of computing devices
  • Understand and use basic probability and statistics

Learning objectives

At the end of the course, students should have the ability to:

  • Describe basic components and explain basic properties of a computer network.
  • Explain, and compare networking techniques including packet switching and circuit switching.
  • Define and calculate network performance metrics including throughput and delay.
  • Illustrate the Internet protocol stack and the Internet architecture.
  • Explain and compare network application models including peer-to-peer and client/server.
  • Recall, describe and illustrate different contemporary Internet application protocols.
  • Explain the principles of TCP reliable data transfer, flow control, congestion control and connection management.
  • Recall, classify and compare least-cost path computation algorithms and Internet routing protocols.
  • Recall, classify and compare data transmission media and medium access control schemes.
  • Reason about the efficiency of data communication protocols.
  • Develop and write client-server programs using the socket API.

Typical syllabus

Overall picture of computer networking (8 hours)

  • Circuit switching vs. packet switching
  • access networks
  • physical media
  • network delays
  • protocol layering
  • TCP/IP architecture

Application layer protocols (8 hours)

  • World wide web (HTTP)
  • File Transfer Protocol (FTP)
  • electronic mail (SMTP)
  • Domain Name System (DNS)
  • socket programming

Transport layer protocols (8 hours)

  • Design issues
  • connectionless transport UDP
  • principles of reliable data transfer
  • connection-oriented Transport TCP
  • flow control
  • congestion control

Network layer and routing (8 hours)

  • Routing approaches
  • routing in the Internet
  • Internet protocol
  • multicast routing
  • tunnelling, router design

Data link layer (8 hours)

  • Multiple access protocols and LANs
  • address resolution protocol
  • wireless LANs
 
 

CS 457 System Performance Evaluation

Watch a video introduction to the course on YouTube.

Objectives

To provide an in-depth understanding of the basic techniques for system performance evaluation. Emphasis will be placed on the application of these techniques to computer systems and networks.

Intended Audience

This course is for CS majors.

Related Courses

Prerequisites: (CS 246 or 247) and (STAT 206 or 231/ 241); Computer Science students only.

References

The Art of Computer Systems Performance Analysis, by R. Jain, John Wiley & Sons, 1991. Course notes are required.

Schedule

3 hours of lectures per week.

Outline

Basic Concept of Modelling and Performance Evaluation (1-2 hours)

Performance metrics. Steps in a performance study. Evaluation techniques: analytic modeling, simulation, and measurement.

Measurement Techniques and Tools (2-3 hours)

Workload characterization. Performance monitors. Benchmarking.

Discrete Event Simulation (6-8 hours)

Queuing and non-queuing models. Event scheduling approach. Random number generators. Generation of random variates.

Verification and Validation of Simulation Models (2-3 hours)

Fundamental results in queuing systems. Model validation technique.

Analysis of Simulation Output (3-4 hours)

Input parameter estimation. Steady state and transient results. Replication. Statistical analysis of output data.

Experimental Design (1-2 hours)

Analytic Modelling of Queuing Systems (6-8 hours)

Single server queue. Network of queues. Scheduling disciplines. Resource utilization. Response time analysis.

Examples of Performance Models (6-8 hours)

Examples from computer systems and networks.

 


CS 458: Computer Security and Privacy

Watch a video introduction to this course on YouTube.

General description

This course introduces students to security and privacy issues that affect various aspects of computing, including programs, operating systems, networks, databases, and Internet applications. The course examines the causes of security and privacy breaches and provides methods to help prevent them.

Logistics

Audience

  • CS major students in third or fourth year

Normally available

  • Fall, Winter, and Spring

Related courses

  • Pre-requisites: CS 350 or SE 350; Computer Science students only
  • Anti-requisites: ECE 458

For official details, see the UW calendar.

Software/hardware used

  • Linux, including virtualized Linux environments
  • Common Linux development and debugging tools, including gcc, gdb, and text editors
  • Mathematics software, such as Maple
  • Secure shell (ssh) and secure copy (scp)
  • Client and server network applications, such as web servers and curl
  • Network traffic analysis tools, such as wireshark
  • A program to produce PDF-format documents
  • Submit command for assignment submission

Typical reference(s)

  • Charles P. Pfleeger, Shari Lawrence Pfleeger, and Jonathan Margulies, Security in Computing, fifth edition

Required preparation

At the start of the course, students should be able to

  • Write, test, and debug programs of moderate size
  • Explain basic properties of the C memory model: bytes vs. words, memory as an array, run-time stack and stack frames, memory allocation on the heap vs. automatic allocation on the stack, pointers as memory addresses
  • Describe memory management (as related to operating systems) and virtual memory
  • Explain the concepts of threads, processes, and address spaces
  • Explain how processes can communicate within the same machine
  • Understand and use basic algebra and probability

Learning objectives

At the end of the course, students should be able to

  • Create programs that can defend against active attacks, not just against random bugs
  • Analyze programs and computing systems to point out security and privacy vulnerabilities
  • Identify and explain security and privacy related threats and issues across a range of computing systems
  • Identify and explain common approaches to protecting security and privacy in computing systems and evaluate the effectiveness of their deployments
  • Enumerate and differentiate key components of security and privacy policies, and evaluate proposed content for them
  • Demonstrate knowledge of legal and ethical issues in computing, particularly as applied to security and privacy

Typical syllabus

Introduction to computer security and privacy (1.5 hours)

  • Meaning of computer security, comparing security with privacy, types of threats and attacks, methods of defense

Program security (6 hours)

  • Secure programs, nonmalicious program errors, malicious code, controls against program threats

Operating system security (6 hours)

  • Methods of protection, access control, user authentication

Network security (4.5 hours)

  • Network threats, firewalls, intrusion detection systems

Internet application security and privacy (9 hours)

  • Basics of cryptography, security and privacy for Internet applications (email, instant messaging, web browsing), privacy-enhancing technologies

Database security and privacy (4.5 hours)

  • Security and privacy requirements, reliability, integrity, and privacy, inference, data mining, k-anonymity

Non-technical aspects (4.5 hours)

  • Administration of security systems, policies, physical security, economics of security, legal and ethical issues

 

 

CS 462: Formal Languages and Parsing

Watch a video introduction to this course on YouTube.

General description

Building on CS 360, this course discusses more advanced topics in formal languages and automata theory, including applications, compiler writing, and parsing methods.

Logistics

Audience

  • CS major students. Usually taken in fourth year.

Normally available

  • Winter Term

Related courses

  • Pre-requisites: CS 360 or 365 or equivalent course
  • Successors: Graduate courses in compiler writing or formal languages

For official details, see the UW calendar.

Software/hardware used

  • —

Typical reference(s)

  • J. Shallit, A Second Course in Formal Languages & Automata Theory, Cambridge University Press

Required preparation

At the start of the course, students should be able to

  • Prove statements by induction
  • Explain basic computing models, such as finite automata, pushdown automata, and Turing machines
  • Describe grammars and machine models

Learning objectives

At the end of the course, students should be able to

  • Explain more about basic computer models
  • Describe the theory behind modern parsing methods
  • Solve problems in the theory of combinatorics on words

Typical syllabus

Properties of strings (3 hours)

  • Outline of formal language theory
  • Strings, machines, proofs by induction
  • Combinatorics on words
  • Thue’s problem

Regular sets (10 hours)

  • Closure of regular sets under quotient, substitution, and inverse homomorphism
  • Decision algorithms for regular sets
  • Myhill-Nerode theorem
  • Minimization of finite automata
  • Finite-state transducers

Context-free languages (6 hours)

  • Coping with ambiguity
  • Inherently ambiguous CFL’s
  • Closure of context-free languages under substitution, inverse homomorphism, and intersection with regular sets
  • Decision algorithms for context-free languages
  • Parsing arbitrary context-free grammars
  • Decidability results for CFG’s

Parsing (6 hours)

  • Phases of compilation
  • Top-down parsing
  • LL(1) grammars
  • Bottom-up parsing
  • LR(0) grammars and LR(k) grammars

Chomsky hierarchy (3 hours)

  • Left- and right-regular grammars
  • Unrestricted (Type 0) grammars
  • Equivalence of Type 0 grammars and Turing machines
  • Context-sensitive languages
  • Linear bounded automata

Deterministic context-free languages (3 hours)

  • Normal forms
  • Closure under complementation
  • Relationship to LR(0) grammars

Other language classes (5 hours)

  • L-systems
  • Applications to computer graphics
  • Rational series
 


CS 466 Algorithm Design and Analysis

Watch a video introduction to this course on YouTube.

Objectives

This course continues the discussion of algorithms started in CS 341. Whereas CS 341 focuses on worst-case behaviour of deterministic algorithms, in this course students are exposed to algorithmic approaches and methods for assessment that reflect a broad spectrum of criteria.

The particular problems and algorithms studied will be chosen by the instructor from application areas such as computational geometry, algebraic algorithms, distributed and parallel algorithms, machine learning, and other areas of active research.

Intended Audience

CS 466 is normally taken in a student’s fourth year. Those interested in the more mathematical aspects of writing good programs will find this course to be of value.

Related Courses

Prerequisites: CS 341; Computer Science students only.

Successors: Graduate courses in algorithms and computational complexity.

References

Introduction to Algorithms, 3rd ed., by Thomas Cormen, C. Leiserson, R. Rivest, C. Stein, MIT Press, 2009.

Schedule

3 hours of lectures per week. Normally available in Fall and Spring.

Outline

Randomized Algorithms (6 hours)

Algorithms that rely on random bits; Las Vegas and Monte Carlo algorithms.

Amortized Analysis (6 hours)

Analyzing sequences of operations whose individual costs differ widely; the accounting and potential methods. Possible topics: Fibonacci heaps; The “union-find” data structure.

Lower Bounds (6 hours)

Decision trees. Information theory lower bounds. Adversary arguments.

Approximation Algorithms (6 hours)

Techniques for creating approximation algorithms. Problems for which good approximations cannot be obtained.

Online Algorithms (6 hours)

Algorithms in which each request must be serviced before the subsequent request is received. The k-server problem.

Other Topics (6 hours)

May include specialized models of computation, Kolmogorov complexity, derandomization, and other tools to support the application areas chosen by the instructor.

 

CS 475: Computational Linear Algebra

Watch a video introduction to this course on YouTube.

General description

CS 475 covers four major topics: solving special linear systems, least squares problems, eigenvalue problems, and singular value decomposition. The course introduces students to mathematical concepts and numerical methods used for solving mathematical problems and to the implementation of algorithms in a high-level programming language framework.

Logistics

Audience

  • CS major students. Usually taken in fourth year.

Normally available

  • Summer

Related courses

  • Pre-requisites: AMATH 242/CM 271/CS 371 or CS 370; Not open to General Mathematics students students
  • Anti-req: CM/CS 372, 472

For official details, see the UW calendar.

Software/hardware used

  • UNIX

Typical reference(s)

  • L.N. Trefethen, D. Bau III, Numerical Linear Algebra, SIAM, 1997
  • J. Demmel, Applied Numerical Linear Algebra, SIAM, 1997
  • H. Wendland, Numerical Linear Algebra: An Introduction,Cambridge University Press, 2017

Required preparation

At the start of the course, students should be able to

  • Write programs in MATLAB
  • Apply techniques and concepts of numerical computation, such as accuracy, stability, efficiency, floating point arithmetic, LU factorization
  • Recall basic data structures, algorithms, and computer organization
  • Use basic linear algebra and calculus

Learning objectives

At the end of the course, students should be able to

  • Use matrix factorizations in solving numerical linear algebra problems
  • Analyze the complexity of numerical linear algebra algorithms
  • Apply the numerical techniques for solving application problems
  • Implement numerical linear algebra algorithms using MATLAB
  • Develop a set of numerical linear algebra routines for solving linear systems, least squares problems, eigenvalue problems, and singular value decomposition.

Typical syllabus

Solving special linear systems (15 hours)

  • Examples of special matrices: symmetric, positive definite, tridiagonal, band, general sparse matrices
  • Direct methods: sparse Gaussian elimination, basic graph theory, ordering algorithms
  • Iterative methods: Jacobi, Gauss-Seidel, SOR, conjugate gradient
  • Convergence analysis and concepts of preconditioning
  • Example application: Image denoising using total variation models

Least squares problems (8 hours)

  • Data fitting, parametric estimation, overdetermined systems, and least squares problems
  • Orthogonal matrices and orthogonal projection
  • Different approaches for solving least squares problems, such as normal equations, QR factorization, and singular value decomposition
  • Compute QR factorization using Gram-Schmidt, Householder transform, and Givens rotation

Eigenvalue problems (7 hours)

  • Basic concepts of eigenvalues and eigenvectors
  • Compute eigenvalues and eigenvectors using power methods, inverse iteration, Rayleigh-quotient iteration, and QR algorithm
  • Connection between QR algorithm and simultaneous iteration
  • Complexity and reduction to Hessenberg or tridiagonal form
  • Example applications: Google page ranking, image segmentation

Singular value decomposition (6 hours)

  • Basic concepts of singular values and singular vectors
  • Compute SVD via eigenvalue decomposition
  • Implementation using bidiagonalization
  • Low rank approximation using SVD and its application
 
 

CS 480: Introduction to Machine Learning

Watch a video introduction to this course on YouTube.

General description

The course introduces students to the design of algorithms that enable machines to “learn”. In contrast to the classic paradigm where machines are programmed by specifying a set of instructions that dictate what exactly a machine should do, a new paradigm is developed whereby machines are presented with examples from which they learn what to do. This is especially useful in complex tasks such as natural language processing, information retrieval, data mining, computer vision and robotics where it is not practical for a programmer to enumerate all possible situations in order to specify suitable instructions for all situations. Instead, a machine is fed with large datasets of examples from which it automatically learns suitable rules to follow. The course will introduce the basics of machine learning and data analysis.

Logistics

Audience

  • CS major students. Usually taken in fourth year. Beneficial for students who are interested in computer applications that solve sophisticated problems.

Normally available

  • Fall, Winter, and Spring

Related courses

  • Pre-requisites: CM 339/CS 341 or SE 240; Computer Science students only
  • Co-requisites: STAT 206 or 231 or 241

For official details, see the UW calendar.

Typical reference(s)

  • Hal Daume III, A course in Machine Learning (under writing)
  • Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning (under writing)
  • Christopher Bishop, Pattern Recognition and Machine Learning (2006)
  • Kevin Murphy, Machine Learning, A Probabilistic Perspective (2012)

Required preparation

At the start of the course, students should be able to

  • Use basic algebra, calculus, and probability
  • Write efficient, readable programs from scratch
  • Read and write technical documents

Learning objectives

At the end of the course, students should be able to

  • Formalize a task as a machine learning problem
  • Identify suitable algorithms to tackle different machine learning problems
  • Apply machine learning algorithms to datasets

Typical syllabus

Introduction

  • Generalization
  • Underfitting, overfitting
  • Cross-validation

Linear models

  • Linear regression
  • Classification with linear separators (mixtures of Gaussians, logistic regression, perceptron, support vector machines)

Non-linear models

  • Non-linear basis functions
  • Kernel methods
  • Deep neural networks

Unsupervised learning

  • Clustering

Sequence learning

  • Hidden markov models
  • Recurrent and recursive neural networks

Ensemble learning

  • Bagging
  • Boosting

Large scale learning

  • Distributed learning
  • Stream learning

End user issues of Machine Learning

Real-world applications of Machine Learning

Topics in Machine Learning

 

CS 482: Computational Techniques in Biological Sequence Analysis

General description

This course introduces the most well known bioinformatics problems and the algorithms behind their solutions. These problems include sequence alignment, large-scale sequence database search, evolutionary tree reconstruction, gene prediction, and protein sequencing. Students explore the underlying computational techniques and skills to solve similar problems.

Logistics

Audience

  • Students taking the Bioinformatics option or students interested in learning how to apply mathematical modeling and algorithmic methods to solve biological problems. Usually taken in fourth year.

Normally available

  • Winter

Related courses

  • Pre-requisites: CS 341, STAT 241 or at least 60% in STAT 231

For official details, see the UW calendar.

Software/hardware used

  • A personal computer for programming

Typical reference(s)

  • R. Durbin, S. Eddy, A. Krogh and G. Mitchison, Biological Sequence Analysis, Cambridge Press, 1999

Required preparation

At the start of the course, students should be able to

  • Program in Java, C++, or Python
  • Design algorithms and analyze an algorithm’s complexity
  • Describe basic concepts in molecular biology or quickly learn the concepts in the first few weeks

Learning objectives

At the end of the course, students should be able to

  • Find and use common bioinformatics resources and tools
  • Apply the learned modeling and algorithmic techniques to solve computational problems in biology
  • Apply the learned modeling and algorithmic techniques to solve data analysis problems in other areas

Typical syllabus

Introduction

  • Brief review of the fundamentals of molecular biology and genetics in the context of biology as an information science.

Pairwise sequence alignment

  • Classic dynamic programming ideas for pairwise sequence alignment
  • Statistical measures of alignment significance
  • Probabilistic models of homologous sequences

Heuristic sequence alignment

  • Mathematical ideas underlying BLAST, FASTA and other heuristic sequence aligners
  • Applications of sequence alignment
  • Multiple alignment

Exact string matching

  • Suffix trees, suffix arrays, and their application in pairwise and multiple alignment

Sequence annotation

  • Gene finding
  • Sequence feature detection
  • Motif finding
  • Hidden Markov models

Evolutionary tree algorithms

  • Classical and contemporary algorithms for inferring evolutionary trees

Protein sequence identification

  • Mass spectrometry and its application in protein identification and sequencing
 
 

CS 484 Introduction to Computational Vision

Required Background

  • Numerical computation (AMATH 242/341/CM 271/CS 371 or CS 370)
  • Basic programming experience (Matlab or C)
  • Probability (STAT230 or 240).
  • Computer Science students only

Assessment

Typical course offerings will have four or five assignments (60% of grade) and a final project (40% of the grade).

Each assignment will each contain a written and a programming component.  The programming components will be small (eg., completing an existing program), but will require significant exploration of the algorithms presented in lectures.  In particular, students will be expected to explore a wide range of input data and paramater settings to determine where algorithms succeed and where they fail. 

The final project will allow the student to explore a topic of their own choosing in detail.  The scope is wide, ranging from image processing to artificial intelligence, but students will be required to implement specific algorithm(s) on their own and perform a detailed evaluation of their performance.  They will also be required to perform their own research and write a comprehensive report.  The students may elect to present their material for partial credit towards the report requirement.  Students may choose a project related to their interest (hobby or work term) and/or research area (graduate students).  A list of topics and past projects will be provided to students on request.  Graduate students will typically do the same assignments but will be expected to produce a project with a substantial research component.

Overall goals

  • Learn modern computer vision problems, algorithms, and current research topics
  • Provide mathematical background for courses in image and signal processing
  • Learn general tools/algorithms for signal processing and data analysis

General guidelines

This course will generally have the same core material (see Outline below) but problems and applications may be specialized to the instructor or students’ interests.

Resources

Most classes will be lectures, involving blackboard work for mathematical derivations, slide presentations to show graphical concepts, and in-class demonstrations using Matlab.  Some time will be devoted to students presenting their projects at the end of term.

The course may use the following textbooks (in order of importantce, with relevant topics listed in italics):

  • E. Trucco and A. Verri. Introductory Techniques for 3D Computer Vision. Prentice-Hall, 1998. (typical topics in course)
  • D.A. Forsyth and J. Ponce. Computer Vision: A Modern Approach. Prentice-Hall, 2003. (many application areas)
  • B.K.P. Horn. Robot Vision. MIT Press, 1986. (lighting models, many early vision algorithms)
  • K.R. Castleman. Digital Image Processing. Prentice-Hall, 1996. (detailed image processing reference)

Finally, there are a number of online resourses, including research papers, data sets and sample code.  A good starting point is the “Computer Vision Homepage” at www.cs.cmu.edu/~cil/vision.html.

Outline Topics

Core Material (required)

  • Optics, Image formation, and Lighting models.  Core background for all vision work.  Closely related to image synthesis (ie., computer graphics).
  • Linear systems and Fourier Theory.  Mathematical background, common to vision and image processing.

     

     

  • Feature detection.  Starting point for most vision algorithms.
  • Fitting models to data.  Model fitting is typically by least squares, but extended to handle noise (robust fitting) and multiple models (mixture models, segmentation, adaptive algorithms).

Some typical topics (vary with instructor/class)

  • Feature grouping.  Segmentation, search, models of visual attention.
  • Image Registration.  Iterative techniques for image alignment; Application to image compositing.
  • Stereopsis.  Baseline stereo; Depth reconstruction by triangulation; Maximum flow formulation of the stereo problem; Epipolar geometry.
  • Optical flow.  Derivation of image flow field from 3D motion; Estimation of optical flow.
  • Object tracking and segmentation.  Optical flow or view-based techniques.
  • Structure from motion.  Scene reconstruction from image flow field: Factorization method, Direct methods.
  • Object Recognition. View based methods: principle components analysis, factor analysis; Model-based approaches; Interpretation tree search.
  • Event Recogntion.  Templates, Hidden markov models, dynamical models.
 
 

CS 485: Machine Learning

Watch a video introduction to this course on YouTube.

General Description

Machine learning is a fast growing topic for both commercial applications and academic research. It addresses the issue of how computers can “learn”, that is, how the process of drawing useful conclusions from massive data sets can be automated. Machine learning plays a central role in a wide range of applications emerging from the need to process data sets whose sizes and complexities are beyond the ability of humans to handle. The course will cover the theoretical foundations and the design of algorithms for machine learning. It draws from several established mathematical areas including statistics, geometry, combinatorics, and computational complexity.

Logistics

CS 485 is a course for Computer Science, Software Engineering and Math major students, and is normally completed in a student’s fourth year. The course should be relevant for all students who are interested in computational statistics, data mining, information retrieval, artificial intelligence, natural language processing, computer vision, computation finance, bioinformatics and health informatics where it is common to analyze massive data sets or it is desirable to design adaptive algorithms.

Related courses (see calendar for official details)

Predecessors: CS 341 and (STAT 206 or 230 or 240).

Typical Reference(s)

Christopher Bishop, Pattern Recognition and Machine Learning (2006) Shai Ben-David & Shai Shalev-Shwartz, Machine Learning: From Theoretical Principles to Practical Algorithms (in preparation)

Typical syllabus

Introduction to machine learning

Theoretical foundation

e.g. learning theory and Bayesian learning

Classification

Regression

Dimensionality reduction

Specific models/algorithms

e.g., naive Bayes, decision trees, neural networks, kernel methods, support vector machines, ensemble learning

 

CS 486: Introduction to Artificial Intelligence

Watch a video introduction to this course on YouTube.

General description

This course introduces students to the fundamental problems of artificial intelligence and the basic models and algorithms used to tackle these problems. Students examine frontier areas of computer science and gain knowledge that will allow them to further their studies in artificial intelligence.

Logistics

Audience

  • CS major students. Usually taken in fourth year. Beneficial for students who are interested in computer applications that solve sophisticated problems.

Normally available

  • Fall, Winter, and Spring

Related courses

  • Pre-requisites: CM 339/CS 341 or SE 240; Computer Science students only
  • Co-requisites: STAT 206 or 231 or 241

For official details, see the UW calendar.

Software/hardware used

  • Typically, students can use any programming language and development tools to complete assignments. Matlab is sometimes recommended.

Typical reference(s)

  • S. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, Prentice Hall, 3rd Edition, 2010.
  • D. Poole and A. Mackworth, Artificial Intelligence: Foundations of Computational Agents, Cambridge University Press, 2010.

Required preparation

At the start of the course, students should be able to

  • Use basic algebra, calculus, and probability
  • Write efficient, readable programs from scratch
  • Read and write technical documents

Learning objectives

At the end of the course, students should be able to

  • Describe some of the fundamental problems of artificial intelligence.
  • Identify basic models and algorithms used in artificial intelligence.
  • Demonstrate understanding of how and when to apply artificial intelligence models and algorithms.
  • Describe current research trends in artificial intelligence.

Typical syllabus

Introduction (1 hour)

  • Introduction to artificial intelligence
  • Building intelligent agents

Problem-solving (9 hours)

  • Building systems that solve problems by searching
  • Constraint satisfaction problems, backtrack and local search algorithms
  • Automated problem solving, graph search algorithms, searching implicit graphs, A* search
  • Automated planning

Knowledge representation and reasoning (4 hours)

  • Building systems that contain data to solve problems
  • Knowledge representation, propositional logic, first order logic, commonsense knowledge
  • Logical inference
  • Representing change
  • Building a knowledge base

Uncertain knowledge and reasoning (10 hours)

  • Building systems that reason and act in uncertain environments
  • Probabilistic reasoning, joint probabilities, conditional probabilities, conditional independence, Bayes rule, Bayesian networks
  • Utilities, decision theory, sequential decision making, value of information
  • Game theory, multi-agent systems, adversarial environments, partially observable environments

Machine learning (10 hours)

  • Building systems that improve with experience
  • Learning a function from examples, linear functions, generalized linear functions (nonlinear bases), neural networks, decision trees
  • Generalization theory, over-fitting and under-fitting, complexity control
  • Topics may also include reinforcement learning and unsupervised learning

Communicating (2 hours)

  • Building systems that communicate
  • Natural language understanding, parsing, grammars, semantic interpretation, pragmatics
 
 

CS 487 Introduction to Symbolic Computation

Watch a video introduction to the course on YouTube.

Objectives

This course is an introduction to the use of computers for symbolic mathematical computation, which involves such traditional algebraic (as opposed to numerical) computations as solving linear equations (exactly), analytic differentiation and integration of functions, and analytic solution of differential equations. The course is designed to expose students to the programming languages and data structures used for symbolic computation, the concepts from modern algebra which are applied to the development of algorithms for symbolic computation, and various applications of symbolic computation.

Intended Audience

CS 487 is normally completed in a student’s fourth year.

Related Courses

Prerequisites: CS 234 or 240 or SE 240; Honours Mathematics or Software Engineering students only.

Cross-listed: CM 433

References

Algorithms for Computer Algebra, by K. Geddes, S. Czapor and G. Labahn, Kluwer Academic Publishers, 1992.

Schedule

3 hours of lectures per week. Normally available in Winter.

Outline

Introduction (1 hour)

Symbolic versus numeric computation. History of systems for symbolic computation.

Algebraic Structures (5 hours)

Rings, integral domains, Euclidean domains, fields, quotient fields, finite fields.

Normal Forms and Data Structures (2 hours)

The need for simplification. Normal forms for polynomials. Data structures for integers and polynomials. Rational functions and power series.

Homomorphism Methods (6 hours)

Homomorphisms. Chinese remainder algorithm and interpolation. The Hensel construction.

Greatest Common Divisor Algorithms (6 hours)

Generalizations of the Euclidean algorithm for multivariate polynomials. Modular algorithms. Hensel techniques. Heuristic techniques.

Polynomial Factoring (6 hours)

Berlekamp’s method. Hensel techniques. Heuristic techniques.

Solution of Equations (4 hours)

Variations of Gaussian elimination. Modular techniques. Systems of polynomial equations.

Symbolic Integration (6 hours)

Hermite/Rothstein method for rational functions. The Risch algorithm for transcendental and algebraic functions.

CS 488: Introduction to Computer Graphics

Watch a video introduction to this course on YouTube.

General description

This course gives students a solid background in 3-D graphics techniques for use as a tool in more advanced applications. A major part of the course involves hands-on activities using an interactive graphics workstation.

Logistics

Audience

  • CS major students. Usually taken in fourth year.

Normally available

  • Fall, Winter, and Spring

Related courses

  • Pre-requisites: (CM 339/CS 341 or SE 240) and (CS 350 or SE 350) and (CS 370 or 371); Computer Science students only

Enrolment may be limited due to availability of graphics equipment.

For official details, see the UW calendar.

Software/hardware used

  • Linux
  • C++
  • OpenGL

Typical reference(s)

  • Donald Hearn, P. Baker, W. Carithers, Computer Graphics with Open GL (4th Edition), Prentice Hall, 2010
  • Dave Shreiner, The Khronos OpenGL ARB Working Group, OpenGL Programming Guide: The Official Guide to Learning OpenGL, Versions 3.0 and 3.1, 7th ed., Addison Wesley, 2009

Required preparation

At the start of the course, students should be able to

  • Write programs in UNIX with C++
  • Use and understand linear algebra, calculus, numerical analysis including numerical linear algebra, data structures, and algorithms

Learning objectives

At the end of the course, students should be able to

  • Carry out mathematical constructions on points, vectors, and transformations in affine spaces
  • Explain the algorithmic and mathematical concepts used at each stage of a modern graphics pipeline
  • Write interactive programs that display and manipulate 2D and 3D geometry
  • Write a ray tracer

Typical syllabus

Graphics environment (4 hours)

  • Overview of a representative processing sequence that connects application programs with images they display on screen
  • Outline of the graphics library students will use and the graphics workstation hardware

Mathematical underpinnings (4 hours)

  • Review of concepts and tools: points, vectors, lines, planes, matrices, dot and cross products, vector space, affine space, projective space, etc.

Transformations (4 hours)

  • 2- and 3-dimensional translation, rotation, and scaling as matrix operations
  • Homogeneous coordinates
  • Clipping, windowing, and viewing with perspective

Interrupting, picking, polling, callbacks (10 hours)

  • Management of picking, selecting, and control tasks through the use of event queues, interrupts, and device polling
  • Windowing systems and user interface toolkits

Hidden surfaces and shading (4 hours)

  • Standard lighting models and their implementation
  • Hidden-surface elimination using depth buffering, scanline coherence, and subdivision
  • Polygon filling

Ray tracing (4 hours)

  • Basic ray tracing techniques for generating shadows, mirror reflections, and refraction
  • Constructive solid geometry models

Physically based rendering (4 hours)

  • Radiosity, bi-directional path tracing, global illumination

Discretionary topics (5 hours)

  • Topics are chosen at the discretion of the instructor. Possible topics include more depth on any of the previous topics, human vision, colour theory, anti-aliasing, database amplification, animation, scientific visualization, graphics hardware support, higher-order curves and surfaces, and dynamic simulation.