Line 1: Line 1:
 +
 
[http://www.youtube.com/playlist?list=PL601FC994BDD963E4 Video Lectures by Shai Simonson]
 
[http://www.youtube.com/playlist?list=PL601FC994BDD963E4 Video Lectures by Shai Simonson]
  
 
[http://www.ecst.csuchico.edu/~amk/foo/csci356/notes/ch11/NP2.html NP Complete]
 
[http://www.ecst.csuchico.edu/~amk/foo/csci356/notes/ch11/NP2.html NP Complete]
 +
 +
[http://www.idt.mdh.se/kurser/cd5560/10_01/examination/KOMPENDIER/Regular/kompendium_eng.pdf Regular expressions, questions and solutions]
  
 
[http://csfundas.wordpress.com/theory-of-computation-2/recursively-enumerable Recursively Enumerable Sets]
 
[http://csfundas.wordpress.com/theory-of-computation-2/recursively-enumerable Recursively Enumerable Sets]

Revision as of 10:45, 15 October 2014

Video Lectures by Shai Simonson

NP Complete

Regular expressions, questions and solutions

Recursively Enumerable Sets

Recursively Enumerable Sets

Notes from CMU

Definitions

Push Down Automata

Linear Bounded Automata

Turing Machine Problems

Turing Machine Handout

Reduction examples for decidablility

Rice's theorem, Undecidable and unrecognizable problems on TM

Undecidable problems about L(CFG)

Trivial and Non-trivial properties of L(M)

Undecidable Problems

Closure property of CFL

NP Complete

A good lecture going deep into Abstract Machines

P, NP, NPC and NP-Hard in SImple terms

Identify the class of the language