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.
Last modified: Wednesday, 15-Feb-2012 10:23:44 EST
