Fog Creek Software
Discussion Board




homebrew CS education

Nick Hebb wrote:

I’m gathering a home-brew BS in CS list of study topics and books to read. Suggestions would be helpful. In my view, many books on Joel’s list and the books others have suggested fall into the “already have a CS degree” category. I’m looking for the subject matters and supporting texts for a core CS degree. I’m scanned some university sites, but my fear is the textbooks are often dry ones written by someone in CS department staff (I’ve actually seen quite a few of these). I want a list of good ones.

Timothy Falconer
Wednesday, March 27, 2002

Any core CS education will include:

1. structured programming
2. data structures
3. algorithms
4. programming languages
5. operating systems

with a few goodies:

6. object-oriented programming
7. discrete structures
8. compiler design
9. c and unix

If you're learning at home, I'd try a good survey book on programming languages (can't recommend a recent one) and definately operating systems (the one by the guy that made minux was pretty good).

Timothy Falconer
Wednesday, March 27, 2002

Computer architecture:  CPU's, multiplexers, gates, etc)  Maybe some Assembler

AI
Graphics
OS

What does stuff like finite automata, state machines (Turing?) etc fall under?    General computing?

And don't forget some core Math classes, dealing with sets, groups, functions, etc

Bella
Wednesday, March 27, 2002

Some CS books I like:

"Great Ideas in Computer Science" is a light introduction to many important areas of CS, from compiler design to noncomputability. There is a new edition that uses Java, but don't discount it because of that. :) The book has some exercises where the reader must generate Java bytecodes by hand.

"Introduction to Algorithms" (aka The CLR Book) is a classic algorithms book. No Java or C. Just pseudo-code and proofs.

Hennessy and Patterson's "Computer Architecture : A Quantitative Approach" and "Computer organization and design : The hardware/software interface" are great books about processor design.

Coulouris' "Distributed Systems: Concepts and Design" is a nice academic book about distributed systems design and theory.

Banana Fred
Wednesday, March 27, 2002

Tanenbaum's (that Minix guy) has the best intro book for operating systems: "Modern Operating Systems". He also has some books about networks and distributed systems. They can be a little "light" but they are all informative and easy to read.

Banana Fred
Wednesday, March 27, 2002

>>What does stuff like finite automata, state machines (Turing?) etc fall under?

  That would be Computational Theory.  A book on this topic was already suggested on this forum.  ( http://www.amazon.com/exec/obidos/ASIN/053494728X/qid=1016358761/sr=1-1/ref=sr_1_1/002-1164014-8317633
).

  I think we could include Databases, as a topic of study ( http://www.amazon.com/exec/obidos/ASIN/0201385902/qid=1017255681/sr=2-1/ref=sr_2_1/002-7386107-5633630 )

  Regards.

Ricardo Antunes da Costa
Wednesday, March 27, 2002

Don't forget object and data modeling and database design.  Too many developers think of the database when it's too late to fix the design.

Colin Davies
Wednesday, March 27, 2002

And something to do with networking, perhaps. I liked _TCP/IP Illustrated (volume 1): The Protocols_ as an introduction to IP network protocols; then when you know what "serialization" is, you're ready for RPC, and distributed computing (note that this is a theory how it works book, not a practice what your API is book). It probably is dry ... but, much wetter than the RFCs. Incidentally, most of my favourite computer books are published by Addison Wesley, to the extent that other things being equal (e.g. online shopping) I'll pick it over another one if both seem to cover a same topic.

Christopher Wells
Wednesday, March 27, 2002

I'm looking through my bookshelf for some of the books I used Oh so long ago....
They are:
Kernigan/Pike- the unix programming environment
C.E Date-an introduction to Database Systems
Feldman-Data Structures in Modula-2
TAHA-Operations Research
Firth-An introduction to Pascal
I've thrown the rest out and for some reason I hung on to these, these come from way back in 1984, gee am I that old?

Tony
Wednesday, March 27, 2002

I appreciate all the input.  There's a lot of overlap with the list of textbooks I compiled from the classes offerred at a local school (Oregon Graduate Institute) ...

Data Structures and Discrete Mathematics
- Algorithms in C++, Robert Sedgewick
- Discrete Mathematics, Seymour Lipschutz and Marc Lipson

Introduction to Software Engineering
- Software Engineering, Ian Sommerville
- The Mythical Man-Month, Fred Brooks

Software Engineering Processes
- Software Process Improvement, Edited by Robin Hunt and Richard Thayer

Object Oriented Analysis and Design
- Doing Hard Time: Developing Real-time Systems with UML, B. Douglass
- The Unified Modeling Language Reference Manual, Rumbaugh, Jacobson, Booch

Object Oriented Programming
- Squeak: Object-Oriented Design with Multimedia Applications, Mark Guzdial
- The Java Programming Language, Arnold, Gosling, Holmes

Principles of Compiler Design
- No text listing

Introduction to Operating Systems
- Modern Operating Systems, Andrew Tanenbaum

Introduction to Database Systems
- Database Management Systems, Ramakrishnan/Gehrke
- SQL: 1999 Understanding Relational Language Components, Simon Melton

Distributed Computing Systems
- Distributed Systems: Concepts and Design, Coulouris, Dollimore, Kindberg

Software Design and Development
- eXtreme Programming eXplained, Kent Beck
- Refactoring: Improving the Design of Existing Code, Martin Fowler
- Object-Oriented Software Development Using Java, Xiaoping Jia,

Introduction to Computer Architecture
- Computer Architecture: A Quantitative Approach, J. L. Hennessy and D. A. Patterson
- Parallel I/O for High Performance Computing, John M. May

Analysis and Design of Algorithms
- Introduction to Algorithms, Cormen, Leiserson, Rivest, and Stein.

Automata and Formal Languages
- Introduction to Automata Theory, Languages, and Computation, J.H.Hopcroft, R.Motwani, J.D.Ullman


So my next questions are:

(1) Any of these texts stand out as really awful.

(2) How useful are the abstract subjects in your day-to-day jobs?  I'm speaking here specifically about the automata and the algorithms classes.

(3) Since this list is from an MS program and the list of subjects overlaps with a lot of with everyone's BS subjects (no pun intended - well, maybe), would you say that this program is just retreading a lot of undergraduate stuff and charging graduate tuition rates?

I ask because I'm considering either my "home brew BS in CS" plan or fulfulling the undergraduate prerequisites (such as the Data Structures class listed at the top) and then enrolling for a MS degree.

Nick Hebb
Thursday, March 28, 2002

Bella> What does stuff like finite automata, state machines (Turing?) etc fall under? General computing?


Algorithms and Abstract Data Types?

http://www.nist.gov/dads/termsArea.html

http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/ds_ToC.html

Ged Byrne
Thursday, March 28, 2002

Nick Wrote:
> (1) Any of these texts stand out as really awful.

Academic books tend to be dry and very "formal", and it doesn't have to be. However, sometimes you have to suck it up and just go through the steps. Maybe you'll be enlightened and maybe you won't. It very much depends on the class of problems that you want to solve.

BTW, for Compilers, the de-facto book would be the Dragon Book, "Compilers, Principles, Techniques, and Tools" by Aho, Sethi, and Ullman.

> (2) How useful are the abstract subjects in your day-to-day jobs? I'm speaking here specifically about the automata and the algorithms classes.

We'll, as we speak, you're using a web browser, right? A web browser contains a html/xml parser, which, from theory of computation is basically a stack machine (how else would you match your open and close tags?) The C/C++ preprocessor is has NP-Complete complexity, yet we use it everyday because the constant multiplier for it is so low. Even something simple like data integration involves parsing and recursive data structures.

If you're building simple business systems (forms, reports, notifications), then I would say that a CS degree is marginally useful from a day to day basis, since most of the time your effort is spent figuring out how to deal with the database. Same goes for database driven web pages. That's something you can get out of a wrox/21days book.

However, if your software has more prongs in it, just dealing with the complexity and reducing it to fundamental CS-like models is very very useful. This is especially true when data models get huge, and you have to search and store the data. Figuring out how to model data according to how it is used by the end user is very important. Heck, even string searching has algorithms (Knuth-Morris-Pratt, Boyer-Moore). Without them, it'd be hard for our GUI's to be as "snappy" as they are. The modern state of computing has less to do with actual Computation insofar as much as data storage and retrieval.

> (3) Since this list is from an MS program and the list of subjects overlaps with a lot of with everyone's BS subjects (no pun intended - well, maybe), would you say that this program is just retreading a lot of undergraduate stuff and charging graduate tuition rates?

Graduate programs vary in quality. My personal opinion is that a MS in CS is not terribly useful unless you went to a well known school and were trying to raise funding for you .com :-P. It all depends on the quality and talent of the students and their peers. Having professors and TA's who do research in the respective fields does help with digesting some of the more esoteric concepts. YMMV obviously. Perhaps in the future, we'll have "professional schools" of software design, much like law and medicine.

BTW, for you self educators, MIT is starting to put their course notes online. A lot of UC Schools actually have their course syllabi in the departmental webpages, and if you surf hard enough, you can actually download the problems sets.

James Wann
Thursday, March 28, 2002

Another book I'd recommend:  _The Science of Programming_ by David Gries.  I consider this the de facto standard introduction to the field of program correctness.  It's not a practical programming book by any means; it has a lot of proofs in it.  However, it will give you a sense of how to prove that a given program will always work, the amount of work involved in deriving such proof, and most importantly it should convince you that any program could at least theoretically be made 100% bug-free.

Paul Brinkley
Thursday, March 28, 2002

James, thanks for the clarification.  I had a feeling that if you peeled back several letters of abstraction, you would find the 'science' in 'computer science'.

Small aside - I've looked at a few of the colleges sites and a lot of the profs have their lectures and exercises posted in Postscript and PDF.  Since the PDF print quality is so bad, I was wondering whether the Postscript would be better. I've tried looking for a good freeware postscript viewer in the past, without much success.  Any recommendations?

Nick Hebb
Thursday, March 28, 2002

Most of those books from your local school are good books. However, I did see that name of one of the most hated books from my undergrad CS work: Hopcroft and Ullman's "Introduction to Automata Theory". This is a dense, horribly written book. It is usually used as a theory book for a compiler course. If you are interested in automata theory, there is probably a better book..

Banana Fred
Thursday, March 28, 2002

Tony recommended:
Kernigan/Pike- the unix programming environment

I don't want a 'me too' comment, but I'll just add that I never quite understood the point of C (or even Unix) until I read this book.  Extremely readable and non-timewasting.

Ricardo also recommended the Sipser book on Computation and CJ Date's on Databases.  Again, likely the best books in their fields, but I'd recommend looking through the intro (0th chapter?) of Sipser before going on to Date.  Things would go 100X more smoothly.

Richard J.
Thursday, March 28, 2002

The Arsdigita University used to offer a full CS education.

But all their lectures are still available as streaming video online http://aduni.org/courses/

Matthew Lock
Thursday, March 28, 2002

Might try the <Programming Language name> in Plain English series of books. For sample problems, try looking for sample Computer Science problems from the AP tests (it is C++, but it should give a good idea of what areas you are weak on).

Masterlode
Thursday, March 28, 2002

*  Recent Topics

*  Fog Creek Home