CS 105: Introduction to Computer Programming 1

General description

This course introduces practical computer programming to students who don’t have previous programming experience. Students learn programming concepts by creating interactive visualizations, simple games, and image processing effects. They also explore fundamental imperative programming language concepts, such as variables, conditionals, loops, functions, events, and arrays. Students learn general skills, such as coding style, modular design, testing, and debugging. In addition, they explore media computation topics, such as two-dimensional graphics drawing, human input, animation, and image processing.

Logistics

Audience

Students in the Global Business and Digital Arts (GBDA) program
Fine Arts – Studio majors taking the Digital Art Specialization
Students interested in learning how to program

Normally available

Fall

Related courses

Successors: CS 106
Conflicts: CS 115, CS 135, CS 145, CS 137, and other courses in introductory computer science

For official details, see the UW calendar.

Software/hardware used

Processing programming language and integrated development environment

Typical reference(s)

Daniel Shiffman, Learning Processing (second edition), Morgan Kaufmann

Required Preparation

At the start of the course, students should be able demonstrate a basic understanding of mathematical concepts. No programming background is expected.

Learning objectives

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

Write interactive programs that draw shapes and respond to mouse and keyboard input using the Processing programming language
Understand and apply concepts, such as variables, conditionals, loops, functions, and arrays
Read simple pieces of code to explain their function, trace code execution, and identify related errors

Typical syllabus

Introduction (3 hours)

What is an algorithm? What is code?
Code syntax and syntax errors

Drawing and attributes (3 hours)

Two-dimensional coordinates, drawing functions, commenting practices, the concept of sequential control flow
Drawing attributes and the concept of program state
Colour representation and hexadecimal numbers

Interaction and variables (3 hours)

Draw loop and the concept of program events
Variable declaration and initialization, variable types, and the concept of computer memory

Conditionals (3 hours)

Boolean logic and relational expressions
If-then-else statements
Numeric representation and binary numbers
Bounds detection for hit testing

Loops (6 hours)

While loop and for loop
Variable scope
Remapping variables
Nested loops

Functions (3 hours)

Writing custom functions, function parameters, return values
Variable shadowing

Arrays (4.5 hours)

Arrays, array elements, indexing
Array operation idiom

Objects and program design (4.5 hours)

Using classes and objects for program encapsulation
Modularity, testing, and debugging

Images, video, and libraries (6 hours)

Loading and displaying images, image pixels
Image processing and computational complexity
Video capture and processing
Using libraries, e.g., loading and playing sounds

CS 106: Introduction to Computer Programming 2

General description

This course, together with its predecessor CS 105, offers a comprehensive introduction to practical computer programming to students who don’t have previous programming experience. While the main theme of CS 105 is to develop basic skills in imperative programming (variable declarations, control flow, defining functions, basic object-oriented programming), in CS 106 we explore more general applications of programming in contexts of interest to visual artists and designers.

Logistics

Audience

Required by students in the GBDA program and available to students from other programs

Normally available

Winter

Related courses

CS 105

For official details, see the UW calendar.

Software/hardware used

Processing programming environment

Typical reference(s)

Shiffman, Daniel, Learning Processing 2nd edition, Morgan Kaufmann

Required preparation

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

Declare variables in an imperative programming language and read and modify the values of those variables
Write simple control flow structures, such as if statements, while loops, and for loops
Write simple helper functions that capture repeated sub-computations
Declare arrays and read and write elements in them
Produce simple interactive sketches that draw shapes and respond to mouse and keyboard input

Learning objectives

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

Use strings and perform basic text processing operations
Write programs that use basic user interface elements (buttons, sliders) and that support direct manipulation of simple shapes (circles, rectangles)
Write a short recursive function
Write programs that read data from external files and/or the internet and that store data in external files
Use libraries to parse tabular data (CSV) and general tree-structured data (JSON)

Typical syllabus

Processing recap (3 hours)

Review of programming concepts from CS 105, in terms of the basic structure of the Processing language: types, declarations, expressions, statements, and functions

Arrays (3 hours)

High-level operations on arrays, including appending, concatenation, and removal
Built-in array manipulation functions

Strings (3 hours)

String class
Working with characters and strings
String comparisons
Printing and displaying text

Input and output (3 hours)

Loading files in various formats (text, images, illustrations) into Processing and writing files

Advanced shapes (3 hours)

