good book for Foundations of CS graduate class ?

surfunbear@yahoo.com
19 Aug 2006 01:31:20 -0400

          From comp.compilers

Related articles
good book for Foundations of CS graduate class ? surfunbear@yahoo.com (2006-08-19)
Re: good book for Foundations of CS graduate class ? joe@burgershack.com (Randy) (2006-08-24)
Re: good book for Foundations of CS graduate class ? surfunbear@yahoo.com (2006-08-24)
Re: good book for Foundations of CS graduate class ? gneuner2@comcast.net (George Neuner) (2006-08-25)
| List of all articles for this month |

From: surfunbear@yahoo.com
Newsgroups: comp.theory,comp.compilers
Date: 19 Aug 2006 01:31:20 -0400
Organization: Compilers Central
Keywords: courses, question
Posted-Date: 19 Aug 2006 01:31:20 EDT

  I signed up for just 1 Graduate level CS class at U Mass Lowell for
the fall. I am not working currently, though have been sending out
resumes and working on a Ruby on Rails website on my own. My undergrad
degree is from 1990, though I have worked as a developer for 15 years
in relevant areas such as supporting a propriatary SQL like language
using yacc and similar. I have been surfing the web and studying
documents I found in the course sylabus and feel I should be able to
handle it based on what I read and that hopefully I will have lots of
time to study if needed. I was thinking of getting this book by Kozen
which I saw recomended in a thread that might help me have an easier
time of it.


http://compilers.iecc.com/comparch/article/99-05-065


It's listed as an undergrad book, but seems relevant based on the
course sylabus I found (below). Here is amazon link for the book.
http://net.gurus.com/bk/a/0387949070


Any other recommendations appreciated ...


Course Sylabus from http://www.cs.uml.edu/~wang/cs502/


Week 1
  Administrative Matter. Mathematical Preliminaries; Strings and
Languages; Regular Languages and Regular Expressions


Note: If you find Sections 1.1 and 6.1 difficult, then this course is
not for you.
  1.1-1.2, 6.1


Week 2
  Deterministic Finite Automata (DFA), Checker method of constructing
DFA, Product automata method and complement automata method of
constructing DFA, NFA, Equivalence of NFA and DFA
  2.1-2.4


Week 3
  DFA and Regular Expressions, Closure Properties of Regular Languages,
Myhill-Nerode Theorem, Minimum DFA, Pumping Lemma
  2.5-2.7


Week 4
  Quiz*, Pumping Lemmas
  2.8


Week 5
  Context-Free Grammas, Parsing and Ambiguity, Pushdown Automata and
Context-Free Grammas
  3.1-3.5


Week 6
  Pumping Lemmas for CFL, One-Tape Turing Machines
  3.6, 4.1


Week 7
  Midterm exam




Week 8
  Multi-tape Turing Machines, Church-Turing Thesis, Unrestricted
Grammars
  4.1-4.5


Week 9
  Primitive and Partial Recursive Functions (brief introduction),
Universal Turing Machines, R.E. Sets and Recursive Sets
  4.6-4.8,


5.1-5.2


Week 10
  Diagonalization, Reducibility, Rice Theorem,
  5.3-5.4, handout


Week 11
  Recursion Theorem, Undecidable Problems
  5.5-5.6


Week 12
  Time and Space Complexity, Hierarchy Theorems, NTM's
  6.2-6.4


Week 13
  Context-Sensitive Languages, NP, Polynomial-Time Reducibility
  6.5,


7.1-7.2 Handout


Week 14
  Bounded halting, Bounded tiling, and Cook's Theorem
  Handout


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.