Section outline

  • Announcements

    Collapse all Expand all

  • General Information

    Teaching Staff
    • Nicos Protopapas  (nikosfprotopapas@gmail.com)
     
    TΑ
    • Chris Pergaminelis, PhD student (chrispergaminelis@gmail.com)

    Lectures

    For the Erasmus students / taught in English:

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

    The first Lecture will take place on Thursday 2/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 03/10: Introduction, Finite Automata, Deterministic Automata (DFA). (Slides 1-19)
      • Lecture 08/10: Non-deterministic Automata (NFA, NFAε), NFA and DFA Equivalence, NFA to DFA Conversion. (Slides 20-36)
      • Lecture 10/10: NFAε to DFA Conversion, DFA Minimization, State Distinguishability and Equivalence, Formal Languages and Formal Grammars. (Slides 37-62)
      • Lecture 15/10: Chomsky Hierarchy, Regular Grammars, Regular Expressions, Equivalence of Regular Expressions and Finite Automata, Product of Automata. (Slides 63-81)
      • Lecture 17/10: Pumping Lemma, Context-Free Grammars, Parse Trees. (Slides 82-98)
      • Lecture 22/10: Pushdown Automata (PDA), Context-Sensitive Grammars, Linear Bounded Automata (LBA), General Grammars, Turing Machines. (Slides 99-118)
      • Tutorial Session 24/10: NFA, DFA, NFA to DFA Conversion, Product of Automata, DFA Minimization, Regular Expressions.
      • Tutorial Session 31/10: Pumping Lemma, Context-Free Grammars.

      Section 2: Asymptotic Notation

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

      Section 3: Graphs, Shortest Paths, Minimum Spanning Trees

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

      Section 4: Arithmetic Algorithms

      • Lecture 14/11: GCD, Exponentation. (Slides 1-30)
      • Lecture 19/11: Fibonacci Numbers, Integer Multiplication. (Slides 31-55)

      Section 5: Computability & Complexity

      • Lecture 21/11: Computational Problems, Halting Problem, Complexity of Computational Problems, P =? NP, TSP Problem, Complexity Classes. (Slides 1-50)
      • Lecture 26/11: Computability & Complexity, Revisited

      • Tutorial Session 28/11: Graph Algorithms
      • Tutorial Session 03/12: Graph Problems
      • Tutorial Session 05/12: Graph Problems

      Section 6: Dynamic Programming

      • Lecture 10/12: Introduction, Fibonacci Sequence, Shortest Path in DAG. (Slides 1-34)
      • Lecture 12/12: Longest Increasing Subsequences, Edit Distance. (Slides 35-86)
      • Lecture 17/12: Shortest Reliable Paths, All-pair Shortest Paths, Knapsack. (Slides 113-170)

      • Tutorial Session 07/01: Revision
      • Tutorial Session 09/01: Revision
      • Tutorial Session 16/01: Revision

  • Grading

    • Grading Breakdown:

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

      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