# eecs 210: discrete mathematicsspring 2020

## essentials

 Instructor J. Garrett Morris Email garrettm@ku.edu Office Eaton 2028 Office hours TH 2:20-5:00 PM, and by appointment Course website https://ittc.ku.edu/~garrett/eecs210s20/https://piazza.com/ku/spring2020/eecs210 Lectures TH 9:30-10:45, Learned 1136

## introduction

The syllabus is available here.

Edsger Dijkstra (1972 recipient of the Turing Award) has said that "computer science is no more about computers than astronomy is about telescopes". This course will introduce you to the concepts and intellectual tools needed to separate (the ideas of) computer science from any particular choice of (that is to say, restriction to) particular machines and the ways they are operated.

We will frame these concepts in formal mathematics. (Although, at this point, it might be more correct to say that the foundations of mathematics lie in formal computer science.) If we want to talk about how long program X takes to run on machine M with data set A, we can rely on empirical measurement and observation. However, we will need something more than observation to validate claims about how long program X would take on an arbitrary machine or for arbitrary input data. This course, then, interleaves an introduction to mathematical reasoning with a survey of the basic objects, notations, and techniques used in computer science.

By mathematical reasoning, I mean proof. You should not find this intimidating. You may have think of proofs as a kind of rarified accomplishment produced by brilliant young theoreticians. And, some of you will be brilliant young theoreticians. But a proof is really just any believable mathematical argument---it's the advanced version of "showing your work". Proofs are the language of mathematics, and much of computer science; my own work is full of theorems and proofs. And, just as how in high-school algebra or calculus you learn standard approaches and useful tricks for solving probles, we'll discover that there are standard approaches and useful tricks for constructing proofs in computer science or mathematics.

We'll also learn about a collection of (formal) objects and ideas that will provide the foundation for much of what you'll learn in the rest of your CS education. We'll learn about sets, relations, and functions, which will serve as the foundations for our formal representations, and are closely connected to how we describe computation abstractly. We'll learn about combinatorics (which is a big word for counting) and probability, which lie at the foundation of many ideas in cryptography and data science. And, we'll learn about graphs and trees, which we can use to represent things from physical networks to interacting software components to programming language syntax.

Hopefully you're excited by what I've said so far, and eager to see how these ideas play out for their own sake. But I realize that many of you are future software engineers and systems architects, not future theoreticians. Why should you take this course? First, many of the ideas we'll begin to explore are relevant to practice. Logic underlies the development of new programming languages and new approaches to verifying programs in existing languages. For example, Amazon uses a tool called TLA+, based in formal logic, to assure that key components of AWS won't crash or misbehave under load. Combinatorics and probability underlie public-key infrastructures, like RSA or elliptical-curve cryptography. These in turn guarantee everything from e-commerce purchases to the blockchains. Trees appear in many areas of computer science, from programming language compilers to geographic information systems to video game renderers.

I believe that the ideas of theoretical computer science are remarkable for both their beauty and their practicality. I hope by the end of this course, you'll agree. Welcome aboard!

## homework

Homework assignments and solutions are no longer available.

 Number Due date Assignment Sample solutions 1 Tuesday, January 28, 9:30 AM HW1.pdf HW1ans.pdf 2 Thursday, February 6, 9:30 AM HW2.pdf HW2ans.pdf 3 Tuesday, February 11, 9:30 AM HW3.pdf HW3ans.pdf 4 Tuesday, February 18, 9:30 AM HW4.pdf HW4ans.pdf 5 Tuesday, February 25, 9:30 AM HW5.pdf HW5ans.pdf 6 Tuesday, March 3, 9:30 AM HW6.pdf HW6ans.pdf 7 Tuesday, March 24, 9:30 AM HW7.pdf HW7ans.pdf 8 Tuesday, March 31, 9:30 AM HW8.pdf 9 Tuesday, April 7, 9:30 AM HW9.pdf 10 Tuesday, April 14, 9:30 AM HW10.pdf 11 Tuesday, April 21, 9:30 AM HW11.pdf

## schedule

 date topics reading notes 1/21 Administrivia and organization Logic Rosen 1.1—1.3 Homework 1 out 1/23 No class—instructor away 1/28 Quantifiers Rosen 1.4—1.5 1/30 Logic in practice: program verification in Dafny Homework 2 out Due on Thursday 2/6. 2/42/6 Proof methods and strategies Rosen 1.6—1.8 Notes on natural deduction Homework 3 out 2/11 Sets and set operations Rosen 2.1—2.2 Homework 4 out 2/13 Exam 1 2/182/20 Relations Rosen 9.1, 9.3—9.6 Homework 5 out 2/252/27 Functions Rosen 2.3 Homework 6 out 3/33/5 Basic modular arithmetic Rosen 4.1—4.3 Homework 7 out 3/24 Cardinality Rosen 2.5 Homework 8 out 3/26 Exam 2 3/243/26 Induction Erickson, Proof by Induction 3/314/2 Counting, combinations, and permutations Rosen 6.1—6.3, 6.5 4/7 Discrete probability Rosen 7.1—7.4 4/9 Recurrence relations Rosen 8.1, 8.3 4/14 More counting Rosen 8.5—8.6 4/164/214/23 Graphs Rosen 10.1—10.6 4/284/305/55/7 Trees Rosen 11.1—11.5