## Course Description

This course covers the mathematical foundations of computer science that are not calculus-based. Such mathematics is especially important in computer science, because data is ultimately represented as discrete bits and an algorithm is inherently a series of discrete steps.

We will begin with an overview of mathematical notation and the basic concepts of sets, functions, and relations. We will then study logic, proof techniques, combinatorics (counting), probability, and the beginnings of graph theory. If time permits, we will work in some elementary number theory. A set of guiding examples from computer science will motivate the topics studied.

## Learning Objectives

If you do well in this course, by the end of it, you will

- be able to read mathematical notation and terminology fluently;
- become comfortable with mathematical thinking that allows you to write clean, logical, proofs;
- become familiar with a number of discrete structures that are used throughout computer science;
- achieve a certain clarity of thinking and expression that (as a side effect) enables you to write correct and efficient code more easily.

## Administrative Information

- Course Staff and Office Hours
- Besides the professor (Amit Chakrabarti), we have an experienced team of TAs to support your learning in this course. Details are on the course's Canvas page.
- Attendance
- In each regular meeting of this class, 40–50% of the time will
be spent in a
*working session*, where students will solve 3–4 problems in small groups, each guided by a TA. Since these sessions are a vital part of the learning experience, in-person attendance is a must. - Getting Help
- Please use Ed
Discussion to ask any questions related to the course and
*do not use email*. - Prerequisites
- CS 10 (or equivalent), and
- a good high-school mathematics education that you can recall very well.
- Textbook
- There is no required textbook. In fact, reading a textbook is rather
low-priority on the list of study techniques for this course. The best
way to learn this subject is by working out lots of problems by yourself
and writing up the solutions using pen-and-paper and/or LaTeX. Maintain
a good notebook with
*your own*lecture notes and*your own*written solutions. Treat this evolving notebook, along with any supplementary notes provided by the professor, as your "primary text" for studying.With that said, here are three textbooks I can recommend as references for further reading. Each book has its strengths (and weaknesses) and each has its own style: I encourage you to read bits of each to figure out which you like best. The answer will differ from one person to another and from one topic to another.

- [LLM] Lehman, Leighton, and Meyer.
*Mathematics for Computer Science*(Aug 2018 revision; Ebook). - [Ros] Kenneth Rosen.
*Discrete Mathematics and Its Applications*(8th Edition). - [Lib] David Liben-Nowell.
*Connecting Discrete Mathematics and Computer Science*(Ebook). Also:*print version*.

- [LLM] Lehman, Leighton, and Meyer.