This course examines elementary data structures and algorithms using the functional, object-oriented, and imperative paradigms of computation, and discusses issues surrounding the effective use of programming languages in "real-world" environments.
CS 136 is for Mathematics students who have taken CS 135, in which a functional approach was used. It is designed to bring students to a level of expertise comparable to CS 134, and can be substituted for CS 134 in all degree requirements.
Prerequisites: Full-time degree registration in the Faculty of Mathematics; CS 135.
Antirequisites: CS 134.
Used in course: Programs are 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 programming will be done in command-line environments on these systems using the gcc compiler.
How to Design Programs by Felleisen, Flatt, Findler, and Krishnamurthi, MIT Press. This book is available in its entirety on the Web.
The C Programming Language by Kernighan and Ritchie, second edition, Prentice-Hall.
Course notes are also required.
Three hours of lecture per week, plus a one-hour tutorial. Normally available in Winter.
Encapsulation (6 hours)
Objects as encapsulated state. Semantics of structure and list mutation in Scheme. Box-and-pointer diagrams. An object/class system for Scheme.
Abstract data types (3 hours)
Definition and implementation of ADTs (Set, Table, Stack) using algorithms from CS 135.
Efficiency (4.5 hours)
O-notation and asymptotic time bounds. Logarithmic-time list operations. Vectors (constant-time access) and their uses. Linear and binary search. A logarithmic-time dictionary structure.
Program scalability (3 hours)
A module system for Scheme. Libraries. Separate compilation. Contracts. Type issues.
Interaction and persistence (3 hrs)
Console and file I/O.
An introduction to C (6 hours)
Box-and-pointer diagrams revisited. The memory model. Explicit typing. Assignment. Functions and procedures. Stacks and frames. Basic I/O. Control flow. Arrays and pointers. Reference parameters.
Imperative algorithmics (3 hours)
Asymptotics of nested loops. Sorting algorithms revisited. Reachability and depth-first search. Garbage collection.
Memory management (6 hours)
Allocation and deallocation. Lists and trees revisited. Queues. Breath-first search. Safety and usability issues. Strong typing in other languages. Foreign interfaces.
History of Computer Science (1.5 hr)
History of concepts covered in this course.