CS 436: Networks and Distributed Computer Systems

General Description

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

Logistics

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

Related courses (see calendar for official details)

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

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

Hardware/Software used: UNIX, any programming language.

Typical References

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

Required preparation

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

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

Learning objectives

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

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

Typical syllabus

Physical and data link layer (6 hours)

media types, encoding, error correction, medium access control

Network layer (6 hours)

hierarchical addressing, forwarding, routing algorithms

Transport layer (6 hours)

reliable data transfer, connection management, rate control

Naming and mobility (3 hours)

indirect naming, name resolution, transparency, handover

High-level services (6 hours)

RPC, message queueing, clocks & synchronization, replication

Security and Privacy (3 hours)

confidentiality, integrity, availability

Operations and applications (3 hours)

email, web, multimedia


CS 442: Principles of Programming Languages

Watch a video introduction to this course on YouTube.

General description

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

Logistics

Audience

  • Fourth year CS majors

Normally available

  • Winter

Related courses

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

For official details, see the UW calendar.

Software/hardware used

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

Typical reference(s)

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

Required preparation

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

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

Learning objectives

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

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

Typical syllabus

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

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

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

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

Polymorphism (9 hours)

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

Other topics (9 hours)

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

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


CS 445: Software Requirements Specification and Analysis

Watch a video introduction to this course on YouTube.

General description

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

Logistics

Audience

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

Normally available

  • Fall and Winter

Related courses

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

For official details, see the UW calendar.

Software/hardware used

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

Typical reference(s)

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

Required preparation

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

  • Write programs

Learning objectives

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

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

Typical syllabus

Introduction (3 hours)

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

Software development groups (3 hours)

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

Requirements elicitation (2 hours)

  • Methods for obtaining requirements from various sources.

Informal notations for behavioural requirements (10 hours)

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

Formal notations for behavioural requirements (6 hours)

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

Non-behavioural requirements (2 hours)

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

Requirements validation (5 hours)

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

Cost estimation (3 hours)

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

Other topics (2 hours)

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


CS 446 Software Design and Architectures

Watch a video introduction to this course on YouTube.

Objectives

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

Intended Audience

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

Related Courses

Prerequisites: CS 350; Computer Science students only.

Antirequisites: CS 430, SE 464.

Related courses: CS 445, CS 447.

Cross-listed as: ECE 452.

Hardware/Software

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

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

References

Schedule

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

Outline

Introduction (1 hour)

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

Software Design Process Models (3 hours)

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

Architecture/Design Representations (9 hours)

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

Design Plans/Architecture (9 hours)

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

Design Strategies and Methods (6 hours)

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

Design Assessment (3 hours)

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

Design Quality Assurance and Verification (3 hours)

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


CS 447 Software Testing, Quality Assurance, and Maintenance

Objectives

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

Intended Audience

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

Related Courses

Prerequisites: CS 350; Computer Science students only.

Antirequisites: SE 465.

Related courses: CS 445, CS 447.

Cross-listed as: ECE 453.

Hardware/Software

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

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

References

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

Schedule

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

Notes

  1. The Course Project builds on CS 446.

Outline

Introduction (2 hours)

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

Software Maintenance (12 hours)

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

Project Management (3 hours)

Cost estimation. Project scheduling. Specification of work units.

Quality Assurance (4 hours)

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

Non-execution based testing (5 hours)

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

Testing in the Small (5 hours)

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

Testing in the Large (5 hours)

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


CS 448 Database Systems Implementation

Watch a video introduction to this course on YouTube.

Objectives

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

Intended Audience

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

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

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

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

Related Courses

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

References

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

Schedule

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

Outline

Review of relational database systems (3 hours)

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

Storage Management (9 hours)

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

Query Processing and Optimization (13 hours)

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

Transaction Management (12 hours)

Transaction models, concurrency control algorithms, database recovery.

Meta-data Management (2 hours)

Implementation of catalogs and integrity constraints.


CS 449: Human Computer Interaction

Watch a video introduction to this course on YouTube.

Goals

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

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

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

Logistics

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

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

Required Preparation

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

Learning Objectives

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

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

Typical Syllabus

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


CS 450: Computer Architecture

Watch a video introduction to this course on YouTube.

General description

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

Logistics

Audience

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

Normally available

  • Winter

Related courses

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

For official details, see the UW calendar.

Software/hardware used

  • UNIX, Verilog Simulator

Typical reference(s)

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

Required preparation

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

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

Learning objectives

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

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

Typical syllabus

Digital hardware design (6 hours)

  • Transistors, digital logic, hardware description languages

Instruction set architecture (3 hours)

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

Scalar pipelines (3 hours)

  • Data dependencies, local and global scheduling, performance

