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.

To participate in week 1 and 2 of this course, you must register at edX.

Visit the link to the online course below. Register there and enroll in the edX course. Once you have done that you can reenter similarly at any time. This is self-paced, you do not need to wait for the kick-off.

Dr. Michael Nüsken
Prof. Dr. Thomas Noll (contact person)
Prof. Dr. Martin Hoefer

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

• Kick-off: Monday, 7 October 2024, 09⁰⁰-09³⁰, hybrid: b-it-max 0.109 and 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 7 - Fri 11 October 2024, online course (Michael Nüsken).
  Online room, daily collect/kickoff 09⁰⁰.
• Week 2: Mon 14 - Fri 28 October 2024, online course (Michael Nüsken).
  Online room, daily collect/kickoff 09⁰⁰.
• Week 4: Mon 24 - Fri 28 March 2025, online course (Martin Hoefer).
  Kick-off and details tba.
• Week 3: Mon 31 March - Fri 4 April 2025, online course (Thomas Noll).
  Kick-off and daily Q&E meetings: 09⁰⁰ Zoom, see third weeks page.

• At least week 1 & 2 of the course take place mostly online. This is mainly self-paced and can be performed at any time. There will be kick-offs in the respective time for getting  to know each other, keeping pace and asking questions.
• 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. In particular, for receiving in-time messages about exam form and schedule please sign up to the mailing list.
• 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).
• WARNING: Make sure that you read the email associated with your Uni ID!

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

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

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