A breadth-first search through the arts & sciences

Almost by accident, I started doing research in algorithmic game theory in my first semester here at UT (Fall ‘09). I had zero background in CS theory and my math background was pretty rusty because I was six years out of undergrad. The only grad level theory courses that are running this semester are Computational Learning Theory and Pseudorandomness. Both are interesting, and taught by great lecturers, but they’re not exactly introductory courses, so I grabbed a few books and I’ve been working through ‘em this semester on my long bus commute.

Most reviews don’t mentioned how suitable a book is for self-study, and books often claim they’re perfect for self-study when they don’t have worked solutions, or even any exercises, so it took a bit of trial and error to find a good set of books I could use to get the equivalent of a BS in CS (minus the areas I’m already familiar with, like computer architecture, operating systems, etc.). I know some people can read a monograph straight through and pick up the material, but I misunderstand things often enough that without some answers I can check against, I’ll be hopelessly lost (and not even realize it) within a few chapters. I hope this list is helpful for anyone else looking to do the same thing.

Apostol, Linear Algebra

I used this freshman year, back in 2000. Nine years ago! Phew! It has answers, but no worked solutions, and no answers to proofs, so if you get stuck, you’re stuck. It’s a great book to use as part of a class, but I didn’t want to work through it again, since I still remembered the solutions to the really hard problems I got stuck on, and knew I’d get stuck on other tough problems that I hadn’t tried, but without any resources for getting unstuck (other than my feeble brain).

As a bonus, you also get a calculus textbook. I really like that Apostol covers linear algebra before multivariable calculus, which takes a lot of the difficultly of multivariable caluclus.

Blyth and Robertson, Basic Linear Algebra and Further Linear Algebra

Like all the books in the Springer Undergraduate Mathematics Series (SUMS), this book was written with self-study in mind, and has a slew of worked solutions. These two books weren’t bad, but the exposition is overly detailed, compared to Apostol; that worked out well for me, since this was the second math book I’d read in years, but it might be tedious if you’re not so badly out of practice. I wasn’t a fan of the exercises. There were a lot of uninspired number pushing problems, and few problems that required creativity, or interesting proofs. Luckly, that weakness can be fixed by using the exercises for MIT’s Linear Algebra course. That course has video lectures, too, but I’ve never liked lectures. You can read an entire chapter in the time it takes to explain one or two examples, even if you use MPlayer or WMP to play the lectures at 2x speed.

If I were going to do it over again, I might use Strang’s Introduction to Linear Algebra instead, since it follows the MIT OCW problems more closely. The reason I didn’t use Strang is that it follows what you might call the strict axiomatic approach. For example, Blyth starts by defining a linear mapping, and then shows that the standard definition of matrix multiplication is the only definition that makes sense. Strang, on the other hand, starts with the standard definition of matrix multiplication, and then proves a bunch of properties about it.

Graham, Knuth, and Patashnik, Concrete Mathematics: A Foundation for Computer Science

This book has entertaining exercises, but I can’t figure out who it’s targeted at. On the one hand, explanations assume little background, going into so much detail that an unmotivated high school student could follow all the derivations. On the other hand, the book is mostly concerned with calculations and symbol pushing, and I’m not sure how useful knowing how to do all these calculations sans theory would be to a high school student. After working through the first few chapters of this book, I feel like I’m a lot better at working with explicit sums, recurrences, etc., but I could have gotten that by grabbing the appropriate volume from Schaum’s Outlines. The preface to the text says that you’ll get so good at manipulating exact quantities that you won’t need to resort to asymptotic analysis, but asymptotics are still easier; in all my classes, and in my limited experience with research, everyone still uses asymptotics, so I don’t know how useful all this has been.

I’ll take the Rawlsian approach to reading the classics and assume that the authors have good reason for writing the text the way they did, that I’m just missing the point. Considering how well regarded this book is, that’s certainly true, but I just don’t get it. I’d appreciate it if someone could enlighten me in the comments.

Dasgupta, Papadimitriou, and Vazirani, Algorithms

When I told people I was using this text, they said I should use CLRS or Kleinberg instead, because they’re much more comprehensive, but I think the topic selection is a feature and not a bug for a first algorithms text. A typical introductory algorithms course will barely scratch the surface of CLRS, with the professor picking selected topics. Since I had no background in the area, and I wasn’t sure how to figure out which topics are important, using a book that wasn’t comprehensive was helpful. I’ve since used CLRS as a reference, and I find Dasgupta’s exposition clearer (and equally concise), when they both cover the same topic. Kleinberg has both great exposition and broad coverage, but the solutions aren’t publicly available.

