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

Watch a video introduction to this course on YouTube.

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

- Fourth year CS majors

- Winter

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

For official details, see the UW calendar.

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

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

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)

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

- 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)

- 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)

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

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

Watch a video introduction to this course on YouTube.

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.

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

- Fall and Winter

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

- 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

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

- Write programs

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

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

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

- Methods for obtaining requirements from various sources.

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

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

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

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

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

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

Watch a video introduction to this course on YouTube.

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.

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.

Prerequisites: CS 350; Computer Science students only.

Antirequisites: CS 430, SE 464.

Related courses: CS 445, CS 447.

Cross-listed as: ECE 452.

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

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

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

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.

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.

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.

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. Selected methods: object modeling technique, structured design, real-time, user interfaces. Methods for design with off-the-shelf components.

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 reviews, scenarios and test cases, testing of executable design representations. Verification of properties.

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.

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.

Prerequisites: CS 350; Computer Science students only.

Antirequisites: SE 465.

Related courses: CS 445, CS 447.

Cross-listed as: ECE 453.

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

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

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

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

- The Course Project builds on CS 446.

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

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.

Cost estimation. Project scheduling. Specification of work units.

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

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

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.

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.

Watch a video introduction to this course on YouTube.

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.

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.

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

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

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

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

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

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

Transaction models, concurrency control algorithms, database recovery.

Implementation of catalogs and integrity constraints.

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

Watch a video introduction to this course on YouTube.

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.

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

- Winter

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

- UNIX, Verilog Simulator

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

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

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

- Transistors, digital logic, hardware description languages

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

- Data dependencies, local and global scheduling, performance

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

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

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

- GPGPU structure and programming models

Watch a video introduction to this course on YouTube.

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.

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

- Winter and Spring*

*Enrollment may be limited due to lab room capacity.

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

For official details, see the UW calendar.

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

- Course web pages
- Course notes

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.

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

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

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

- 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

- 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

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 approaches to the design of real-time systems
- Language support for real-time concurrent systems: Golang
- Type-safe communication
- Multiprocessors, scheduling

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.

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

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.

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)

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

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

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

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

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

Encryption, public and private keys, authentication, privacy.

File transfer, electronic mail, World-Wide Web.

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

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

- CS major students. Usually taken in fourth year

- Fall, Winter, and Spring

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

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

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

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

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.

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

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

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

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

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

Watch a video introduction to the course on YouTube.

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.

This course is for CS majors.

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

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

3 hours of lectures per week.

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

Workload characterization. Performance monitors. Benchmarking.

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

Fundamental results in queuing systems. Model validation technique.

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

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

Examples from computer systems and networks.

CS 458: Computer Security and Privacy

Watch a video introduction to this course on YouTube.

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.

- CS major students in third or fourth year

- Fall, Winter, and Spring

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

For official details, see the UW calendar.

- 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

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

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

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

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

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

- Methods of protection, access control, user authentication

- Network threats, firewalls, intrusion detection systems

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

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

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

Watch a video introduction to this course on YouTube.

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

- CS major students. Usually taken in fourth year.

- Winter Term

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

- —

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

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

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

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

- 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

- 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

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

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

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

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

CS 466 Algorithm Design and Analysis

Watch a video introduction to this course on YouTube.

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.

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.

Prerequisites: CS 341; Computer Science students only.

Successors: Graduate courses in algorithms and computational complexity.

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

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

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

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

Decision trees. Information theory lower bounds. Adversary arguments.

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

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

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

Watch a video introduction to this course on YouTube.

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.

- CS major students. Usually taken in fourth year.

- Summer

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

- UNIX

- 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

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

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.

- 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

- 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

- 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

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

Watch a video introduction to this course on YouTube.

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.

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

- Fall, Winter, and Spring

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

- 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)

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

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

- Generalization
- Underfitting, overfitting
- Cross-validation

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

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

- Clustering

- Hidden markov models
- Recurrent and recursive neural networks

- Bagging
- Boosting

- Distributed learning
- Stream learning

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.

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

- Winter

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

For official details, see the UW calendar.

- A personal computer for programming

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

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

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

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

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

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

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

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

- Classical and contemporary algorithms for inferring evolutionary trees

- Mass spectrometry and its application in protein identification and sequencing

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).- L
*inear 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.

Watch a video introduction to this course on YouTube.

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.

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)

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

Watch a video introduction to this course on YouTube.

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.

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

- Fall, Winter, and Spring

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

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

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

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

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.

- Introduction to artificial intelligence
- Building intelligent agents

- 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

- 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

- 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

- 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

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

Watch a video introduction to the course on YouTube.

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.

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

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

Cross-listed: CM 433

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

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

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

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

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

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

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

Berlekamps method. Hensel techniques. Heuristic techniques.

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

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

Watch a video introduction to this course on YouTube.

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.

- CS major students. Usually taken in fourth year.

- Fall, Winter, and Spring

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

- Linux
- C++
- OpenGL

- 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

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

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

- 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

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

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

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

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

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

- Radiosity, bi-directional path tracing, global illumination

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