This course provides a mathematical foundation for formal study of algorithms and the theory of computing. It also introduces functional programming, a powerful computing paradigm that is distinct from the imperative and object-oriented paradigms introduced in Computer Science 167. Students will practice formal reasoning over discrete structures through two parallel modes: mathematical proofs and computer programs. We will introduce sets and lists, Boolean logic, and proof techniques. We will explore recursive algorithms and data types along with mathematical and structural induction. We consider relations and functions as mathematical objects and develop idioms of higher-order programming. We consider applications useful in computer science, particularly counting sets. May be elected as Mathematics 220.
Computer Science 167 or 270; and Mathematics 124 or 125.