Education

Lecture notes on Theory of Computation

• 0 - Introduction
• 1 - Models of Computation
• 2 - Finite State Machines
• 3 - Finite Automata and Regular Languages
• 4 - Finite Automata with external storage
• 5 - Context Free Grammars and Languages
• 6 - Turing Machines
• 7 - Complexity: P & NP
• 8 - Equivalence of TMs, PMs and Markov algorithms

Summary of main concepts

• 3 - Finite automata and regular languages: theory
• 5 - Context-free languages, grammars and pushdown automata
• 6 - Effective computability: Turing machines
• 7 - Complexity: P & NP

Lecture notes on Algorithms

• 0 - Introduction and Schedule
• 1 - Computational Geometry
  • 1.0 - Introduction
  • 1.1 - Sample problems and algorithms
  • 1.2 - Plane Sweep
  • 1.3 - The closest pair problem
• 2 - Transitive closure, spanning trees and matrix operations
• 3 - Euclidean graphs and exhaustive search
• 3.1 - Euclidean Spanning Trees
• 3.2 - Exhaustive Search
• 4 - Graph theory and algorithms
• 4.1 - Flow in networks (summary)
• 4.4 - Flow in transport networks
• 5 - Basics of numeric computation
• 6 - Randomized algorithms
• 7 - Approximation and online algorithms
• 8 - Exam