Re: good book for Foundations of CS graduate class ?

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

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