|
 |
|
|
|
Didn't quite know where this should go, and I apologize if something like this has already been posted. But ...
I was nosing through the shelves at the UCI bookstore today, quite unsuspectingly, and in the mathematics section to boot, wondering innocently how I might supplement my knowledge of discrete math when I was quite suddenly taken by surprise by a new title: "Programming Challenges" by Steven S. Skiena and Miguel A. Revilla, subtitled "The Programming Contest Training Manual". I think most everyone here will recognize Skiena's name as the author of "The Algorithm Design Manual", which is quite good, although I think a bit cursory in parts.
The book is a list of challenges culled from the Online Judge at http://online-judge.uva.es ... The problems listed in the book are a selection taken from the literally thousands available at that site, and the authors purport that the included problems, which are organized by type of approach needed to solve them, are among the very best, most interesting, and most effective in their being used to illustrate problem approaches. Chapters include an introduction to the mechanism used for submissions at the Online Judge site and also for the book's site, programming-challenges.com, and also chapters on Strings, Sorting, Arithmetic and Algebra, Combinatorics, Number Theory, Backtracking, Graphs, Dynamic Programming and more, oh so much more.
The book lists problem types, suggestions and brief tutorials, which amount to elaborated hints, for solving the problems, and guides you through a course of the kinds of problems you'll find on TopCoder. I haven't worked through anything in depth yet, so I can't comment on quality of coverage or content, but I can say that it looks promising and I'm looking forward to it. Skiena's other book has proven interesting.
There's a short section in the back which talks favorably about TopCoder. The book weighs in at US$32.95, which is the price I bought it at because I'm too much of a geek to wait, but you can get it on Amazon right now for 30% off, and free shipping to boot. My initial impression is that working through this organized set of problems would be a great help in getting a handle on the types of things TopCoder throws at you in the SRMs. Since I've been hunting for a categorized selection of problems for just such a use, this was a real find for me. If anyone else has more info, please add it.
Oh, and sorry if this has been mentioned previously.
Peace. |
|
|
|
|
interesting book but too expensive |
|
|
|
|
Yeah, this book has been mentioned a couple times but it
won't hurt to mention it again.
Hmm... Amazon.com has 30% off (US $23.07) but Amazon.ca
doesn't (CDN $52.95)...? :( |
|
|
|
|
This looks like a good book and I'm probably going to go ahead and buy it. While I'm at it can anyone recommend any good reference books to go with my order? I have a ton of big bulky reference/teaching books that just have too much excess junk to be of any real use in the heat of a competition :) I usually code just C++ but may consider buying all 3 (C++/Java/C#) if I find a good series. |
|
|
|
|
There're many things you can only learn by practice... |
|
|
|
|
.. and perfect practice makes perfect. It's always good to have a little direction. |
|
|
|
|
The book I and others recommend for TopCoder is
Introduction to Algorithms, Second Edition
by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
It's fat but worth it. Not that useful *during* a competition, but who uses books during a competition? |
|
|
|
|
For quick C++ info, I usually turn to "The C++ Programmer's Reference" by Herbert Schildt. For more in depth info, check "C++, The Complete Reference" by the same author. |
|
|
|
|
I second radeye's mention of CLR as one to have on your shelf. (Aside: I remember it variously being called "The Big White Book" (since it's white) and "The Big Red Book" (since the cover photo is of a piece of art called 'Big Red'))
Personally, I grew up with Sedgewick's 'Algorithms' (the 1980 first edition with code fragments in Pascal). It's a bit less formal, so it covers more ground per page (and drops lots of enticing hints about things it doesn't cover). I'd suggest it, or a book like it, as more suitable for competition training than CLR -- you need lots of tips & tricks and examples to hone your intuition more than you need rigor. (I know I usually come across a pedantic theory guy, but that came *after* being an intuitive hacker -- and I think it's more productive to learn things in that order). My biggest beef with CLR is that it just doesn't cover a whole lot of stuff (I don't recall any geometry in there, for instance). What it covers, it covers exhaustively, but there's a bunch of important stuff missing.
Clearly I'm biased by my personal history (and I haven't looked at a recent Sedgewick 'Algorithms In Trendy Language X', so maybe it's gone downhill). |
|
|
|
|
Well, I wanted to acquire a lot of information quickly in order to improve my skills for TopCoder, so I went on a book hunt, too. CLR is a great book, I have to agree, but it's exhaustive, which doesn't translate to quick, and your discrete math needs to be recent and handy for you, too, or you'll get bogged down during proofs. Understanding the proofs helps tremendously for CLR because the code in the book is pseudo-code and, as such, ain't gonna do you much good during a competition even if you were inclined to haul out that huge tome because you just happened to know where, oh, subsets were covered inside. Do CLR over a period of time, and your skills will skyrocket, but don't plan on catching up on a few pages between your bagel and OJ in the mornin'.
I have to second someone else's suggestion for the Sedgewick books. They come in C++ and Java flavors, and they get the gritty with a minimum of nitty. Sedgewick goes over some math, but keeps it down and stresses concepts. There are loads of exercises, too. I have the newer editions and an old, single-volued edition, too. Any would be fine.
Skiena's "Algorithm Design Manual" is a good intro, but the first half is an overview and the second half is a subject-by-subject discussion of the best resources for the given problem category. In short, it's a great supplement, but not a standalone.
Check out fellow TopCoder Stefan Pochmann's site (http://www.cs.ubc.ca/~pochmann/topcoder/) for a nice discussion on subset generation. He keeps promising more articles, and he does have a couple others, but mostly he's not too dedicated. But he's got a solution archive there, too, and that's handy.
Finally, the more problems you do, the better you get. I find my own progress has been directly tied to how busy I've been able to get with sample problems on TopCoder, USACO (http://ace.delos.com/usacogate/) or UVa (http://online-judge.uva.es).
As for your idea of concentrating on three languages, eh. I wouldn't. Get ridiculously good at one and you'll find your knowledge translates more fluidly, I think. Just my .02.
Peace. |
|
|
|
|
Here is the review of the book I posed in amazon.com if anyone interested in reading before getting the book
(http://www.amazon.com/exec/obidos/ASIN/0387001638/qid=1054943434/sr=2-1/ref=sr_2_1/104-7898141-4931113):
Good programming training manual but needs improvement
------------------------------------------------------
In general, this is a good training manual on programming competitions. The only other book for programming competitions I am awared of is "Problems in Programming: Experience through Practice", authored by Andrej Vitek, et al, and published by John Wiley & Sons, which I have not read. But the authors of this book tried to cover many topics without much depth. The topics should be treated more thoroughly, and more examples should be added. I hope the next revision of the book can be improved in these lacking areas.
Half of the books are a collection of problems you can get from the Programming Challenges website (http://www.programming-challenges.com). The lecture notes (in HTML and PDF formats), and audio (in MP3 formats), which the materials of the book extracted from, can be downloaded from the website.
For Java and C++ coders, some of the data structures and algorithms they provided are already available in classes and methods in the standard and STL libraries, respectively. But it is interesting to see how these data structures and algorithms are being designed and implemented in C from the book.
In my opinion, the code segments and examples chosen for the second half (chapters 8 and up) of the book are pretty good selections. The last two chapters of the book are my favorate chapters since the data structures and algorithms presented there for geometric problems, in particular computational geometric problems, are very subtle making solving some of these problems very simple.
I would like to add that other ways to improve programming skill are trying solving good programming problems yorself and learn from reading other good programmers' code. One of the best websites to do that is the TopCoder (http://www.topcoder.com) site. Every week they run single round match and every year they run both Collegiate and Invitational tournaments inviting members to solve programming problems. You are also able to practice problems from old matches and tournaments and read solutions submitted by other members at any time. |
|
|
|
