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

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:

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

References

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