Course Goals

• Provide computation models
• Analyze power or models
• Answer Intractability Questions
  • What computation Problems can each model solved
• Answer time complexity questions (Analysis of algorithms)
  • How much time we need to solve the problems

Kinds of Automation

• Finite Abstracts (As temporary memory)
• Pushdown Automata (Stack)
• Turing Automata (Random Access Memory)

Example of finite automata

• Elevators, Vending machines
• Lexical Analyzers
• Small Computing power

Turing Machines

• Example can be any algorithm with highest Known computing power

Time complexity of computational problems

• P problems:
  • polynomial time problems
  • solved in polynomial time
• NP-complete problems
  • Non-deterministic polynomial time problems
  • Believed to take exponential time to be solved