Drawing fancy shapes with beginShape() and endShape() using the PShape class

User interfaces (3 hours)

Model-view-controller architecture
Direct manipulation interfaces
User interface toolkits
ControlP5 library in Processing

Geometric context (3 hours)

Use of translate(), rotate(), and scale() to modify a program’s coordinate system
Building a hierarchy of transformations using pushMatrix() and popMatrix()
Order of operations

Recursion and fractals (3 hours)

Iterated function systems as a demonstration of recursion

Randomness and noise (3 hours)

Random() function in detail
Pseudorandomness
Applications of randomness
Introduction to noise()

Text processing (3 hours)

Decomposing text into tokens
Regular expressions
Unicode
Working with dates and times

Structured data processing (3 hours)

Dealing with table-structured (CSV) and tree-structured (JSON) data
Processing live data acquired from web APIs

CS 115: Introduction to Computer Science 1

General description

This course introduces students to key concepts in the field of Computer Science through the use of a functional programming language.

Logistics

Audience

1A students in the Faculty of Mathematics
Students interested in pursuing a Computer Science minor
Students interested in learning more about Computer Science

Normally available

Fall, Winter, and Spring

Related courses

Predecessors: None
Successors: CS 116
Co-requisites: None
Conflicts: CS 135, CS 145, CS 137, and other courses in introductory computer science

For official details, see the UW calendar.

Software/hardware used

Racket programming language
DrRacket programming environment

Typical reference(s)

M. Felleisen, R. Findler, M. Flatt, S. Krishnamurthi, How To Design Programs, MIT Press (First edition)

Required preparation

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

Demonstrate a basic understanding of mathematical concepts, including functions

No programming background is assumed.

Learning objectives

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

Given a clear and concise statment of a problem or task, write a program from scratch of up to fifty lines of properly-formatted, tested, and documented Racket code to solve the problem or carry out the task
Use elementary data structures, such as lists and trees, in programs
Use abstract list functions in programs

Typical syllabus

An introduction to functional progamming (24 hours)

Basics of Racket: function application and definition in mathematics and in Racket, formal grammar and syntax, the substitution model, primitive data types (numbers, strings, characters, Boolean)
Conditional expressions, including nested conditionals
Design recipe for moving from problem description to code that processes data
Structures and their semantics in the substitution model
Lists of primitive types, lists of structures, and nested lists
Structural recursion on lists and integers and on two recursive values using the design recipe

Data abstraction (7.5 hours)

Basic dictionaries (number keys and string values) implemented using association lists and binary search trees
Binary trees and general trees
Applications, including the evaluation of arithmetic and Racket expressions (involving the use of mutual recursion)

Functional abstraction (4.5 hours)

Functions as values, including parameters to other functions
Abstract list functions (with a focus on map, filter, foldr, and build-list)
Local definitions for both constants and functions
Scope
Lambda

CS 116: Introduction to Computer Science 2

General description

CS116 continues the development started in CS115, transitions to imperative programming, and introduces important issues in Computer Science.

Logistics

Audience

1B students in the Faculty of Mathematics
Students interested in pursuing a Computer Science minor
Students interested in learning more about Computer Science

Normally available

Fall, Winter, and Spring

Related courses

Predecessors: CS 115, CS 135
Successors: CS 136, CS 230, CS 234, CS 330
Co-requisites: None
Conflicts: CS 137, CS 138

For official details, see the UW calendar.

Software/hardware used

Python programming language
WingIDE programming environment or alternate

Typical reference(s)

A. Downey, Think Python: An Introduction to Software Design, O’Reilly Media

Required preparation

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

Given a clear and concise statment of a problem or task, write a program from scratch of up to fifty lines of properly-formatted, tested, and documented Racket code to solve the problem or carry out the task
Use elementary data structures, such as lists and trees, in programs
Use abstract list functions in programs

Learning objectives

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

Given a clear and concise statement of a problem or task, write a program from scratch of up to a hundred lines of properly-formatted, tested, and documented Python code to solve the problem or carry out the task
Use higher-order functions to improve the readability and efficiency of programs
Use various forms of recursion (structural, accumulative, generative) in programs
Use various forms of iteration (for, while) in programs
Describe the basic memory model for mutation of basic types, lists, and objects in Python
Distinguish between constant, linear, quadratic and exponential running times of algorithms
Explain the relative advantages and disadvantages of lists and dictionaries
Write useful Python programs using console and file input and output for practical tasks

