**CS 231: Discrete Mathematics**

Prof. Richard Eisenberg

Fall 2017

Bryn Mawr College

Instructor: | Richard Eisenberg |

Email: | `rae@cs.brynmawr.edu` |

Office Phone: | 610-526-5061 |

Home Phone (emergencies only): | 484-344-5924 |

Cell Phone (emergencies only): | 201-575-6474 (no texts, please) |

Office: | Park 204 |

Office Hours: | Mondays 3:30-4:30pm, Tuesdays 1:30pm-2:30pm |

If this doesn’t work, do not fret. Email instead. | |

Lecture: | MW 10:10-11:30 |

Lecture Room: | Park 229 |

Lecture Recordings: | at Tegrity: access via Moodle; look for link on right side of screen. |

Website: | http://cs.brynmawr.edu/cs231 |

GitHub Repo: | https://github.com/goldfirere/cs231 |

Piazza Q&A Forum: | https://piazza.com/brynmawr/fall2017/cs231/home |

Time | TA | Location |

Tuesdays, 7-9pm | Rose Lin (rlin1@brynmawr.edu) | Park 231 |

Mondays, 7-9pm | My Nguyen (mnguyen1@brynmawr.edu) | Park 231 |

Mondays, 7-9pm | Caroline Shen (yshen3@brynmawr.edu) | Park 231 |

Thursdays, 4-6pm | Wenqi Wang (wwang1@brynmawr.edu) | Park 231 |

Tuesdays, 7-9pm | Zhengyi Xu (zxu@brynmawr.edu) | Park 231 |

By the end of this course, you will be able to…

- reason about problems using formal mathematical logic
- write inductive proofs
- apply combinatorial techniques to estimate probabilities
- describe the shape of a variety of discrete structures

During the course, you will…

- write proofs
- use precise mathematical reasoning

This is a course in discrete mathematics, the branch of mathematics that underpins computer science and number theory. The word *discrete* means “individually separate and distinct”. Applied to mathematics, this word means that we will be studying the behavior of mathematical structures that can be considered as individual, distinct units: for example, we will study integers, not the real numbers; or we will study *true* and *false*, not the unit interval (that is, the range of numbers between 0 and 1).

A key part of any mathematical investigation is *proof*. In this course, we will do many proofs by *induction*, a powerful technique where local reasoning can be used to prove global properties. Along the way, we will also discuss a variety of discrete structures, including Boolean algebra, the natural numbers, sets, functions over sets, trees, and graphs. We will also use our knowledge to delve into combinatorics, the mathematics of counting; combinatorics underly much of probability and data science.

This course does *not* build on calculus or linear algebra. Instead, it explores separate areas of mathematics. Work in this course will be all pencil-and-paper; there will be no computer programming.

The **required** textbook for the course is:

**Discrete Mathematics with Applications**, Fourth Edition, by Susanna S. Epp. It is available at the bookstore.

Known errata for this book are posted.

Recommended reading:

These two books offer nice background and motivation for the material in this course.

**How to Bake π: An Edible Exploration of the Mathematics of Mathematics**, by Eugenia Cheng, available online through the library. This breezy, light-hearted book is the best articulation I’ve read of why math is fun and important. It specifically motivates a branch of mathematics called*category theory*, which is not studied in this course. However, really, it just motivates mathematical thinking. Feel free to skip most of Part II of the book (the part on category theory), but don’t miss the last chapter, which is a gem and does not depend on the category theory material.**Gödel, Escher, Bach: An eternal golden braid**, by Douglas R. Hofstadter, available at the library. This classic explores mathematics and computer science through logic, with an emphasis on recursion. It was written for a non-specialist audience.

And I can’t help but recommend