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.
CS 136 is for Mathematics students who have taken CS 135.
Prerequisites: Full-time degree registration in the Faculty of Mathematics; CS 135.
Antirequisites: CS 134.
Programs are to be written in Racket and C. 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. C program compilation environments have yet to be finalized.
How to Design Programs by Felleisen, Flatt, Findler, and Krishnamurthi (MIT Press). This book is available in its entirety on the Web.
C Programming: A Modern Approach by K.N. King (W.W. Norton & Company).
Lecture slides will be made available online.
Three hours of lecture per week, plus a one-hour tutorial.
Mutation, interaction, and encapsulation (7.5 hours)
Mutation of identifier-value bindings in Racket. Sequencing of statements. Basic I/O in Racket. State encapsulation (primitive objects). Semantics of structure and list mutation in Racket. 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 Racket. 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 Racket and C. Logarithmic-time list operations. Vectors/arrays in Racket 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 Racket. 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 hr)
History of concepts covered in this course.