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

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.

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

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:

To understand the fundamentals of storage systems and disk-based data structures;
To understand the process of query processing and optimization; and
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

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

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

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

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

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

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)

Course web pages
Course notes

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

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

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.

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)

Berlekamps 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.

CS 436: Networks and Distributed Computer Systems

CS 442: Principles of Programming Languages

General description

Logistics

Audience

Normally available

Related courses

Software/hardware used

Typical reference(s)

Required preparation

Learning objectives

Typical syllabus

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

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

Polymorphism (9 hours)

Other topics (9 hours)

CS 445: Software Requirements Specification and Analysis

General description

Logistics

Audience

Normally available

Related courses

Software/hardware used

Required preparation

Learning objectives

Typical syllabus

Introduction (3 hours)

Software development groups (3 hours)

Requirements elicitation (2 hours)

Informal notations for behavioural requirements (10 hours)

Formal notations for behavioural requirements (6 hours)

Non-behavioural requirements (2 hours)

Requirements validation (5 hours)

Cost estimation (3 hours)

Other topics (2 hours)

CS 446 Software Design and Architectures

Objectives

Intended Audience

Related Courses

Hardware/Software

References

Schedule

Outline

Introduction (1 hour)

Software Design Process Models (3 hours)

Architecture/Design Representations (9 hours)

Design Plans/Architecture (9 hours)

Design Strategies and Methods (6 hours)

Design Assessment (3 hours)

Design Quality Assurance and Verification (3 hours)

CS 447 Software Testing, Quality Assurance, and Maintenance

Objectives

Intended Audience

Related Courses

Hardware/Software

References

Schedule

Notes

Outline

Introduction (2 hours)

Software Maintenance (12 hours)

Project Management (3 hours)

Quality Assurance (4 hours)

Non-execution based testing (5 hours)

Testing in the Small (5 hours)

Testing in the Large (5 hours)

CS 448 Database Systems Implementation

Objectives

Intended Audience

Related Courses

References

Schedule

Outline

Review of relational database systems (3 hours)

Storage Management (9 hours)

Query Processing and Optimization (13 hours)

Transaction Management (12 hours)

Meta-data Management (2 hours)

CS 449: Human Computer Interaction

CS 450: Computer Architecture