VLIW pipelines (6 hours)

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

Dynamic pipelines (9 hours)

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

Thread-level parallelism (6 hours)

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

Data-level parallelism (2 hours)

  • GPGPU structure and programming models


CS 452: Real-Time Programming

Watch a video introduction to this course on YouTube.

General description

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

Logistics

Audience

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

Normally available

  • Winter and Spring*

*Enrollment may be limited due to lab room capacity.

Related courses

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

For official details, see the UW calendar.

Software/hardware used

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

Typical reference(s)

Required preparation

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

  • Write programs in C.*

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

Learning objectives

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

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

Typical syllabus

Real-time systems (2 hours)

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

Concurrency and CPU multiplexing (3 hours)

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

Real-time operating system (12 hours)

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

Process structuring techniques (9 hours)

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

Application (6 hours)

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

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

Other topics (6 hours)

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


CS 454 Distributed Systems

Objectives

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

Intended Audience

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

Related Courses

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

References

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

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

Schedule

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

Notes

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

Outline

Fundamentals of Distributed Algorithms (10 hours)

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

File and Directory Systems (6 hours)

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

Distributed databases (3 hours)

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

Security and Protection (3 hours)

Encryption, public and private keys, authentication, privacy.

Distributed Services (6 hours)

File transfer, electronic mail, World-Wide Web.

Examples of Distributed Systems (8 hours)

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


CS 456 Computer Networks

General description

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

Logistics

Audience

  • CS major students. Usually taken in fourth year

Normally Available

  • Fall, Winter, and Spring

Related courses

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

Software/hardware used

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

Typical References

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

Required preparation

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

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

Learning objectives

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

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

Typical syllabus

Overall picture of computer networking (8 hours)

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

Application layer protocols (8 hours)

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

Transport layer protocols (8 hours)

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

Network layer and routing (8 hours)

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

Data link layer (8 hours)

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


CS 457 System Performance Evaluation

Watch a video introduction to the course on YouTube.

Objectives

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

Intended Audience

This course is for CS majors.

Related Courses

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

References

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

Schedule

3 hours of lectures per week.

Outline

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

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

Measurement Techniques and Tools (2-3 hours)

Workload characterization. Performance monitors. Benchmarking.

Discrete Event Simulation (6-8 hours)

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

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

Fundamental results in queuing systems. Model validation technique.

Analysis of Simulation Output (3-4 hours)

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

Experimental Design (1-2 hours)

Analytic Modelling of Queuing Systems (6-8 hours)

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

Examples of Performance Models (6-8 hours)

Examples from computer systems and networks.


CS 458: Computer Security and Privacy

Watch a video introduction to this course on YouTube.

General description

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

Logistics

Audience

  • CS major students in third or fourth year

Normally available

  • Fall, Winter, and Spring

Related courses

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

For official details, see the UW calendar.

Software/hardware used

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

Typical reference(s)

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

Required preparation

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

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

Learning objectives

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

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

Typical syllabus

Introduction to computer security and privacy (1.5 hours)

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

Program security (6 hours)

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

Operating system security (6 hours)

  • Methods of protection, access control, user authentication

Network security (4.5 hours)

  • Network threats, firewalls, intrusion detection systems

Internet application security and privacy (9 hours)

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

Database security and privacy (4.5 hours)

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

Non-technical aspects (4.5 hours)

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



CS 462: Formal Languages and Parsing

Watch a video introduction to this course on YouTube.

General description

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

Logistics

Audience

  • CS major students. Usually taken in fourth year.

Normally available

  • Winter Term

Related courses

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

For official details, see the UW calendar.

Software/hardware used

Typical reference(s)

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

Required preparation

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

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

Learning objectives

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

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

Typical syllabus

Properties of strings (3 hours)

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

Regular sets (10 hours)

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

Context-free languages (6 hours)

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

Parsing (6 hours)

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

Chomsky hierarchy (3 hours)

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

Deterministic context-free languages (3 hours)

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

Other language classes (5 hours)

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


CS 466 Algorithm Design and Analysis

Watch a video introduction to this course on YouTube.

Objectives

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

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

Intended Audience

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

Related Courses

Prerequisites: CS 341; Computer Science students only.

Successors: Graduate courses in algorithms and computational complexity.

References

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

Schedule

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

Outline

Randomized Algorithms (6 hours)

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

Amortized Analysis (6 hours)

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

Lower Bounds (6 hours)

Decision trees. Information theory lower bounds. Adversary arguments.

Approximation Algorithms (6 hours)

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

Online Algorithms (6 hours)

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

Other Topics (6 hours)

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


CS 475: Computational Linear Algebra

Watch a video introduction to this course on YouTube.

General description

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

Logistics

