# Coursebooks

## Advanced information, computation, communication I

Aberer Karl

English

#### Remarque

This course focuses on the foundational, discrete mathematics core of advanced computation.

#### Summary

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics as diverse as mathematical reasoning, combinatorics, discrete structures & algorithmic thinking.

#### Content

I. Mathematical reasoning: propositional logic, propositional functions, quantifiers, rules of inference; this includes very basic logic circuits.
II. Sets and counting: cardinalities, inclusion/exclusion principle, sequences and summations.
III. Algorithms and complexity: basic algorithms, computational complexity, big-O notation and variants, countability.
IV. Number representations such as binary and hexadecimal and (postponed to 2nd semester) basic number theory: modular arithmetic, integer division, prime numbers, hash functions, pseudorandom number generation; applications.
V. Induction and recursion: mathematical induction, recursive definitions and algorithms.
VI. Basic combinatorial analysis: permutations, binomial theorem, basic generating functions.
VII. Basic probability: events, independence, random variables, Bayes' theorem.
VIII. Structure of sets: relations, equivalence relations, power set.
IX. (time permitting) Elementary graph theory: graphs, Euler and Hamilton paths, Dijkstra's algorithm, spanning trees.

#### Keywords

Propositional logic, counting, complexity, big-O, number representations, sets, matrices, modular arithmetic, induction, basic probabilities, Bayes theorem, combinatorial analysis, recurrences, generating functions, countability, graph theory.

#### Learning Outcomes

By the end of the course, the student must be able to:
• Recognize if there is a mistake in a (simple) proof
• Apply general problem-solving techniques
• Recognize the mathematical structures present in applications
• Apply simple recursion and use it to design recursive algorithms
• Apply the tools studied in class to solve problems
• Demonstrate familiarity with mathematical reasoning
• Solve linear recurrences and use generating functions
• Formulate complete, clear mathematical proofs

#### Transversal skills

• Assess one's own level of skill acquisition, and plan their on-going learning goals.
• Continue to work through difficulties or initial failure to find optimal solutions.
• Demonstrate the capacity for critical thinking

#### Teaching methods

Ex cathedra lectures

#### Expected student activities

Studying the book, test your understanding by making the exercises, ask questions

#### Assessment methods

Final exam (100%), mostly (and possibly exclusively) multiple choice

#### Supervision

 Office hours No Assistants Yes Forum No Others A list of students assistants and their contact data will be made available on the moodle page for this course, along with an assignment of each registered student to one of the student assistants. If you have a question, first contact the student assistant assigned to you. If that does not help, contact one of the teaching assistants (Negar Foroutan, Banaei Mohammadreza). Furthermore, you are always welcome to drop me an email (karl.aberer@epfl.ch) for any type of question related to this course or your study at EPFL. Never hesitate to ask questions before, during or after the lectures!

#### Resources

##### Bibliography

"Discrete Mathematics and Its Applications", Kenneth H. Rosen, 8th ed, McGraw-Hill 2019. (You should be able to find the pdf on the web.)

### Reference week

MoTuWeThFr
8-9 CO1
9-10
10-11    INJ218
INM10
INM11
INM200
INM202
INR219
11-12
12-13
13-14
14-15
15-16
16-17    CO1
17-18
18-19
19-20
20-21
21-22

Lecture
Exercise, TP
Project, other

### legend

• Autumn semester
• Winter sessions
• Spring semester
• Summer sessions
• Lecture in French
• Lecture in English
• Lecture in German