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 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.
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 gcc in a command-line environment. The use of a text editor such as vim is recommended. Students using only Windows for development should install Cygwin.
C Programming: A Modern Approach 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.
Three hours of lecture per week, plus a one-hour tutorial.
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. 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.
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.
Structures in C. Memory allocation and deallocation. Lists and queues in C. Safety and usability issues.
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 concepts covered in this course.
David R. Cheriton School of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1
Tel: 519-888-4567 x33293
Fax: 519-885-1208
Contact | Feedback: cs-uops@cs.uwaterloo.ca | David R. Cheriton School of Computer Science | Faculty of Mathematics
Last modified: Friday, 21-Oct-2011 10:59:03 EDT
