CS 341 Algorithms

Watch a video introduction to this course on YouTube.

Objectives

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

Intended Audience

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

Related Courses

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

Antirequisites: SE 240, SYDE 423.

Cross-listed as: CM 339

Successors: CS 466.

References

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

Schedule

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

Notes

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

Outline

Introduction and Analysis of Algorithms (6 hours)

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

Algorithm Design Techniques (15 hours)

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

Undecidability and Intractability (15 hours)

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


CS 343: Concurrent and Parallel Programming

Watch a video introduction to this course on YouTube.

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

Logistics

Audience

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

Normally available

  • Fall and Winter

Related courses

  • Pre-requisites: CS 350 or SE 350

For official details, see the UW calendar.

Software

  • UNIX, C++

Typical reference(s)

  • Course notes

Required preparation

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

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

Learning objectives

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

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

Typical syllabus

Advanced control flow (3 hours)

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

Coroutines (4 hours)

  • Multiple stacks, context switching
  • Semi and full coroutines

Concurrency (3 hours)

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

Mutual exclusion (4 hours)

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

Locks (4 hours)

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

Concurrency errors (3 hours)

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

High-level concurrency (8 hours)

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

Other concurrency approaches (3 hours)

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

Optimization (2 hours)

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

Distributed environments (2 hours)

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


CS 348 | SCS | UW

Revised March 3, 2015

CS 348: Introduction to Database Management

Watch a video introduction to this course on YouTube.

General description

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

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

Logistics

Audience

  • CS major students

Normally available

  • Fall, Winter, and Spring

Related courses

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

For official details, see the UW calendar.

Software/hardware used

  • A database management system, currently DB2 on Linux labs

Typical reference(s)

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

Required preparation

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

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

Learning objectives

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

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

Typical syllabus

Introduction (2 hours)

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

Relational database systems (6 hours)

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

Database design (7 hours)

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

SQL and interfaces (7 hours)

  • SQL DDL, SQL DML, QBE

Database application development (5 hours)

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

Database tuning (3 hours)

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

Database administration (3 hours)

  • Views and view management
  • Database security and authorization

Current topics (6 hours)

  • Distributed databases, data warehouses, data mining


CS 349: User Interfaces

Watch a video introduction to this course on YouTube.

General description

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

Logistics

Audience

  • CS major students interested in modern user interfaces

Normally available

  • Fall, Winter, and Spring

Related courses

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

For official details, see the UW calendar.

Software/hardware used

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

Typical reference(s)

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

Required preparation

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

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

Learning objectives

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

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

Typical syllabus

Event architecture (4 hours)

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

Design patterns (4 hours)

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

Components and interactor trees (4 hours)

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

Algorithms for user interaction (4 hours)

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

2D graphics (4 hours)

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

People and the human-machine interface (6 hours)

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

UI specification (4 hours)

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

Special topics (6 hours)

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



CS 350: Operating Systems

General description

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

Logistics

Audience

  • 3A or 3B CS major students

Normally available

  • Fall, Winter, and Spring

Related courses

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

For official details, see the UW calendar.

Software/hardware used

  • C programming language

Typical reference(s)

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

Required preparation

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

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

Learning objectives

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

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

Typical syllabus

Operating system introduction (2 hours)

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

Multi-programming (7 hours)

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

Concurrency (6 hours)

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

Memory management (8 hours)

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

Device management (3 hours)

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

File systems (5 hours)

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

Interprocess communication (5 hours)

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



CS 360 Introduction to the Theory of Computing

Watch a video introduction to this course on YouTube.

General description

This course introduces the theoretical foundations of Computer Science.

Logistics

Audience

  • CS major students and especially students interested in graduate school

Normally available

  • Fall, Winter, and Spring

Related courses

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

For official details, see the UW calendar.

Software/hardware used

  • None

Typical reference(s)

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

Required preparation

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

  • Describe what a proof is
  • Create proofs by induction

Learning objectives

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

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

Typical syllabus

Finite automata (10 hours)

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

Context-free grammars (10 hours)

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

Turing machines (9 hours)

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

Undecidability (7 hours)

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


CS 370: Numerical Computation

Watch a video introduction to the course on YouTube.

General description

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

Logistics

Audience

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

Normally available

  • Fall, Winter, and Spring

Related courses

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

For official details, see the UW calendar.

Software/hardware used

  • MATLAB

Typical reference(s)

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

Required preparation

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

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

Learning objectives

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

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

Typical syllabus

Floating point numbers (3 hours)

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

Interpolation (6 hours)

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

Ordinary differential equations (9 hours)

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

Discrete Fourier analysis (9 hours)

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

Numerical linear algebra (9 hours)

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


CS 371: Introduction to Computational Mathematics

Watch a video introduction to the course on YouTube.

General description

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

Logistics

Audience

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

Normally available

  • Winter and Spring

Related courses

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

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

For official details, see the UW calendar.

Software/hardware used

  • MATLAB

Typical reference(s)

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

Required preparation

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

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

Learning objectives

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

Typical syllabus

Floating point number systems (3 hours)

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

Polynomial interpolation (4 hours)

  • Interpolation: Lagrange and cubic spline

Nonlinear equations (4 hours)

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

Numerical linear algebra (11 hours)

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

Discrete Fourier analysis (11 hours)

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

Numerical integration (3 hours)

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