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
Prof. Dr. Ir. Gerhard Woeginger

Students are encouraged to ask and answer any questions related to the course on the mailinglist. You can always post on 20us-brico-at-lists.bit.uni-bonn.de. We will use it for announcement regarding the course. 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 here and on the mailing list —sign up, see above.

• Kick-Off: Monday, 12 October 2020, 09⁰⁰-09³⁰, online room.
  Just afterwards, we will perform a speed grouping. 09³⁰-11³⁰, in a second online room.
  You need to sign up as described there to get the speed grouping room link.
• All teaching in week 1/2 is online. To participate
  • either join the kick-off
  • or email me explaining your reasons.
• Week 1: Mon 12 - Fri 16 October 2020, online course (Michael Nüsken).
  Online room, daily collect/kickoff 09⁰⁰.
• Week 2: Mon 19 - Fri 23 October 2020, online course (Michael Nüsken).
  Online room, daily collect/kickoff 09⁰⁰.
• Week 3: Mon 8 - Fri 12 March 2021, online course (Thomas Noll).
• Week 4: Mon 15 - Fri 19 March 2021, online course (Gerhard Wöginger).

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

You find a version of the slides on sciebo until December 2021. [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.

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

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 Fourth 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

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