CS Readings

This page contains links to readings on the subject of Computer Science. They are meant to teach theoretical concepts; though each work may use a specific programming language to explain things, the concepts they teach should be applicable to any programming language.

I originally orginized this page from “easiest” to “hardest” to read, but after I thought about it, it doesn’t work very well. So, now I’m orginizing these works by programming abstraction level. That is, topics dealing with low-level programming concepts (e.g. machine language) will come first, followed by high-level language concepts (e.g. object-oriented programming theory), and ending with high-level software engineering concepts (e.g. design patterns or software development). This organization reflects the idea that programmers need to know the fundamentals before they learn how and why those fundamentals are abstracted. Not coincidentally, it also reflects the history of programming itself.

But it is often just as difficult to learn “low-level” concepts as it is to learn abstract concepts. (That’s one reason those abstractions exist in the first place.) So, I’ve included my (entirely biased and subjective) rating of how easy it is to read and understand each work. Easy works should be comprehensible to any first-year programming student; moderate works require more in-depth knowledge; and advanced works require a deep understanding of programming concepts (and likely some college-level math skills). Of course, these are theoretical computer scientists we’re talking about, and the author’s unnecessary wordiness may bump the difficulty up a level.

Everything on this page is free (“as in beer”), and I favor sources that are also libre (“free as in freedom”). This is because I believe that knowledge and learning should be as open as possible. My ultimate goal is to provide libre works that contain all the knowledge from the textbooks of every one of my theoretical CS courses. (Or at least the ones that weren’t a waste of time.)

This page will be updated whenever I come across a work that I think is well-written and informative. So, check back occasionally.

Articles and Papers

Fundamental Concepts in Programming Languages by Christopher Strachey (PDF)
Rating: moderate
Absolutely essential reading if you want to understand L-values, R-values, and the different types of polymorphism. It was written in 1967, so just ignore the references to Algol. Oh, and remember the thing I said about “unnecessary wordiness?” I was talking about this paper.

Object-Oriented Programming with Objective-C from the Apple Developer Library (PDF)
Rating: easy
Despite the name, it has very little to do with Objective-C. It is mainly an introduction to object-oriented programming, theory, and terminology.

Big O notation (PDF)
Rating: easy
This is a very good introduction to big O notation, used to determine the efficiency of algorithms (among other things). The paper includes a handy guide to calculating big O complexities from specific code blocks. It is a handout for MIT course 16.070, Introduction to Computers and Programming. I’m not entirely sure who wrote it.

Queuing Analysis by William Stallings (PDF)
Rating: advanced
Queuing theory has a lot of useful applications, but especially in operating system design and network analysis. But for whatever reason, it’s not covered in that many CS courses – even my operating systems book doesn’t cover it. You should still learn it, or at least know about it, so read away. (By the way: I’ve always spelled it “queueing,” but I guess that’s fallen out of favor lately.)

This paper is one of the downloads available at ElectronicsTeacher.com, and the other downloads are also pretty useful.

Books

Programming from the Ground Up by Jonathan Bartlett (PDF)
Rating: moderate
This book covers fundamental programming concepts, like functions, files, and memory management. But it explains these concepts using assembly language – specifically, the AT&T syntax for GNU/Linux on x86 processors. After reading this book, you should have a pretty decent understanding of how computer programs end up being implemented on the computer hardware.

The link above is to a PDF where the pages are “book size” (roughly 7.5″ x 9.25″). I found this size to be easier to read digitally, but if you want to print it out, there is also a PDF version whose pages are LTR size (8.5″ x 11″).

Open Data Structures by Pat Morin
Rating: moderate
This website is the home to three books about data structures, differing only in the programming language used (Java, C++, or “pseudocode” – Python sources are available for this one). All are libre; they available as PDF’s or as HTML pages, and LaTeX sources are also available.

The books do a fairly good job of covering all the “classic” data structures (hash tables, BST’s) as well as a couple that are not so widely covered (scapegoat trees, skiplists). Some mathematical knowledge is required, but it’s not too horrible (logarithms, big-Oh notation, some probability theory), and it’s all reviewed in the books.

Introduction to Theory of Computation by Anil Maheshwari and Michiel Smid (PDF)
Rating: advanced
A free textbook for COMP 3803 at Carleton University, an undergraduate course on the theory of computation. It covers such topics as finite automata, context-free grammars, Turing machines, decidability, and P vs. NP complexity.

Compiler Design by Seth D. Bergmann
Rating: advanced
These books cover compiler theory: finite state machines, regular languages, top-down and bottom-up parsing, code generation, register allocation, optimization, and so forth. Originally written to parse a subset of Pascal, it has since been expanded into versions that cover C/C++ and Java.

Operating Systems: Three Easy Pieces by Remzi and Andrea Arpaci-Dusseau
Rating: advanced
This is a continuously-evolving book about operating system theory: CPU scheduling algorithms, virtual memory, page tables, concurrency, mutex locks and semaphores, file system implementations, and so forth. Like most books on operating systems, it focuses mainly on POSIX-compiant OS’s. You have to buy the book if you want a single PDF file, but each chapter can be downloaded separately. There’s actually a reason for that; read Remzi’s blog entry on why textbooks should be free for details.

Learning JavaScript Design Patterns by Addy Osmani
Rating: easy/moderate
Though it uses JavaScript as the language of choice, this book is really about design patterns. Fully understanding those patterns in the context of JavaScript may require some moderate knowledge (e.g. of closures), but if you just want to learn about the patterns themselves, then it’s not difficult at all (hence the two ratings).

Software Architecture by A. Bijlsma, B.J. Heeren, E.E. Roubtsova, and S. Stuurman
Rating: moderate
This book deals with software architecture – the high-level design of complex software systems. Subjects include quality assurance, requirements engineering, UML, and enterprise application patterns. It is part of the Free Technology Academy, which has other interesting (and libre) materials.

The book itself is fairly easy to understand, and could be followed by any programmer, even one without much coding experience. I rated it “moderate” simply because software architecture is a vast and complicated subject.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s