## Discrete Math

This compulsory course teaches the use of Discrete Math in Computer Science.

The main focus of the course is on training problem solving skills: each student gets a problem which he has never seen before, for which, on first sight, he has no idea how to solve it, in fact, he may have trouble understanding what is asked from him in the exercise.

Another focus is to learn problem solving in small groups.

The course is based on the textbook "Invitation to Discrete Mathematics" by Matousek and Nesetril. We will cover Chapters 2--8 and 10 in class.

**WORK THROUGH CHAPTER 1 BEFORE THE FIRST CLASS MEETING to revive your UG math.**

**SOLVE ALL THE EXERCISES!!**

You need a copy of the book for the whole course! Moreover, you will need a **hard copy** of the book for the exams! (The exams are open book.) There should be sufficiently many copies (~35) in the libraries.

### Course prerequisites

This is a graduate level course. We take *undergraduate level math for computer science* for granted. Computer Science majors at the University of Tartu have 24 ECTS worth of undergraduate math education, covering, among others, logic & proofs, calculus, (linear) algebra, and basic probability.

**Make sure your UG math for CS is up to speed!**
If it isn't you'll have to work *very* hard for this MTAT.05.008. Here's how you can make sure your UG math is sufficient.

(1) You can test whether your UG math background is sufficient by reading Chapter 1 of the textbook, and solving all the exercises in that chapter on your own. If you can do that (possibly with considerable effort), you're fine.

If you find that you couldn't solve the exercises if your life depended on it, then the course will be very challenging, even overwhelming most of the time, and passing the exams will require a *lot* of very frustrating work. But don't worry about it: you're smart, so, if you put in the work, and find yourself a study group, we'll get you there. In fact, last year's experience shows that you can even get an A. (No promises here.)

(2) Check out the ATI Math Wiki for a subset of the *facts* you're supposed to know. What the Math Wiki doesn't give you is experience in solving problems.

(3) A more comprehensive source is the MIT undergraduate course "Mathematics for Computer Science". It has video lectures. Check out the lectures 1-3, 6-23. Keep in mind that that is an undergraduate course. Solve the problems in the assignments.

### Course organization

The course has one compulsory weekly meeting (you have to attend), two voluntary weekly sessions -- and a lot of individual study time (same as "Advanced Algorithms", but more frustrating). The individual study consists of (a) reading the assigned sections of the textbook and (b) solving as many of a list of the recommended exercises as you can. For (b), **find yourself a study group**: a few people consuming large amounts of pizza while discussing the recommended exercises, trying to come up with solutions, making sure everybody understands the solutions, etc.

In the compulsory class meetings, you'll solve problems in small groups, under time pressure, and hand them in at the end of the class. The solutions will be marked and returned to you. The results will not influence the final grade.

In the practice session classes, you will solve problems in small groups, but we'll be there to give you hints etc. These sessions are for guided learning of how to solve problems.

Finally, in the textbook session classes, we'll discuss the assigned reading, trying to make sure everybody understands all the concepts and arguments.

### The final grade

The final grade will be compiled from your results of one **midterm exam** and one **final exam**. In the exam, you'll have to solve problems on your own (no group), but there will be less time pressure.

Dirk Oliver Theis

Mozhgan Pourmoradnasseri