- fundamental problems in computer science -

 (1) computability theory

  Wikipedia :

      Computability
      * links to all the rest...

      Turing machine
      * first, discuss what it is
      * "universal" one
      * According to the Church-Turing thesis, the problems solvable
        by a universal Turing machine are exactly those problems
        solvable by an algorithm 
      * see examples from text

      Complexity Classes P and NP
      * sorting : O(n log(n)), O(n^3), etc
      * Is P = NP ?   ($1 million prize...)
         best guess is no :  ( NP   ( P )  ( NP Complete )  )
          P  means answer can be found in polynomial time (as size grows)
          NP means answer can be checked in polynomial time
         (Nondeterministic Polynomial, e.g. parallel computer poly time)
          NP-complete is a class of "hard" NP's that have been shown 
          to be equivalent: if you can do one in P time, you can do 'em all.

      * NOTE that a smaller order isn't always faster!
        (depends on coefficients...)

      Traveling salesman problem : one of the classic NP
      * brute force: N! graphs to check ... O(n^n)
        Stirling's formula : N! ~ sqrt(2 pi n) (n/e)^n )

      Grammars
      * context-free 
      * formal languages
      * logic