General description

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

Logistics

Audience

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

Normally available

- Fall and Spring

Related courses

- Pre-requisites: Not open to Computer Science students

For official details, see the UW calendar.

Software/hardware used

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

Typical reference(s)

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

Required preparation

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

- Use standard application software

Learning objectives

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

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

Typical syllabus

**Methodology** (3 hours)

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

**System administration **(3 hours)

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

**Structured word processing **(3 hours)

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

**Vector and pixel graphics **(6 hours)

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

**Networking and the internet **(3 hours)

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

**Scripting **(6 hours)

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

**Relational databases **(9 hours)

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

**Social media **(3 hours)

- Usage
- Ethics
- Privacy
- Usefulness

General description

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

Logistics

Audience

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

Normally available

- Winter

Related courses

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

For official details, see the UW calendar.

Software/hardware used

- UNIX, MIPS Simulator

**Typical reference(s)**

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

Required preparation

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

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

Learning objectives

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

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

Typical syllabus

**Introduction (2 hours)**

**Assembly language **(8 hours)

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

**Data representation and arithmetic **(4 hours)

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

**Compiling and linking **(4 hours)

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

**Basic processor design **(4 hours)

- Datapath, pipelining, hazards

**Memory and I/O devices **(6 hours)

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

**Multiprocessing **(6 hours)

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

**Operating systems **(2 hours)

- Brief overview of components

General description

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

Logistics

Audience

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

Normally available

- Spring

Related courses

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

For official details, see the UW calendar.

Software/hardware used

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

Typical reference(s)

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

Required preparation

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

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

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

Learning objectives

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

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

Typical syllabus

**Basic concepts (7 hours)**

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

**General approaches (18 hours)**

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

**Hardness (3 hours)**

- Lower bounds
- NP-completeness

**Beyond hardness (5 hours)**

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

CS 234: Data Types and Structures

General description

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

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

Logistics

Audience

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

Normally available

- Fall, Spring

Related courses

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

For official details, see the UW calendar.

Software/hardware used

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

Typical reference(s)

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

Required preparation

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

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

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

Learning objectives

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

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

Typical syllabus

**Basic concepts **(12 hours)

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

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

**Sorting algorithms **(3 hours)

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

**Stacks, queues, and priority queues **(4 hours)

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

**Map (or Dictionary) ADT **(9 hours)

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

**Graphs **(5 hours)

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

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

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

General description

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

Students will learn to

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

Logistics

Audience

- 2B Computer Science students

Normally available

- Fall, Winter, and Spring

Related courses

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

For official details, see the UW calendar.

Software/hardware used

- UNIX, C++

Typical reference(s)

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

Required preparation

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

Analytical:

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

Computational and algorithmic:

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

Learning objectives

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

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

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

Typical syllabus

**Introduction and review **(3 hours)

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

**Stacks, queues, and priority queues **(3 hours)

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

**Sorting and analysis of randomized algorithms **(5 hours)

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

**Search trees **(5 hours)

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

**Hashing **(5 hours)

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

**Range search and multidimensional dictionaries **(5 hours)

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

**Algorithms and data structures for text processing **(8 hours)

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

CS 246: Object-Oriented Software Development

General description

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

Logistics

Audience

- 2A Computer Science students

Normally available

- Fall, Winter, and Spring

Related courses

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

For official details, see the UW calendar.

Software/hardware used

- Unix, C++

Typical reference(s)

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

Required preparation

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

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

Learning objectives

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

- Design, implement, test, and debug C++ programs to solve problems requiring hundreds of lines of code, making appropriate use of

- types, variables, arrays, strings, and dynamic memory; loops, conditionals, and other control structures; structures, unions, and enumerations; procedures and functions; the preprocessor; formatted and unformatted I/O
- classes, objects, overloading, and single inheritance
- a subset of the STL, including vector, list, and map
- assertions and exceptions
- basic software development tools, including makefiles, a shell, a revision control system, and a debugger
- test suites for unit testing, white and black box testing
- structured programming, incremental development
- interface design, abstractions, information hiding, cohesion and coupling
- a subset of UML to specify classes, objects and relationships between them
- a selection of design patterns, including adapter and template

