# Advanced information, computation, communication I

CS-101 / **7 credits**

**Teacher: ** Aberer Karl

**Language:** English

**Remark:** 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
- Argue about (un)countability
- 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 |

## 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.)

## Ressources en bibliothèque

## Websites

## Moodle Link

## In the programs

**Semester:**Fall**Exam form:**Written (winter session)**Subject examined:**Advanced information, computation, communication I**Lecture:**4 Hour(s) per week x 14 weeks**Exercises:**2 Hour(s) per week x 14 weeks

**Semester:**Fall**Exam form:**Written (winter session)**Subject examined:**Advanced information, computation, communication I**Lecture:**4 Hour(s) per week x 14 weeks**Exercises:**2 Hour(s) per week x 14 weeks

**Semester:**Fall**Exam form:**Written (winter session)**Subject examined:**Advanced information, computation, communication I**Lecture:**4 Hour(s) per week x 14 weeks**Exercises:**2 Hour(s) per week x 14 weeks