For self-study, I really like the parenthetical notes that ask you “do you understand why?”, which force you to make sure you’re really understanding the material as you read it. You can, allegedly, get solutions to the book if you register your copy, but I used the problems and solutions from Wanger’s CS 170 course at Stanford, instead. The solutions have been taken down, but this book is used widely enough that there should be no problem finding a semester’s worth of problems.

If you really have a burning desire to use CLRS, Peteris Krumins has a nice set of notes up, with links to video lectures from the MIT OCW course.

Levitin, Introduction to the Design and Analysis of Algorithms

I ordered this off amazon after seeing these two blurbs: “Other learning-enhancement features include chapter summaries, hints to the exercises, and a detailed solution manual.” and “Student learning is further supported by exercise hints and chapter summaries.” One of these blurbs is even printed on the book itself, but after getting the book, the only self-study resources I could find were some yahoo answers posts asking where you could find hints or solutions, so I used Dasgupta instead.

Jukna, Extremal Combinatorics: With Applications in Computer Science

I’m always wary when a book claims to be self-contained, but this time the claim is actually true! This was the first book I read after my hiatus from academia, and I managed to work through the better part of it without any references. It was really slow going for me, though; I originally assumed that was because it had been so long since I’d solved anything close to a non-trivial problem, but after staring at one rather dense passage on the Linear Algebra Method for an hour without making any progress, I asked a local prof for some clarification, and he suggested I look at Babai and Frankl for a clearer exposition of that material, and Alon and Spencer for the Probabilistic Method.

Despite having many more exercises, and going into much more depth, I’m getting through Babai and Frankl more quickly than I managed to get through this. If I had to do it over again, I would have read Babai and Frankl and Alon and Spencer before cracking open this book. That isn’t to say this isn’t a great book — it has CS applications (including recently proven results) interleaved with all the math, which is nice; if you aren’t as out of practice as I was, you can probably tackle this no problem with just a high school mathematics background.

The only caveat for self-study is that this book doesn’t include solutions, but a decent portion of the problems have hints, and the hints are strong enough that it’s trivial to find the solution given the hint, so you can stick to exercise with hints if you don’t want to worry about getting stuck with no way out.

Babai and Frankl, Linear Algebra Methods in Combinatorics with Applications to Geometry and Computer Science

This is the most fun book I’ve read this semester. I haven’t had time to work through the entire book, but that parts I’ve done have clear exposition and problems that test your creativity without being impossibly hard. It’s too bad the newest available edition is a “preliminary version” that was last updated in 1992. I’d love to see this book completed.

This is the first book in this list that requires more than basic high school math. Any of the linear algebra books mentioned above should be enough to get you through this. This book isn’t available in many libraries, so if you want to make sure you have enough background to handle this book before buying, these short IMOP tutorials by Po-Shen Loh. Those will also give you a feel for the types of problems this book covers. If you think those are fun, you’ll love this book.

Durbin, Eddy, Krogh, and Mitchison, Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids, and Borodovsky and Ekishiva, Problems and Solutions in Biological Sequence Analysis

I tried working through these before reading an intro probability text, which was a bad idea. This book has an introductory section on probability, but it didn’t have enough exercises to hammer in the level of understanding necessary to effortlessly read the text. I think I could handle this now, but I’ll wait until gnofai finishes their MCMC tutorial before revisiting this.

Shoham and Leyton-Brown, Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations

A lot of people overlook this book because of the title, but if you have no background in the field, this is the gentlest introduction to algorithmic game theory available. I’ve recommended this book to a few people who were struggling with Nisan’s Algorithmic Game Theory book, and they’ve all loved it. This book contains all of the game theory, CS, and economics background you’ll need to get through it. Unfortunately, it doesn’t have worked exercises, but when I was searching for problems, I ran across Kevin Leyton-Brown’s Multiagent Systems class, and he was nice enough to email me the solutions, as long as I emailed him my answers to the problems, to prove that I was actually working the problems. Very cool. A quick google search shows that, right now, you can get problems and solutions from an old course at Stanford.

Nisan, Roughgarden, Tardos, and Vazirani, Algorithmic Game Theory

I loved this book for what it was: a survey of results of all aspects of algorithmic game theory. However, it’s not an introductory text that you’d want to read straight through; that’s not a criticism, since the book is that way by design. Just sayin’, since I’ve seen a lot of people try to read it cover-to-cover as an intro. For instance, chapter five is basically the Devanur, Papadimitriou, Saberi, and Vazirani JACM paper, Market Equilibruim via a Primal-Dual Algorithm for a Convex Program, with a bit more motivation, and some related problems thrown in. It’s a brilliant result, and well written to boot, but that’s probably not the fifth thing you want to read about if you’re just starting out.

Krishna, Auction Theory

