Section outline

  • Announcements

    Collapse all Expand all

  • General Information

    Teaching Staff
    • Theofilos Triommatis (theotriomatis@gmail.com)
     
    TΑ
    • Chris Pergaminelis, PhD student (chrispergaminelis@gmail.com)

    Lectures

    For the Erasmus students / taught in English:

    • Tuesday 17:45-19:30, Amph. 4
    • Thursday 17:45-19:30, Amph. 4

    The first Lecture will take place on Thursday 1/10. The page will be regularly updated with the course material.

    Below you may find material (slides, etc.) from the previous year. You can consult this material until the new one is uploaded.

  • Lecture Content (2024-25)

    • Section 1: Automata, Languages, Grammars

      • Lecture 0210: Introduction, Finite Automata, Deterministic Automata (DFA). (Slides 1-19)
      • Lecture 07/10: Non-deterministic Automata (NFA, NFAε), NFA and DFA Equivalence, NFA to DFA Conversion. (Slides 20-36)
      • Lecture 9/10: NFAε to DFA Conversion, DFA Minimization, State Distinguishability and Equivalence, Formal Languages and Formal Grammars. (Slides 37-62)
      • Lecture 14/10: Chomsky Hierarchy, Regular Grammars, Regular Expressions, Equivalence of Regular Expressions and Finite Automata, Product of Automata. (Slides 63-81)
      • Lecture 16/10: Pumping Lemma, Context-Free Grammars, Parse Trees. (Slides 82-98)
      • Lecture 21/10: Tutorial: NFA, DFA, NFA to DFA Conversion, Product of Automata, DFA Minimization, Regular Expressions.
      • Lecture 23/10: Pushdown Automata (PDA), Context-Sensitive Grammars, Linear Bounded Automata (LBA), General Grammars, Turing Machines. (Slides 99-118)
      • Tutorial Session 30/10: Pumping Lemma, Context-Free Grammars.

      Section 2: Asymptotic Notation

      • Lecture 04/11: Asymptotic Notation. (Slides 1-19)

      Section 3: Graphs, Shortest Paths, Minimum Spanning Trees

      • Lecture 11/11: Shortest Paths, Dijkstra's algorithm. (Slides 1-42)
      • Lecture 13/11: Correctness of Dijkstra's algorithm, Bellman-Ford algorithm, MST, Prim, Kruskal, Boruvka algorithms. (Slides 43-87)

      Section 4: Arithmetic Algorithms

      • Lecture 18/11: GCD, Exponentation. (Slides 1-30)
      • Lecture 20/11: Fibonacci Numbers, Integer Multiplication. Short Tutorial session (Slides 31-55)

      Section 5: Computability & Complexity

      • Lecture 25/11: Computational Problems, Halting Problem, Complexity of Computational Problems, P =? NP, TSP Problem, Complexity Classes (Slides 1-50)

      Section 6: Dynamic Programming

      • Lecture 27/12: Introduction, Fibonacci Sequence, Shortest Path in DAG, Longest Increasing Subsequences, Edit Distance. Short Tutorial session (Slides 1-86)

  • Grading

    • Grading Breakdown:

      • E: final exam score, out of 10
      • A: exercises score, out of 1.5

      Final Grade = max{E * (1 + A/10), 10}

      Note: To have your exercises graded, you must briefly present your solutions on a date and time that will be announced later.

  • Material