A combined course on functional programming and formal proof. Students write programs over a variety of data structures, proving their programs correct with respect to precise logical specifications. Programming topics (and proof topics) range over: recursion (induction); combinatorics; algebraic data types, from lists to trees to abstract syntax trees (structural induction); parsers and interpreters (soundness properties); regular expressions (set theory and language theory). Prerequisites: any CSCI 051x course or Computer Science AP Exam-A with a score of 5.

Key topics include abstract data types (including stacks, queues, trees, priority queues and dynamic dictionaries), analysis of algorithms (including worst-case, average-case and amortized analysis) and program verification. Extensive practice in Java. Serves the same role as HM 70 as a prerequisite for upper-division computer science courses at any of The Claremont Colleges.

This class investigates models of computation such as finite-state automata and Turing machines, formal languages such as context free grammars, and computability. Connections to applications such as lexical analysis and parsing will be explored. Students will learn to read and to construct formal proofs in this context.

Data representations, machine level representation of programs, processor architecture, program optimizations, the memory hierarchy, linking, exceptional control flow, performance measurement, virtual memory, system-level I/O and basic concurrent programming. These concepts are supported by a series of hands-on lab assignments.

Algorithm design, computer implementation and analysis of efficiency. Discrete structures, sorting and searching, parsing, pattern matching and data management. Reducibility and theoretical limitations.

Colloquium presentations and discussions of topics in computer science and closely related disciplines. For junior Computer Science majors only.