This is pretty much the only game in town for a comprehensive, modern, introduction to auction theory. It’s completely self-contained in terms of economics, and you could get away with only having basic calculus and probability, cribbing from the appendices in the back for the required knowledge about stochastic orders, order statistics, and affiliated random variables, but for one thing. The book doesn’t have exercises, so if you want to check your understand as you go, you’ll have to cover up the examples as you’re reading and see if you can work through them as they’re developed, which might tough to do without a casual facility for those topics, since there’s only one example of each “type”, so you can’t get an idea for how a problem should be solved, and then use that prototype on future examples.

Sipser, Introduction to the Theory of Computation

Like Dasgupta, this is another book I was warned away from, because it’s neither rigorous nor comprehensive; in general, I view that as an advantage in an introductory text, since I’d rather see intuition than symbol pushing, but I would have preferred a bit more rigor here. A lot of the proofs are given in a “proof sketch” level of detail, and it would have been nice to be able to see everything without having to refer to another text. Also, a lot of important results are pushed into the exercises (e.g., Rice’s Theorem), so you probably won’t get much out of this if you don’t do key exercises. Some exercises have solutions, but not all do, and most of the key exercises don’t, which is non-ideal for self-study.

One criticism that’s commonly leveled against this book is that the topic selection is dated. I don’t know enough about the area to comment; I’ve been told that Arora’s Computational Complexity: A Modern Approach has a nice up to date selection of topics, but I could only find Hebrew solutions, so I went with Sipser for self-study, and used Arora to supplement the topics. Arora has excellent exposition, so it’s a shame that book doesn’t include any solutions at all.

Gelman, Carlin, Stern, and Rubin, Bayesian Data Analysis

This book has very well written solutions to a lot of the problems, and it claims to require nothing beyond introductory calculus and probability. While the claim is technically true, but I don’t think you’ll get much out of it if that’s all the background you have. For instance, they state the formula for Fisher information in the text, and one of the problems asks you to calculate the Fisher information. I did the calculation, and got the right answer, proving that I could push symbols around according to some definition, but I still have no idea what the Fisher information really represents, or why you’d ever want to find it. This might be a great text if you have basic statistics under your belt, but I’d pass on it if, like me, you don’t.

Osborne and Rubinstein, A Course in Game Theory

This comprehensive book covers all the results of classical game theory. The preface notes that it’s designed to be a graduate level text, but (except for one section), it’s all accessible with no background whatsoever. There’s one scary section right at the beginning, where Kakutatni’s fixed point theorem is used in a couple of exercises relating to the existence of Nash equilibria, but it gets easier from there.

This book has the perfect setup for self-study, with exercises sprinkled throughout the text. Ironically, it’s only useful for self-study in spite of the best efforts of the authors — on their website, they mention that they’re only posting solutions because the solutions had been leaked to so many people that they might as well just put them up, even though they’d prefer to not have all solutions publicly available.

Bertsekas, Introduction to Probability

I picked this up in order to get the necessary probability background to read an intro stats text, so that Gelman’s Bayesian Data Analysis would be comprehensible. For that, it was perfect. Signal processing EE folks tell me it has all the probability necessary for them, too.

For CS theory, it could use more coverage on tail bounds, and it has nothing on information theory, martingales, etc. I ended up using Mitzenmacher and Upfal to supplement for those topics. Unfortunately, their book doesn’t have publicly available solutions, so it may be best to use something like Bertsekas, with Mitzenmacher as a supplement, even if you’re only interested in the CS side of things.

In addition to having solutions to all the exercises, there are multiple years of extra problems and exams for 6.041 / 6.431 the MIT website.

Hauge and Hunter, The Self-Coached Climber: The Guide to Movement Training Performance

Ok, so this isn’t CS related, but there seem to be a disproportinately large number of climbers among CS/EE types, so here’s my quick review. Unlike most climbing books (e.g., John Long’s series of forty identical books with different pictures on the cover), this book really covers technique. I don’t know if how useful it would be for experienced climbers, but as a noob, reading this book and applying the techniques gave me an immediate improvement of ~ 1 V grade.

To be continued…

I decided to try blogging again after re-reading Steve Yegge’s old post where he mentions that he only spends three hours a week blogging. If he can that much in a few hours, I can surely write the occasional half-hour blog post; I’m committing half an hour a week to blogging: I’ll post whatever I can write in half an hour per week, even if that results in incomplete posts (like this one). I’ll extend (and perhaps proofread) this post next week, if I have any time left in my half-hour quota after writing a post or two. Considering our blogging track record, I doubt I’ll ever finish this unless I publish this embarrassingly unedited version now, so here goes nothing :-)

The style of this post was inspired by the Chicago Mathematics Bibliography, but it’s not nearly as useful because it doesn’t compare different books. I’ll try to remedy that, as the time quota permits.