CS 135 | SCS

This course covers the principles of program design and the fundamentals of computation through functional evaluation.

Intended Audience

CS 135 is for 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.

Related Courses

Antirequisites: CS 115, 121, 122, 123, 125, 131, 132, 133, 134, 137, 138, 145, CHE 121, CIVE 121, ECE 150, GENE 121, PHYS 139, SYDE 121

Hardware and Software

Used in course: Programs are written in subsets of the language Scheme. Student labs are equipped with the DrRacket 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.

References

How To Design Programs by Felleisen, Findler, Flatt, and Krishnamurthi, MIT Press, 2003. This book is available in its entirety on the Web, though students are encouraged to purchase a physical copy.

Schedule

Outline

Simple Forms of Data (3 hours)

Numbers, arithmetic, function definition and composition, design recipes, conditional expressions, symbols.

Structured Data (3 hours)

Structure definitions, constructors, selectors, data definitions, type predicates, functions for mixed data.

Syntax and Semantics (1.5 hr)

Arbitrarily Large Data: Lists (6 hours)

Definition of lists, designing functions to process and produce lists, recursive definition of natural numbers, recursive data definitions.

Non-Linear Structures (6 hours)

Multi-clausal recursive data definitions, trees, mutually referential data definitions, design methods for complex data, iterative refinement, multiplexing.

Abstraction Through Local Definitions (9 hours)

Encapsulation, block structure, binding, functional abstraction, filters, polymorphism, generic functions, parametric data definitions, functions as data, functions that produce functions, anonymous functions, abstract list and tree functions (definition and use).

Generative Recursion (6 hours)

Generative versus structural recursion, backtracking algorithms, accumulators and accumulative recursion.

History of Computer Science (1.5 hours)

Babbage, Hilbert, Godel, Church, Turing. Early development of electronic computers and programming languages. History of concepts covered in this course.