Typical syllabus

Introduction to imperative programming (15 hours)

Common features of imperative languages
Basics of Python: assignment and introduction to mutation, basic console output and keyboard input, basic program structure, defining and using functions
Relating concepts from Racket to Python: lists of basic types, if statements, including nested conditionals; basic structural recursion; abstract list functions and lambda
Basic Python memory model, including lists

More advanced concepts from imperative programming (15 hours)

Additional forms of recursion: accumulative and generative
Iteration: bounded (for loop), guarded (while loop); simple and nested iteration; applications, including linear and binary search algorithms
Investigating several sorting algorithms
Dictionaries
Basic use of classes (in comparison to Racket structures), introduction to object-oriented principles in Python, and mutation of objects
Functions as parameters: extending the design recipe to include polymorphism
File input and output: basic and structured file processing, basic exception handling (try-except block)
Additional topics, possibly including programming with real world data, web pages, etc.

Issues in Computer Science (6 hours)

Basic introduction to run-time analysis and simple run-time classes (constant, logarithmic, linear, linearithmic, quadratic, exponential) through studied algorithms
Discussion of design issues related to data structures (for example, choosing between lists and dictionaries) and effects on complexity and memory requirements

CS 135 Designing Functional Programs

Objectives

This course covers the principles of program design and the fundamentals of computation through functional evaluation.

Intended Audience

CS 135 is for students who would prefer a more conceptual treatment of introductory computer science in a simple language that is educationally effective but not commercially relevant. While the course is designed to be taken by those with no prior programming experience, students with prior experience will also find it relevant, due to its unusual focus. It is suitable for both CS majors and non-majors.

Related Courses

Antirequisites: CS 115, 121, 122, 123, 125, 131, 132, 133, 134, 137, 138, 145, CHE 121, CIVE 121, ECE 150, GENE 121, PHYS 139, SYDE 121

Successor: CS 136.

Hardware and Software

Used in course: Programs are written in subsets of the language Scheme. Student labs are equipped with the DrRacket integrated development environment running on networked personal computers. Versions for Windows, Mac OS, Unix/X and Linux are freely downloadable for use on computers owned by students.

References

How To Design Programs by Felleisen, Findler, Flatt, and Krishnamurthi, MIT Press, 2003. This book is available in its entirety on the Web, though students are encouraged to purchase a physical copy.

I-Clicker RF Response Remote (Required) .

Schedule

Three hours of lecture per week, plus a tutorial. Available in Fall and Winter.

Outline

Simple Forms of Data (3 hours)

Numbers, arithmetic, function definition and composition, design recipes, conditional expressions, symbols.

Structured Data (3 hours)

Structure definitions, constructors, selectors, data definitions, type predicates, functions for mixed data.

Syntax and Semantics (1.5 hr)

Vocabulary and grammar of the beginning student language.

Arbitrarily Large Data: Lists (6 hours)

Definition of lists, designing functions to process and produce lists, recursive definition of natural numbers, recursive data definitions.

Non-Linear Structures (6 hours)

Multi-clausal recursive data definitions, trees, mutually referential data definitions, design methods for complex data, iterative refinement, multiplexing.

Abstraction Through Local Definitions (9 hours)

Encapsulation, block structure, binding, functional abstraction, filters, polymorphism, generic functions, parametric data definitions, functions as data, functions that produce functions, anonymous functions, abstract list and tree functions (definition and use).

Generative Recursion (6 hours)

Generative versus structural recursion, backtracking algorithms, accumulators and accumulative recursion.

History of Computer Science (1.5 hours)

Babbage, Hilbert, Godel, Church, Turing. Early development of electronic computers and programming languages. History of concepts covered in this course.

CS 136 Elementary Algorithm Design and Data Abstraction

Objectives

This course examines elementary data structures and algorithms using the functional and imperative paradigms of computation, and discusses issues surrounding the effective use of programming languages in “real-world” environments.

Intended Audience

CS 136 is for Mathematics students who have taken CS 135.

Related Courses

Prerequisites: Full-time degree registration in the Faculty of Mathematics; CS 116 or at least 60% in CS 135 or CS 145 taken fall 2011 or later.

Antirequisites: CS 134, 137, 138, 145 taken fall 2010 or earlier.

