CS 134 | SCS

This course introduces students to the three basic paradigms of computer science: design (from engineering), experiment (from science), and proof (from mathematics). These are introduced through study of some elementary data structures and algorithms, together with the programming mechanisms and methodologies required to implement and use them.

Intended Audience

A choice of CS 134 or CS 136 is required for all academic plans in the Faculty of Mathematics. CS 134 is the second course in both the Programming-Basics Sequence (following CS 125) and the Objects-First Sequence (following CS 133). Students with extensive programming experience (ICS4M or equivalent) are encouraged to take the Functional-First Sequence, though they are also eligible to take CS 134 in 1A. Additional information about choosing a first CS course is available.

Related Courses

Prerequisites: CS 125 or 132 or 133/130; Honours Mathematics or Software Engineering students only.

Hardware/Software

Used in Course: An integrated development environment for Java running on networked personal computers.

Assumed Background: Significant experience with an imperative language and experience with object-oriented programming, including object-oriented design.

References

Data Abstractions and Problem Solving with Java, updated edition by F. Carrano and J. Prichard, Addison Wesley, 2004. Course notes required.

Schedule

3-hour lectures, 1-hour tutorials and 2-hours laboratory each week. Normally available in Fall, Winter, and Spring. Also offered at St. Jerome's in the Winter.

Outline

Algorithm Design, Correctness and Efficiency (9-12 hours)

Concepts and tools of algorithm and program design. Pre- and post-conditions, assertions, correctness. Efficiency with respect to space and time, analysis using O-notation. Examples based on vectors, sorting, and Mealy machines.

Recursion (6-9 hours)

Recursive definitions and algorithms. Binary search. Inductive proofs of recursively defined properties. Recursive sorting algorithms.

Abstract Data Types (12-15 hours)

Object-oriented methods to support abstract data types. Iterators. Implementations of sets and tables using arrays and linked lists. 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. Binary search trees.

Discipline of Computer Science (3 hours)

Retrospective on software principles and practice and accompanying theory. Social impacts of computer technology. Responsibility and liability.