Readings for CSU 390

• Read in textbook:
  • Chapter 0 (Introduction)
  • Chapter 1 (Regular Languages)
  • Chapter 2 (Context-Free Languages)
  • Section 3.1 (Turing Machines)
  • Section 3.3 (The Definition of Algorithm)
  • Chapter 4 (Decidability)
  • Section 5.1 (Undecidable Problems from Language Theory)
  • Definition 5.17 (computable function)
  • Chapter 7 (Time Complexity) except section 7.5

Supplemental readings

• Dr Fran Allen just became the first woman ever to win the ACM Turing award.
• The asymptotic complexity of a naive (doubly recursive) calculation of Fibonacci numbers is roughly proportional to 5^(-1/2).
• Donald E Knuth. The Complexity of Songs. Communications of the ACM 27(4), 1984, pages 345-348.

Last updated 26 March 2007.