Hardware and Software

Programs are to be written in Scheme and C. Student labs are equipped with the DrScheme integrated development environment running on networked personal computers. Versions for Windows, Mac OS, Unix/X and Linux are freely downloadable for use on computers owned by students. C programs will be compiled using Clang/LLVM in the RunC environment. gedit is recommended for use as an editor.

References

C Programming: A Modern Approach, 2nd edition by K.N. King (W.W. Norton & Company).

How To Design Programs by Felleisen, Findler, Flatt, and Krishnamurthi, MIT Press, 2001. This book is available in its entirety on the Web, though students are encouraged to purchase a physical copy.

Lecture slides will be made available online.

Schedule

Three hours of lecture per week, plus a one-hour tutorial.

Outline

Mutation, interaction, and encapsulation (7.5 hours)

Mutation of identifier-value bindings in Scheme. Sequencing of statements. Basic I/O in Scheme. State encapsulation (primitive objects). Semantics of structure and list mutation in Scheme. Box-and-pointer diagrams.

The memory model and introduction to C (7.5 hours)

The memory model. Variable declaration, assignment and infix expressions in C. Basic I/O in C. Compilation. Pointers, addresses, garbage collection, and memory reuse in Scheme. Modelling functions, procedures, and recursion in C. The limits of recursion in C. Loop constructs.

Efficiency (7.5 hours)

O-notation. Analysis of simple programs in Scheme and C. Logarithmic-time list operations. Vectors/arrays in Scheme and C and their uses. Linear and binary search. Hash tables and their uses. Pointers and strings in C.

Memory management (6 hours)

Structures in C. Memory allocation and deallocation. Lists and queues in C. Safety and usability issues.

Abstract data types (6 hours)

Information hiding in Scheme. A module system. Libraries. Definition and implementation of ADTs. Separate compilation in C. Overview of approaches to abstraction and code reuse in other languages (Java, C++, ML, Haskell).

History of Computer Science (1.5 hour)

History of concepts covered in this course.

CS 137 Programming Principles

Objectives

This course introduces software engineering students to elementary data structures, and to the functional programming paradigm.

Intended Audience

Level 1A Software Engineering undergraduates. It is assumed that students have experience developing well-structured, modular programs.

Related Courses

Antirequisites: CS 115, 135, 136, 145, CHE 121, CIVE 121, ECE 150, GENE 121, PHYS 239, SYDE 121

Successor: CS 138.

Hardware and Software

Used in course: An integrated development environment (IDE) for C++ (such as xCode for Mac OS X).

References

C Programming: A Modern Approach 2nd ed. Author: K.N. King

Schedule

Three hours of lecture per week, plus a two-hour lab and a one-hour tutorial. Normally available in Fall only.

Outline

Introduction and review (6 hours)

Review of hardware and software, problem solving and programming, including declarations, selection and looping constructs, I/O.

Subprograms (6 hours)

Functions. Scoping. Parameter passing, by value and by reference. Top-down design. Programming with stubs.

Structured Data (7.5 hours)

Arrays. Structures. Arrays of structures. Multidimensional arrays. Appropriate choice of data structures. String processing and tokenization.

Recursion (3 hours)

Introduction to recursive procedures and functions.

Analysis (1.5 hours)

Introduction to O-notation, space and time efficiency, and complexity.

Sorting Algorithms (4.5 hours)

Algorithm design and efficiency, through discussion of of elementary sorting algorithms (insertion sort, selection sort) and advanced sorting algorithms (mergesort, quicksort, heapsort).

Pointers and Dynamic Structures (6 hours)

Introduction to pointers, memory allocation and deallocation, singly and doubly-linked lists.

History of Computer Science (1.5 hours)

Babbage, Hilbert, Godel, Church, Turing. Early development of electronic computers and programming languages. History of concepts covered in this course.

CS 138 Introduction to Data Abstraction and Implementation

Objectives

This course introduces Software Engineering students to elementary data structures and their implementation, and to the object-oriented programming paradigm.

Intended Audience

Software Engineering undergraduates who have taken SE 1A. It is assumed that students have experience programming in an imperative language such as C or C++.

Related Courses

Prerequisite: CS 137

Antirequisites: CS 116, 135, 136, 145, 146

Successor: CS 241.

Hardware and Software

Used in course:

