(See also CourseTextbooks, which contains references for the books mentioned here)

Drafty thoughts on what to do/say

WARNING: THIS POLICY IS STILL SUBJECT TO SUBSTANTIAL REVISION. CONTACT LAS BEFORE RELYING ON THIS INFORMATION!!!

This course cuts across many areas of CS and, unfortunately, most textbooks don't. The Right Thing might be to buy five different books, but at approximately $100 a pop, this doesn't seem like a reasonable thing. Therefore, we're going to try some creative solutions:

• There will be no single required text in any area. This means that you can use earlier editions, cheaper books you can find used, etc. We will make some recommendations for books and for properties that better books have.

  • This will of course cause some confusion because different people will be reading different notations, but that's precisely the spice that makes Olin such an...um...interesting place.

  • Important disclaimer: This does NOT excuse students from accessing resources in order to learn the required material. The intent of this policy is to give you discretion on how you spend your time and money, but your solution should be no worse than acquiring texts and using them to learn. In particular, be sure that you get your hands on a decent resource for algorithms and for theory of computation, whatever your learning style dictates that may mean.

• The library will have copies of some books in each area. Of course, they're not going to have enough for 25 students to read simultaneously, but it's a start.

• The Computers and Cognition Lab also has a book collection that you are welcome to make use of. However, during the fall semester, we ask that these books not leave the CCL area as these are also the only instructor copies (i.e., if you take the book, Lynn may volunteer you to teach that class).

• We will make liberal use of on-line material where it's available, suitable, and locatable. We will also ask you to help in this effort by adding material that you find useful and by commenting on material that we're providing.
• We will develop our own materials. Each student will be responsible for helping to create course notes during the semester.

The major areas in which you might want (access to) a textbook are:

• == Algorithms ==

  The definitive book in this area at the moment appears to be Cormen. Although it's now out in second edition, the first edition is perfectly satisfactory. This is also a really wonderful book and one that those of you building a CS library may want to own. There are a large number of other algorithms books, many quite good. If you find one inexpensively, please verify that it covers

  • orders of growth (sometimes called big-O notation)

  • sorting
  • searching
  • hashing/hash tables
  • binary trees
  • graph algorithms, especially shortest path

  Ideally, it should also cover NP/NP-completeness, but this topic is often found in Complexity books as well.
  
  

  • Some alternative books include:

    • Sedgewick and Flajolet (claims to be more about analysis while Cormen is more about design...)

    • Rawlins (takes an alternative, more didactic approach to the material; topic order is very different but book is eminently readable)

    • Levitin (another very different organization of topics)

  Note that there are two traditional CS courses whose textbooks may have similar names: Algorithms, which is a second or third year course, and Data Structures, which is sometimes also called CS 2. Textbooks for a Data Structures/CS2 course are probably not really suitable for FOCS. (When in doubt, ask Lynn.) == Automata and Complexity Theory == There are really many reasonable choices here and no one book that stands out above the rest. A lot may depend on individual preferences: Do you like mathy proofs and very formal constructs or intuitive explanations with less notation? If you can find one that seems to suit you well and that doesn't break your budget, you might want to acquire a copy of an automata theory book. It should cover:

  • fininte state machines (AKA finite state automata), both deterministic and nondeterministic
  • regular expressions
  • context free grammars (AKA context free languages)
  • push-down automata (AKA stack machines)
  • Turing machines
  • the halting theorem
  • NP (AKA NP-completeness, NP-hardness); may also be covered in Algorithms books
  One heuristic I've been using is to look at the book's treatment of the Pumping Lemma. If it's not there, that's a bad sign, of course, but the way that it is either explained or proved or otherwise treated is probably a good indicator of how the authors approach the material overall.

  I personally am attracted to Hopcroft, Motwani, and Ullman and will always have a special place in my heart for Lewis and Papadimitrou. Both books are in second editions, but I would guess that the first edition of either would be fine; in the case of L&P I can definitely vouch for it. L&P feels particularly mathy to me, while Hopcroft seems like a more balanced book, but student styles will surely vary. I'm also looking forward to getting ahold of Sipser, which gets phenomenal reviews.

  Bottom line: If you like to acquire books, buy a good one. If you are the kind of person who doesn't look at a book after the semester's over, there are a lot of decent options in this area and you should find one that works for you. If you don't ever look at a book -- or will be OK with the common resources available -- that's OK too. But be sure to read the disclaimer, above. == Programming Languages ==

  Actually, you don't need to buy a programming languages book. However, I strongly recommend Friedman, Wand, and Haynes if you are interested in the topic. Note, however, that it is not a traditional programming languages book -- it doesn't cover lots of different languages -- but instead focuses directly on the process of language interpretation. It is a phenomenal book and a reasonable advanced scheme resource as well.

  In contrast, books like Tucker and Noonan and Appleby and VandeKoppe provide a broader survey of programming languages per se. A book like this is a good resource if you're looking for information on how various languages work. There are also some other marvelous scheme books (many of which go far beyond teaching the language itself) listed in that section, below.

  • == Scheme ==

  Scheme is a dialect of lisp, but it is sufficiently different from other lisps that you probably don't want to use a standard lisp introduction (and you certainly don't want a lisp reference). There's some decent online material -- including the reference manual for the current release -- but some people prefer books. I can certainly recommend: Hmm....This list is getting out of control. I think that's because so many people who write scheme books are really writing books about Important Ideas in Computer Science. Thus, there are many books in this area to recommend, but with very different flavors. Also, an amazing fraction of these books are available online, so you can browse before you buy....