- Explain the following properties of the memory model used in C++, including their impact on time and space efficiency when designing code: bytes vs. words, memory as an array, run-time stack and stack frames, memory allocation on the heap vs. automatic allocation on the stack, pointers as memory addresses, the representation of objects in memory
- Define and explain at an elementary level basic software-engineering concepts, including the water-fall model and other development methodologies

Typical syllabus

**Shell **(4 hours)

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

**C++ **(16 hours)

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

**Unix tools **(8 hours)

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

**Software engineering **(8 hours)

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

CS 247: Software Engineering Principles

General description

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

Logistics

Audience

- 2B Software Engineering students

Normally available

- Spring

Related courses

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

For official details, see the UW calendar.

Software/hardware used

- UNIX, C++, Java

Typical reference(s)

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

Required preparation

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

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

Learning objectives

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

__Design and implement data abstractions (ADTs, polymorphic objects, generic functions) in C++____Critique designs with regards to cohesion, coupling, generality, robustness, information hiding____Create software designs that are modular, general, robust, flexible____Express software designs and behaviour using basic UML models____Express the structure of an OO program as a class model____Express the state of a dynamic data structure as an object model____Express interactions between objects using a sequence diagram____Develop and test programs incrementally____Test and debug programs systematically____Use simple software tools effectively, including makefiles, gdb, version control__

__Typical syllabus__

__Module Design (12 hours)__

__ADT design, function and operator overloading____Modules and interfaces____Namespaces____Interface specification__

__Object-Oriented Design and Programming (12 hours)__

__Composite objects____OO design principles and patterms____Multiple inheritance and mixins__

__Software Engineering and Tools (5 hours)__

__UML modelling____Incremental development (make)____Testing and debugging (gdb)____Version control (e.g., svn)__

__Generic Programming (5 hours)__

__STL algorithms____Iterators__

General description

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

Logistics

Audience

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

Normally available

- Fall, Winter, and Spring

Related courses

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

For official details, see the UW calendar.

Typical reference(s)

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

Required preparation

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

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

Learning objectives

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

- Design simple combinational and sequential hardware at the logic gate level in order to implement simple algorithms and computations, such as addition, multiplication, and data-path control for processors
- Describe number systems used by computer hardware, including IEEE floating point and two’s complement, at the bit level, including being able to
- Operate on these number representations and compute their values
- Explain the limits of these representations, including rounding error and overflow conditions

- Explain how machine language is executed by hardware, and describe a simple processor architecture for executing a RISC machine language
- Explain some simple processor implementation optimization techniques, in particular pipelining, and how differences in code ordering can impact performance for processors using these optimizations, including being able to
- Analyze performance of a code sequence executing on a pipelined architecture
- Reorganize (given) code in order to improve performance on a pipelined architecture

- Explain basic cache and virtual-memory architectures, and how they can impact performance, including being able to
- Analyze a memory-access trace relative to these architectures in order to predict performance
- Compute average-case performance given miss probabilities and miss penalties
- Identify specific cases (such as loop index ordering) that can impact performance, and reorganize such code to improve performance

- Describe a basic multicore and multiprocessor architecture and explain the key factors that will affect performance and scalability of programs written for these architectures

Typical syllabus

**Introduction **(2 hours)

- Overview of computer organization
- Measuring performance

**Digital logic design **(6 hours)

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

**Data representation and manipulation **(6 hours)

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

**Basic processor design **(5 hours)

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

**Pipelining **(5 hours)

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

**Input/Output **(3 hours)

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

**Memory Hierarchies **(3 hours)

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

**Multi-processing **(3 hours)

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