CS 136 Elementary Algorithm Design and Data Abstraction

Objectives

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.

Intended Audience

CS 136 is for Mathematics students who have taken CS 135.

Related Courses

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.

Hardware and Software

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 Clang/LLVM in the RunC environment. gedit is recommended for use as an editor.

References

C Programming: A Modern Approach, 2nd edition 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.

Schedule

Three hours of lecture per week, plus a one-hour tutorial.

Outline

Mutation, interaction, and encapsulation (7.5 hours)

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 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 Scheme. 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 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.

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 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 Computer Science (1.5 hour)

History of concepts covered in this course.