Foundations of informatics - a bridging course

This course is listed

• in Aachen RWTHonline as Foundations of informatics - a bridging course,
• in Bonn Basis as Foundations of Informatics - a bridging course.

Dr. Michael Nüsken (contact person)
Prof. Dr. Thomas Noll
PD Dr. Walter Unger

Students are encouraged to ask and answer any questions related to the course on the mailinglist. You can always post on 21us-brico-at-lists.bit.uni-bonn.de. We will use it for announcement regarding the course and exams(!). To subscribe to or unsubscribe from the mailing list visit the list's Info page.

The exam will happen after all four weeks of the course, thus some time next spring or summer. Due to the imponderabilia of the pandemic we do not even fix the form of the exam. It may be a classical presence exam or it may be online oral exams. We wil decide details next spring and publish them via the mailing list — so sign up, see above.

• Kick-off: Monday, 4 October 2020, 09⁰⁰-09³⁰, online room.
  Just afterwards, we will perform a speed grouping. 09³⁰-11³⁰.
• All teaching in week 1/2 is online. To participate
  • either join the kick-off
  • or email me explaining your reasons.
• Week 1: Mon 4 - Fri 8 October 2021, online course (Michael Nüsken).
  Online room, daily collect/kickoff 09⁰⁰.
• Week 2: Mon 11 - Fri 15 October 2021, online course (Michael Nüsken).
  Online room, daily collect/kickoff 09⁰⁰.
• Week 3: Mon 7 - Fri 11 March 2022, online course (Thomas Noll).
  Kick-off and daily Q&E meetings: 09⁰⁰ Zoom, see third weeks page.
• Week 4: Mon 14 - Fri 18 March 2022, online course (Walter Unger).
  Kick-off Monday 09⁰⁰ Zoom, see below.
  Q&A Session 1: Friday, 18 March 2022, Zoom, see below.
  Q&A Session 2: Wednesday, 14 April 2022, Zoom, see below.

All material for week 1 and week 2 is in the online course which is available from July 2021 to December 2022.

You find a version of the slides on sciebo until December 2022. [Registering at sciebo and installing the client helps here and later.]

• At least week 1 & 2 of the course takes place online.
• The courses of the Media Informatics programme only start after the first two weeks of the bridging course.
  (A similar agreement for the Software Systems Engineering programme does not exist, you have to arrange with the collision.)
• For some students this course is compulsary. That means: you have to pass the exam eventually. You have two occasions for the exam every year, typically in April and June.
• You have to register for the exam in your respective program (ie. not with us!).

Possibly, your study advisor cares for first network access.

• You may use eduroam.
• Apply for a b-it account (includes applying for a Uni ID at Bonn).
  (For the Uni ID at Bonn you will need to fill in your data online [choose "guest", "Cooperation study program media informatics Aachen"] and then send an email with a scan of your student card and some identity card. In return, you will obtain credentials via standard mail. This is then enough to apply for a b-it account.)

This week will deal essentially with three subjects:

• Linear Algebra (Gauß-Jordan-algorithm, expansion, dim ker A + dim im A = n, ...),
• Probabilities (Definitions, conditional probabilities, random variables, expected runtime of a random exit loop, some applications, ...),
• Integers modulo N (Definition, inversion and extended Euclidean algorithm, square and multiply, exponentiation, Theorem of Lagrange, of Euler and Fermat's little theorem, RSA correctness and efficiency, ...).

You might enjoy solving the geocache Felix Bauklötze.

Agenda

• foundations (first examples, asymptotic notation, solving recurrence equation)
• sorting (QUICKSORT, sorting in linear time)
• data structures (linked lists, binary search trees)
• graph algorithms (elementary (breadth-first, depth-first), single-source shortest path)

Literature

• Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, 3rd edition, MIT Press, 2009.
• Goldreich, Computational Complexity: A conceptual perspective, Cambridge University Press, 2008.
• Knuth, TAOCP, Vol. 1 -- Fundamental Algorithms, 3rd edition, Addison-Wesley.

Regular Languages

• Introduction to Formal Languages
• Deterministic and Nondeterministic Finite Automata
• Regular Expressions and Languages
• Closure and Decidability Properties

Context-Free Languages

• Context-Free Grammars and Languages
• Relation to Regular Languages
• Pushdown Automata
• Closure and Decidability Properties

Find details about this week on Third week's page.

1. Introduction to computability
2. Undecidable problems; halting problem; theorem of Rice
3. Recursive enumerability; PCP; Hilbert's tenth problem
4. Introduction to complexity
5. NP-completeness of selected graph problems
6. NP-completeness of selected number problems

Find details about this week on Fourth week's page.

Kick-off Monday 09⁰⁰ Zoom.
Q&A Session 1: Friday, 18 March 2022, Zoom.
Q&A Session 2: Wednesday, 14 April 2022, Zoom.

Equivalent V4+Ü4.
For some MI-students this course is obligatory, for the others it's optional. There are no credits for this course.