This course covers the principles of object-oriented program design through the study of elementary data structures and algorithms.
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 the same level of experience as 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 Java, with Scheme used for some initial examples. Student labs are equipped with an integrated development environment for Java running on networked personal computers, versions of which will be available for personal computers owned by students and running Windows, Mac OS, Unix/X, or Linux.
How To Design Class Hierarchies by Felleisen, Flatt, Findler, Gray, Krishnamurthi, and Proulx. This book is available in its entirety on the Web.
The Object of Data Abstraction and Structures Using Java by Riley, Addison-Wesley, 2003.
Course notes are also required.
Three hours of lecture per week, plus a two-hour laboratory. Normally available in Winter.
From Scheme to Java (15 hrs)
Objects, classes, behaviours, constructors, methods, accessors, modifiers. Interpretation and compilation. Assignment, control structures, arrays, ArrayList. Subclasses, superclasses, inheritance, exceptions, interfaces.
Abstract Data Types (9 hrs)
Object-oriented methods to support abstract data types. Implementations of sets and tables using arrays and linked lists.
Elementary Data Structures and their Analysis (12 hrs)
Algorithm analysis. Abstract definitions, properties, and various implementations for stacks, queues, and trees. Applications, including implementation of nested procedure calls, depth-first and breadth-first traversals, and discrete event simulation. Collections.
History of Computer Science (1.5 hr)
History of concepts covered in this course.