Moodle page for the course is up.

## MTAT.05.008 Discrete Math

This course serves to diverging purposes:

- Provide (potential) Theory students with the high-level foundation required for their thesis research;
- Present programming-only students with a selection of useful, applicable discrete math.

In recent years, attempts to reconcile these two goals have failed: Theory students didn't get the material they needed, and programming students were overwhelmed by the requirement to produce rigorous proofs and solve difficult problems.

This year, the course will be split into two branches.

- S-Branch: for students who
*consider*specializing / writing their thesis in Theory (specialization module 2.4) - P-Branch: for students who don't.

You don't need to decide on a branch now:

`In the first lecture session (Wed, Sep 2) there will be a Qualifying exam.`

The main reason for this exam is to assess the average skill level of the new CS master students. Students with sufficiently high scores are eligible for S-Branch.

`Decide for Your branch by Mon, Sep 7!! (by signing up for the corresponding Practice Session)`

P-Branch | S-Branch |
---|---|

6 ECTS CP | 6 + 3 ECTS CP |

Course contents

P-Branch | S-Branch |
---|---|

* Basics about graphs and counting | *(already have that) |

* Sublinear time algorithms | * Sublinear time algorithms, w/ proofs, |

...lower bounds for sublinear time algorithms, | |

...Communication Complexity | |

* Data stream (sublinear space) algorithms | * Data stream algorithms w/ proofs |

...lower bounds | |

* Discrete probability (needed for the proofs) | |

* Information theory | |

* Quantum computing basics |

Homeworks

P-Branch | S-Branch |
---|---|

3 easy exercises per week, 1 of them a proof | 3 doable + 1 challenging exercises a week, mostly involving proofs |

Advantages

P-Branch | S-Branch |
---|---|

* Less work needed | * More skills acquired |

* Learn some cool discrete-math-ish algorithms | * More, cooler algorithms |

* Learn to develop new algorithms, not just puzzle together known ones | |

* Learn basic (undergraduate level) graphs and counting stuff you need for other courses | * Learn discrete math you need for Theoretical Computer Science |

* Learn how to prove lower bounds for algorithms | |

* Who needs math anyway?!? | * Theory is not math! |

**Potential S-Branch students: check out the Theory Café.**

## FAQ

### What is "Theory"??

Definition by example: Here are some completely arbitrary (but, I suppose, less known to students) things you could be doing in your Theory master's project.

- Find and analyze a randomized algorithm for a specific problem
- Find and analyze a data stream (or sublinear) algorithm for a specific problem
- Find and analyze a query-based learning algorithm for a specific machine learning problem
- Prove a lower bound on the number of queries needed to learn a type of objects
- Prove a lower bound on the space needed by a data stream algorithm for a specific problem
- Prove a lower bound on the running time of any algorithm for a specific problem
- Prove something about graphs
- Prove something about random graphs

The important distinction is this:

- Do you want to add to the total number of lines of codes in the world? (-> P-Branch)
- Do you want to add to the knowledge and understanding of Computer Science problems in the world? (-> S-Branch)

"Theory" stands for **Theoretical research in specialization module 2.4 "Cryptography and Theoretical Informatics"**, and "theoretical" means, a substantial part of your work is in proving theorems, as opposed to writing code.

**It's important to realize that we also offer non-Theory (= no significant amount of proving) thesis projects in Module 2.4, e.g., Computational Optimization, where you're supposed to implement code solving some optimization problem of relevance, for example in a data stream or online setting. There are also non-theory Masters topics in Coding Theory**.

### Can I switch between branches?

It's easy to migrate from S-Branch to P-Branch, **at any time,** if you find it's not your cup of tea. The other direction is "allowed", but it might be very, very difficult to catch up with what the other S-Branch students learned.

### I hear, the number of CPs in the two branches differ...?

S-Branch students have one additional lecture per week (it will be on video), and more difficult homeworks than P-Branch. That is why S-Branch students will earn **9 CP** on the course, whereas P-Branch students will earn **6-CP**. (S-Branch students must register for MTAT.05.124 "Special Assignment in TCS" to claim their extra credits. MTAT.05.124 serves only the purpose of delivering those CPs. The grade for MTAT.05.124 will simply be the same as that for MTAT.05.008.)

### Which branch is right for me?

Obviously, if you're already 95% committed to writing code for your master's project, then S-Branch will be a waste of time for you. Apart from that, here are 3 bullet points to help you decide if S-Branch is for you.

**(1) Your personality.**
S-Branch students enjoy intellectual challenge.

Consider the following situation: The homework assignment is a problem which you've never seen before, which doesn't look similar to anything you've ever seen before, and nothing you know seems to help you solve it. What's your reaction?

- P-Branch student "I want a normal problem, please."
- S-Branch student "That's ok, I appreciate the challenge."

**(2) Your background.**
S-Branch students have mastered undergraduate math stuff such as proofs, functions, relations, counting, and basic probability.

Consider the following situation: The homework assignment asks you to give a rigorous proof for a statement involving the number of objects of a certain type. There's a hint which says that you're supposed to prove, by induction, that a bijection to the set of k-element subsets of an n-element set exists. What's your reaction?

- S-Branch student "So...??"
- P-Branch student "What's bijection and induction? What does n choose k mean? Will someone explain to me what a 'rigorous proof' is, please?"

**(3) Your motivation & aptitude.**
The intellectual demands on Theory students are higher than on other students. Moreover, S-Branch has a higher workload and more difficult homework assignments.