| Instructor | J. Garrett Morris |
| 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 |
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 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 |
| 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/4 2/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/18 2/20 |
Relations | Rosen 9.1, 9.3—9.6 | Homework 5 out |
| 2/25 2/27 |
Functions | Rosen 2.3 | Homework 6 out |
| 3/3 3/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/24 3/26 |
Induction | Erickson, Proof by Induction | |
| 3/31 4/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/16 4/21 4/23 |
Graphs | Rosen 10.1—10.6 | |
| 4/28 4/30 5/5 5/7 |
Trees | Rosen 11.1—11.5 |