This course covers the principles of program design and the fundamentals of computation through functional evaluation.
CS 135 is for Mathematics students who would prefer a more conceptual treatment of introductory computer science in a simple language that is educationally effective but not commercially relevant. While the course is designed to be taken by those with no prior programming experience, students with prior experience will also find it relevant, due to its unusual focus. It is suitable for both CS majors and non-majors, and can be substituted for CS 133 in all degree requirements.
Prerequisites: Full-time degree registration in the Faculty of Mathematics.
Antirequisites: None.
Successor: CS 136.
Used in course: Programs are written in subsets of the language Scheme. 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.
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.
Course notes are also required.
Three hours of lecture per week, plus a two-hour laboratory. Normally available in Fall.
Simple Forms of Data (3 hrs)
Numbers, arithmetic, function definition and composition, design recipes, conditional expressions, symbols.
Structured Data (3 hrs)
Structure definitions, constructors, selectors, data definitions, type predicates, functions for mixed data.
Syntax and Semantics (1 hr)
Vocabulary and grammar of the beginning student language.
Arbitrarily Large Data: Lists (5 hrs)
Definition of lists, designing functions to process and produce lists, recursive definition of natural numbers, recursive data definitions.
Non-Linear Structures (6 hrs)
Multi-clausal recursive data definitions, trees, mutually referential data definitions, design methods for complex data, iterative refinement, multiplexing.
Abstraction Through Local Definitions (6 hrs)
Encapsulation, block structure, binding, functional abstraction, filters, polymorphism, generic functions, parametric data definitions, functions as data, functions that produce functions, anonymous functions.
Generative Recursion (6 hrs)
Generative versus structural recursion, backtracking algorithms, costs of computing, vectors, accumulators.
Changing The State of Variables (6 hrs)
Assignment, memory, initializers, state changes from recursion, mutable structures, semantics of advanced student language.
History of Computer Science (1.5 hr)
Babbage, Hilbert, Godel, Church, Turing. Early development of electronic computers and programming languages. History of concepts covered in this course.