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)
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 23us-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.

For meetings with your fellows you can use this free BBB room.

Information about the examn will be distributed via the mailing list — so sign up, see above.

The exam will be organised following all four weeks of the course as an oral face-to-face exam, either at Aachen or Bonn. The first and second period will start on April 29, 2024 and June 10, 2024, respectively. Previous registration via RWTHonline is mandatory. Please note that you have to choose the exam depending on your preferred location (Aachen or Bonn).

• Kick-off: Monday, 9 October 2023, 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 9 - Fri 13 October 2023, online course (Michael Nüsken).
  Online room, daily collect/kickoff 09⁰⁰.
• Week 2: Mon 16 - Fri 20 October 2023, online course (Michael Nüsken).
  Online room, daily collect/kickoff 09⁰⁰.
• Week 3: Mon 11 - Fri 15 March 2024, online course (Thomas Noll).
  Kick-off and daily Q&E meetings: 09⁰⁰ Zoom, see third weeks page.
• Week 4: Mon 18 - Fri 22 March 2024, online course (Walter Unger).
  Kick-off ahd daily session start; 09⁰⁰, zoom. Afternoon sessions including Q&E Mon-Thu 14⁰⁰, zoom.

All material for week 1 and week 2 is in the online course which is available from August 2023 to December 2024.

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

• At least week 1 & 2 of the course take place 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, ...).

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

Kick-off ahd daily session start; 09⁰⁰, zoom. Afternoon sessions including Q&E Mon-Thu 14⁰⁰, zoom.

Slides. (To be added eventually.)

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