Section outline

  • Announcements

    Collapse all Expand all

  • General Information

    Teaching Staff
    • Giannis Papaioannou  (ipapaioannou@corelab.ntua.gr)
     
    TΑ
    • Chris Pergaminelis, PhD student (chrispergaminelis@gmail.com)

    Lectures

    For the Erasmus students / taught in English:

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

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

  • Lecture Content

    • 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)

  • 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