CS 146 | SCS | UW

Revised August 19, 2011

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.