The UNIX operating system, the Bash shell, and command-line tools such as the g++ compiler.

References

Absolute C++, 6th edition, by Walter Savitch and Kenrick Mock. Pearson.

Schedule

Three hours of lecture per week, plus a one-hour tutorial. Normally available in Winter only.

Outline

Introduction (3 hours)

Operating system and Unix concepts, programming language concepts.

Introduction to C++ concepts (3 hours)

C++ basics, basic types, IO, use of simply library elements (string, vector).

ADT and their implementations as linked structures (12 hours)

The stack, queue, and priority and queue ADTS; the linked list, sorted linked list; Trees, binary trees, binary search trees; the C/C++ memory model: pointers vs references, stack vs freestore; implementing and travesing linked structures; recursion and stack frams; recursive vs iterative solution to ADTs; space and time complexity of solutions; simple testing and debugging strategies.

Object-based computing (9 hours)

Interface vs implementation; class definitions, instantiation, object construction and destruction; object vs pointers to objects; interface design and abstraction, responsibility allocation; the adapter design pattern.

Introduction to object-oriented programming (9 hours)

Introduction to inheritance and its implementation in C++; introduction to generics, type parameterization, and C++ templates; the template method design pattern; use of generic data containers and the Standard Template Library; design heuristic and strategies for object-oriented programming.

CS 146: Elementary Algorithm Design and Data Abstraction (advanced version)

(Emphasized text represents additional material not found in CS 136.)

Goals

To familiarize students with key concepts in introductory computer science from an imperative perspective and to contrast this with the functional perspective taken in CS 145;
To allow students to complete the CS portion of their Math core requirements and, if desired, to continue on to second-year core courses in CS;
To provide top students with appropriate challenges and enrichment and to explore topics in greater depth than possible in CS 136.

Logistics

Intended for 1B students in the Faculty of Mathematics. Normally available Winter.

Related courses (see calendar for official details)

Predecessors: CS 145 with a grade of at least 75%.

Successors: CS 246, CS 245, CS 251.

Conflicts: CS 116, 136, 137, 138, 145 taken fall 2010 or earlier.

Software used: Racket (dialect of Scheme), Unix-like development environment (Linux, OS X, Cygwin), C compiler.

Typical Reference(s)

C Programming: A Modern Approach (second edition) by K.N. King (W.W. Norton & Company).

The C Programming Language (second edition) by B. Kernighan and D. Ritchie (Prentice-Hall).

Required preparation

A mark of 75% or greater in CS 145. Students who complete CS 145 with a mark of less than 75% may apply for instructor consent to take CS 146. Students who complete CS 135 with an outstanding record may also apply for instructor consent. Prior experience in imperative programming (in particular using C or C++) will be considered in such requests, but will not be the main criterion; aptitude is still of primary importance.

Learning objectives

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

given a clear and concise statement of a problem or task, write a program from scratch of up to two hundred lines of properly-formatted and documented C code to solve the problem or carry out the task;
use elementary data structures such as lists and trees in such programs, with proper attention to explicit allocation and deallocation of memory;
be able to write programs in both Scheme and C that obtain input from external sources and/or send output to external sources (interaction, files, redirected files) and whose I/O behaviour conforms to precise specifications;
analyze the running time and space requirements of such programs and describe examples of data that demonstrate that the analysis cannot be improved.

Typical syllabus

Introduction to C and elementary mutation in Scheme

Command-line interfaces. The memory model. Variable declaration, assignment and infix expressions in C. Basic I/O in C. Compilation. Mutation of identifier-value bindings in Scheme. Modelling functions, procedures, and recursion in C. Loop constructs. Algorithm analysis in C. File I/O in C and Scheme. Program organization and testing methods.

Memory management

Structures in C. Memory allocation and deallocation. Mutable structures, sharing, and garbage collection in Scheme. Space analysis in C and Scheme.

Mutable ADTs

Mutable lists, queues, deques, and trees in C. Time-space tradeoffs among mutable and immutable ADT implementations.

Low-level abstractions

Pointer arithmetic in C. Arrays in C and vectors in Scheme. Search, sorting, and graph algorithms revisited. Strings in C. Elementary hashing. Bitwise operations. Processing binary data. Libraries in C and Scheme.

Implementing high-level abstractions

Interpreting Scheme in C. Compiling Scheme to C. Compiling to virtual machines.