good book for Foundations of CS graduate class ?
19 Aug 2006 01:31:20 -0400

          From comp.compilers

Related articles
good book for Foundations of CS graduate class ? (2006-08-19)
Re: good book for Foundations of CS graduate class ? (Randy) (2006-08-24)
Re: good book for Foundations of CS graduate class ? (2006-08-24)
Re: good book for Foundations of CS graduate class ? (George Neuner) (2006-08-25)
| List of all articles for this month |

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.

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.

Any other recommendations appreciated ...

Course Sylabus from

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

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

Week 4
  Quiz*, Pumping Lemmas

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

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

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


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

Week 11
  Recursion Theorem, Undecidable Problems

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

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

7.1-7.2 Handout

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

Post a followup to this message

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