• Structure and Interpretation of Computer Programs is a masterpiece, definitely worth owning for the serious computer scientist, overkill for our use (but I'd love for everyone to read it anyway). Fully available on the web! (AKA the Wizard book)

• How to Design Programs is beautiful, though I don't personally know it as well as SICP. HTDP is also available online, though -- like SICP -- also worth purchasing if it's the kind of thing you like to own (or read on paper). Again, overkill for this course, but not necessarily for your life.

• The Little Schemer and The Seasoned Schemer are smaller books that use a particular style that you'll love or hate, but they will definitely open your mind.... (Not available online as far as I can tell, and someone seems to have walked off with my Little Schemer, but Amazon's look inside this book will give you some sense of the style.)

• Simply Scheme is a good introductory CS book in scheme. I don't know The Schemer's Guide but it sounds similar.

• Dybvig's book is also good but more advanced/referency.

• I don't really know The Schematics of Computation but probably should.

• Found a ref to Teach yourself Scheme in Fixnum Days by Dorai Sitaram. No opinion yet, but I like the joke.

• Another misc ref to An Introduction To Scheme and its Implementation; again, no info.

• Also, Friedman et al. from the programming languages list belongs here as well. It's an advanced book but a brilliant one.

• See also SCSH, the scheme shell, and scheme48, guile, .... Also SLIB. Whew. I guess I got carried away...

  • == Prolog ==
  Katie compiled some resources elsewhere and I'm exhausted from Scheme. Web resources include:

  • gprolog is a nice interpreter; useful with this is the gprolog manual.

  • Guide to Programming has some good explanations, but isn't finished.

  • Programming Prolog: a first course is fairly exhaustive, but their copy editors seem be on vacation.

  • Fun with Prolog is short and sweet, though it assumes some basic familiarity.

  • Introduction to Prolog is comprehensive, if fast-paced.

  I'm sure there are also some good paper resources somewhere. (Clocksin and Mellish Programming in Prolog was nice to random-access, but it's a bit dated(?)) == Logic == This is probably not a separate book but a topic that you'll want covered somewhere. It's a better-than-average place to use online resources, given the role it will play in the course, but keep your eyes out for a decent chapter on logic in one of your books.

intent to add some specific references duly noted

• == Other topics == Not sure we're doing other things, but ML and IR are still on the maybe list.