Sunday, August 17, 2008

Graduate Algorithms, Fall 08

I needed to feel grounded, I needed to feel the inspiration for algorithms at a base level. So, I decided to teach a graduate algorithms course this fall. Many of you have taught such a course, even several times. There are terrific notes and homework exercises on the web. I am sure each of us would use our own notes to supplement the material out there. Question is, should one even recommend a textbook for the students? I feel like I am bumping against some ethical question here, but the question as it arose in mind was just technical, that is, are the books useful beyond the material on the web that is easily accessible?

ps: As an aside, what textbook to recommend? CLRS is rigorous, but bulky. Kleinberg-Tardos is new on the block, emphasizes the creative design part, but may be wordy. There is the somewhat dated, terse gem by Dexter Kozen. More recent, surprisingly under my radar, book by Dasgupta, Papadimitriou and Vazirani. Etc.

12 Comments:

Blogger Suresh Venkatasubramanian said...

It's a tough call, and REALLY depends on the crowd you're teaching to. I've been struggling with this for two year, and although I have a formula that's stable (review of greedy/d&c/dp/flows, np-hardness, approximations, randomization, misc lectures), I can't say it's ideal.

The main problem with a grad algos class is the "review or not to review" question. And the textbook you use is controlled by this: KT is good for grad students because it covers some more advanced topics than CLRS. the new Vazirani et al book is nice, but it doesn't have any breadth and that can be a pain when setting homeworks, finding material etc.

Ultimately your own notes are ideal: but it takes a lot more work: unless you're planning to do this regularly, I'd go with KT.

11:12 AM  
Blogger Tyler said...

My grad-level algorithms class was taught by Victor Shoup, and I don't think I ever looked at our textbook because I found the class notes to be completely sufficient. That is meant solely as a compliment to the possibilities of good teaching (I still refer to texts on a regular basis for many technical details I struggle to remember).

At the same time, different students learn differently, and I'm willing to bet some would complain if there were no text, no matter how good the teaching. With that in mind, it might make sense to choose a detailed syllabus and a style for the homeworks, and _then_ consider which texts make the most sense. Class is more fun if you're teaching what you want to :)

Also: I think online resources have reached the point that they can seriously substitute for a hardcopy reference (usually without exercises, though). For example, a combination of wikipedia and open notes from MIT can cover a lot.

4:19 PM  
Blogger JeffE said...

I use my own notes. I don't officially recommend any textbook.

Unofficially, I recommend Kleinberg and Tardos, despite its unabashed tendency to utilize language somewhat more profligately than the task at hand truly requires, often to the detriment of the readers' understanding and mastery of the algorithmic material being presenting for consideration. Also, it's wordy.

CLRS is not only bulky, but its levels of rigor, detail, and clarity vary wildly. Some chapters are good; others are horrible. I recommend it only for stunning oxen.

I adore Dasgupta's book as a textbook for undergraduates. It's pithy, it's well-written, it covers the right material at the right pace, and it's not obscenely expensive. But I don't think it's meaty enough for CS graduate students.

8:53 PM  
Blogger Unknown said...

I cannot recommend any particular book at the moment, as I don't have enough experience, but I like DPV very much. It is indeed very well-written and concise (and it is still available online). Some time ago I started collecting links to courses and books on algorithms: http://logic.pdmi.ras.ru/~kulikov/mylinks.html
This is just a set of links without any order, but may be useful probably.

11:56 PM  
Anonymous Anonymous said...

* Hi Jeff, Your notes were one of the items I had in mind when I said there are terrific notes on the web! :)

* Hi Alexander, Thanks for gathering those links, it is very useful.

* Hi All: Thanks for feedback on DPV, need for homework, etc.

This is going to be fun.
-- metoo

12:33 PM  
Anonymous Anonymous said...

If you are looking to reach out to non-theory students, I think Kleinberg-Tardos is best. On the other hand, if you want it to be a "hard-core theory class", then notes may be the better way to go.

6:04 PM  
Anonymous Anonymous said...

Lectures on Algorithms -Dexter Kozen. Extremely clear and crisp.

3:06 AM  
Anonymous Anonymous said...

my personal favorites (for a slightly advanced grad course) are Kozen's book and Hastad's lecture notes. Both of these are really notes for the teacher to use, not for the students to learn from. IMHO, textbooks like CLRS or KT have less value for teachers and more value for students, especially the exercises and problems.

10:55 AM  
Anonymous GRE said...

Thanks for your share! I think this information is helpful for everyone. I'm doing practice GMAT here: gmatonlinetest.com . I hope it's useful for GMAT test takers.

8:52 PM  
Anonymous Cheap Viagra said...

you are very brave, I mean teach something like algorithms is so risky, I never was good with this matter, and the true I still been bad with this one.

11:22 AM  
Anonymous Graduate thesis said...

Hey, Really great work,I would like to join your blog anyway so please continue sharing with us,
Graduate thesis

1:45 PM  
Anonymous High School Diploma Online said...

I like the information that you shown is hard to faith and many superbly I liked the way you afford things here.

2:50 AM  

Post a Comment

<< Home