Audience

  • CS major students. Usually taken in fourth year.

Normally available

  • Summer

Related courses

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

For official details, see the UW calendar.

Software/hardware used

  • UNIX

Typical reference(s)

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

Required preparation

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

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

Learning objectives

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

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

Typical syllabus

Solving special linear systems (15 hours)

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

Least squares problems (8 hours)

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

Eigenvalue problems (7 hours)

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

Singular value decomposition (6 hours)

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


CS 480: Introduction to Machine Learning

Watch a video introduction to this course on YouTube.

General description

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

Logistics

Audience

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

Normally available

  • Fall, Winter, and Spring

Related courses

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

For official details, see the UW calendar.

Typical reference(s)

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

Required preparation

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

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

Learning objectives

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

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

Typical syllabus

Introduction

  • Generalization
  • Underfitting, overfitting
  • Cross-validation

Linear models

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

Non-linear models

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

Unsupervised learning

  • Clustering

Sequence learning

  • Hidden markov models
  • Recurrent and recursive neural networks

Ensemble learning

  • Bagging
  • Boosting

Large scale learning

  • Distributed learning
  • Stream learning

End user issues of Machine Learning

Real-world applications of Machine Learning

Topics in Machine Learning


CS 482: Computational Techniques in Biological Sequence Analysis

General description

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

Logistics

Audience

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

Normally available

  • Winter

Related courses

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

For official details, see the UW calendar.

Software/hardware used

  • A personal computer for programming

Typical reference(s)

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

Required preparation

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

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

Learning objectives

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

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

Typical syllabus

Introduction

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

Pairwise sequence alignment

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

Heuristic sequence alignment

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

Exact string matching

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

Sequence annotation

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

Evolutionary tree algorithms

  • Classical and contemporary algorithms for inferring evolutionary trees

Protein sequence identification

  • Mass spectrometry and its application in protein identification and sequencing


CS 484 Introduction to Computational Vision

Required Background

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

Assessment

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

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

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

Overall goals

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

General guidelines

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

Resources

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

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

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

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

Outline Topics

Core Material (required)

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

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

Some typical topics (vary with instructor/class)

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


CS 485: Machine Learning

Watch a video introduction to this course on YouTube.

General Description

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

Logistics

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

Related courses (see calendar for official details)

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

Typical Reference(s)

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

Typical syllabus

Introduction to machine learning

Theoretical foundation

e.g. learning theory and Bayesian learning

Classification

Regression

Dimensionality reduction

Specific models/algorithms

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


CS 486: Introduction to Artificial Intelligence

Watch a video introduction to this course on YouTube.

General description

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

Logistics

Audience

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

Normally available

  • Fall, Winter, and Spring

Related courses

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

For official details, see the UW calendar.

Software/hardware used

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

Typical reference(s)

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

Required preparation

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

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

Learning objectives

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

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

Typical syllabus

Introduction (1 hour)

  • Introduction to artificial intelligence
  • Building intelligent agents

Problem-solving (9 hours)

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

Knowledge representation and reasoning (4 hours)

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

Uncertain knowledge and reasoning (10 hours)

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

Machine learning (10 hours)

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

Communicating (2 hours)

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


CS 487 Introduction to Symbolic Computation

Watch a video introduction to the course on YouTube.

Objectives

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

Intended Audience

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

Related Courses

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

Cross-listed: CM 433

References

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

Schedule

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

Outline

Introduction (1 hour)

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

Algebraic Structures (5 hours)

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

Normal Forms and Data Structures (2 hours)

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

Homomorphism Methods (6 hours)

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

Greatest Common Divisor Algorithms (6 hours)

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

Polynomial Factoring (6 hours)

Berlekamp’s method. Hensel techniques. Heuristic techniques.

Solution of Equations (4 hours)

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

Symbolic Integration (6 hours)

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


CS 488: Introduction to Computer Graphics

Watch a video introduction to this course on YouTube.

General description

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

Logistics

Audience

  • CS major students. Usually taken in fourth year.

Normally available

  • Fall, Winter, and Spring

Related courses

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

Enrolment may be limited due to availability of graphics equipment.

For official details, see the UW calendar.

Software/hardware used

  • Linux
  • C++
  • OpenGL

Typical reference(s)

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

Required preparation

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

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

Learning objectives

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

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

Typical syllabus

Graphics environment (4 hours)

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

Mathematical underpinnings (4 hours)

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

Transformations (4 hours)

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

Interrupting, picking, polling, callbacks (10 hours)

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

Hidden surfaces and shading (4 hours)

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

Ray tracing (4 hours)

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

Physically based rendering (4 hours)

  • Radiosity, bi-directional path tracing, global illumination

Discretionary topics (5 hours)

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