24 Aug 2006 18:15:19 -0400

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) |

From: | Randy <joe@burgershack.com> |

Newsgroups: | comp.theory,comp.compilers |

Date: | 24 Aug 2006 18:15:19 -0400 |

Organization: | Compilers Central |

References: | 06-08-118 |

Keywords: | books |

If you're committed to taking the course, I suggest that you buy the

Du & Ko text and decide for yourself if you understand it. If not,

also buy a well regarded older undergrad CS theory text like:

Sipser (my favorite)

http://www.amazon.com/gp/product/053494728X/sr=8-2/qid=1156390733/ref=pd_bbs_2/103-6801875-0439845?ie=UTF8

Lewis & Papadimitriou (also very good)

http://www.amazon.com/gp/product/0132734176/ref=ed_oe_h/102-2366519-7237712?ie=UTF8

Aho, Hopcroft & Ullman (a bit too succinct and formal)

http://www.amazon.com/gp/product/0201000237/sr=1-2/qid=1156391059/ref=sr_1_2/102-2366519-7237712?ie=UTF8&s=books

Sudkamp (mostly harmless)

http://www.amazon.com/gp/product/0201821362/ref=ed_oe_h/102-2366519-7237712?ie=UTF8

The syllabus you listed looks to be 90% identical to the standard

junior level theory course. Du & Ko's other book (on computational

complexity) is renowned for being very formal and difficult. Probably

their CS theory book will be comparably daunting. A good second

theory book might be a wise investment.

Randy

surfunbear@yahoo.com wrote:

*> 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.