HN Books @HNBooksMonth

The best books of Hacker News.

Hacker News Comments on
The Algorithm Design Manual

Steven S S. Skiena · 19 HN comments
HN Books has aggregated all Hacker News stories and comments that mention "The Algorithm Design Manual" by Steven S S. Skiena.
View on Amazon [↗]
HN Books may receive an affiliate commission when you make purchases on sites after clicking through links on this page.
Amazon Summary
This newly expanded and updated second edition of the best-selling classic continues to take the "mystery" out of designing algorithms, and analyzing their efficacy and efficiency. Expanding on the first edition, the book now serves as the primary textbook of choice for algorithm design courses while maintaining its status as the premier practical reference guide to algorithms for programmers, researchers, and students. The reader-friendly Algorithm Design Manual provides straightforward access to combinatorial algorithms technology, stressing design over analysis. The first part, Techniques, provides accessible instruction on methods for designing and analyzing computer algorithms. The second part, Resources, is intended for browsing and reference, and comprises the catalog of algorithmic resources, implementations and an extensive bibliography. NEW to the second edition: • Doubles the tutorial material and exercises over the first edition • Provides full online support for lecturers, and a completely updated and improved website component with lecture slides, audio and video • Contains a unique catalog identifying the 75 algorithmic problems that arise most often in practice, leading the reader down the right path to solve them • Includes several NEW"war stories" relating experiences from real-world applications • Provides up-to-date links leading to the very best algorithm implementations available in C, C++, and Java.
HN Books Rankings
  • Ranked #5 this year (2022) · view

Hacker News Stories and Comments

All the comments and stories posted to Hacker News that reference this book.
What are your goals? I don't mean to be snarky when I say that learning to ask a structured question (or being more disciplined about asking them) should be high on your priority list. Book like the pyramid principle about top down communication would probably be helpful.

1. It's probably fine. Based on your self-description, based on your self-description I imagine you're still struggling with syntax and program structure. Programming in either language will improve your abilities in that regard and let you focus more on the underlying ideas in your classes. That said, if you can stick to 1 or 2 languages for most of your CS classes that is preferable.

2. Data Structures and Algorithms is useful, how useful depends on your goals. If you want to make the big bucks you should aim to be fluent in at least a textbook's worth of material. If you don't feel the need to aim for the top, you can get away with less. I would start with Skienna:

If you really want to be a master, you can then go for CLRS:

3. This depends on your goals. If you're aiming to be a top engineer now's one of your few chances to really focus in on lower level system stuff: Operating Systems, Networking, Compilers, or Databases. If you want a decent job fast of college, focus on data structures and algorithms and start trying to deploy code on something like digital ocean. That said you probably also want to do:

General advice: Dive deep, understanding a few things really well is better than understanding many things shallowly (you will retain more info over time).

A mistake many people make when reading textbooks is to guess what words mean. In technical texts this usually leads to misunderstandings and ultimately a slower learning process. Take the time to understand the words even if it takes hours (imminent deadlines notwithstanding), you will go faster. (I once took a month to get through a single page of a textbook because it had so many new words and concepts).

Start using version control (preferably git). Try to at least every hour if you have new code.

Try to start writing well structured code now. You probably won't do a great job at first but by trying earlier you'll do better.

Related to above, start writing tests for your code. Code that is testable is usually better structured.

Source: Senior engineer at one of the bigger tech companies and a former educator.

@Hermitian909, thank you for sharing your insight. I deeply appreciate it.

Points taken: I'll continue working with both languages (which has the added benefit of seeing the similarities and differences between the two). I'll begin diving into the algorithms -- in fact, I grabbed _Grokking Algorithms_, which is an interesting read, but I'll certainly pick up _The Algorithm Design Manual_.

And your point about asking clear, structured questions is a great one, as is taking the time to really, actually understand what I'm reading.

Thank you again for your time.

Have you tried some of the old "Graphics Gems" series books yet? [1], [2], [3] They are not CS fundamentals but will help you out with the necessary concepts, math and algorithms for graphics programming and ray-tracing.

As others have mentioned any books on Data Structures & Algorithms are a must. [4], [5], [6]

However in my opinion, trying to understand CS fundamentals without undergoing some sort of formal education is a chore. You won't know what you are missing. Going through an established approved syllabus will give you a fuller understanding. But that is only if you are interested in the long haul.

There are a number of MOOCs that may fit the bill allowing you to slowly gather the knowledge without sacrificing too much time and focus on a day job to keep you going. I feel they are also great value for money for what you get. Some of them are from very reputable names if that is important. [7][8].

Since you have a B.Sc you can do the Masters level but there are also Bachelors level courses. [9]










I'm actually going to apply to the OMSCS as well, so hopefully I get in. It'll be part-time so I can work, but I'll definitely have less of a social/gaming life for the next few years if I'm pursuing an online masters lol

OMSCS Website:

A very good choice Karsteski, probably one of the best online CS programs out there. Wishing you the best in getting in.

I have embarked on another MOOC catering to a business degree and still figuring out how to balance course load with personal and professional life but I am loving it.

Learning a lot and the courses encourage group/team assignments working with students from all over the world. Learning to navigate the global team work model.

Good luck.

Maybe Clever Algorithms: Nature-Inspired Programming Recipes[1]. These techniques might not be useful to everybody, all the time, but they can be very handy in places.


A couple of other suggestions.

Managing Gigabytes: Compressing and Indexing Documents and Images[2]

Mining of Massive Datasets[3]

Algorithm Design Manual[4]

Network Algorithmics[5]

Neural Network Design[6]

I think all of these fall into the category of "Won't be applicable to everyone, but can be good for those who need this kind of stuff."







That looks good! Thanks!
The Algorithm Design Manual by Steven Skiena

Amazing book. Very readable. I highly recommend it. The book has a section call "War story" at the end of each chapter in which Skiena shares his real life experience of when the contents from that particular chapter came in handy for him.

Go through it. You won't regret

Note, there seems to be a 3rd Edition in 2020

> The Algorithm Design Manual by Steven Skiena

And his CSE 373 course lectures:

I bought the PDF last year for $7 (a very steep discount) during Apress/Springer's Black Friday sale. If you don't need the book right now or are on a budget, it may be worth waiting until next week in case they repeat the offer.
I came here precisely to suggest Skiena. Excellent book that gives you a good grounding in both theory and practice, and opens the road for further study, if you're so inclined.
Wow. I actually took one of his classes way back at Stony Brook. Great guy.
It's unfortunate that it costs 77$ :(

Edit: unfortunate for me ofc.

$30 used on ebay
cols had it for $11.50. As an aside, I really love that website. I am not too picky about the books I buy being in perfect condition, so it works out well for me. YMMV.
Not OP but I’m interested in this subject as well. I took a look at this book and others that are similar and I’ve realized my foundations on math are really lacking to even understand the given examples. Since I only had the opportunity to finish my high school diploma and this was several years ago I wonder if you could have any suggestion to brush my math knowledge up in order to properly understand the examples of these books. The thing for me is that I’m not sure where I should start. Would you know any resource to introduce me to the math foundations in order to understand such texts? Or maybe math concepts that I should study before I dig in. I really appreciate it. Thanks.
The best book if you have any programming background is 'Mathematical Modeling and Applied Calculus' by Joel Kilty and Alex M. McAllister reviewed here:

There's a small workshop for it here: throwing in some youtube tutorials. The book presents everything as functions and their parameters, like linear functions, trig, sigmoidal, e and logarithms, you learn all the parameters to these functions and can type into desmos online graph to see what they're doing visually. You don't have to do the whole thing just use it for background material when an algorithm text uses calculus methods like L'Hopital's rule.

Poh-Shen Loh has a discrete math course open on his youtube channel you can use the book he recommends to look up anything that is assumed knowledge in lectures. Discrete Mathematics, by L. Lovász, J. Pelikán, and K. Vesztergombi. A book called Asymptopia by Spencer is well done too, good chapters for learning everything you want about big-O/omega/theta some topics are advanced and some anyone can do.

>Since I only had the opportunity to finish my high school diploma and this was several years ago I wonder if you could have any suggestion to brush my math knowledge up in order to properly understand the examples of these books.

You should really consider taking a few community college math courses if you're serious. Math is extremely difficult to learn on your own. Not only because of not knowing what you don't know, but because it requires intense effort and repetition which is very hard to force yourself to do. You can work through the concepts and delude yourself into thinking you understand something when really you're just hand waving it. Taking an actual course and being faced with the gaps of your knowledge by someone else is very humbling and essential to actually learning it.

> You can work through the concepts and delude yourself into thinking you understand something when really you're just hand waving it

I keep seeing this and I don't quite understand how this one works.

If I were studying math on my own (which I've done and still do), I'd do the following:

1. Pick a book. Say, Rudin's Principles of Mathematical Analysis[0]. Read a section, then attempt problems. Pick a problem. Say, "prove {1/n: n is natural} U{0} is compact directly from the definition(not using Heine-Borel)". It's guaranteed your "proof" is not a proof.

2. Compare your solution to existing solution manuals or ask a question on MSE[1]. Since the given book by Rudin is super-massively famous, each question has probably been asked/answered about a bagillion times each on MSE, so just searching MSE alone would likely to spit out many answers to your questions. People on MSE will tell you exactly why your "solution" is wrong and where you tripped up. Sometimes even the clarifying answers are hard to understand. But then you can ask new questions, think more, correct your misconceptions until it all finally clicks. Do that with all the rest of the problems[2].

I don't see how the process above is delusional.

[0] This book is not a realistic fit for a novice, though. Instead, one would start with books like [3], [4], [5], [6] to learn how to prove things and think like a mathematician would.


[2] In reality, the more math you see and do, the more mathematically mature and less dependent on others(to check your work) you become. In fact, if you can solve any problem in "[email protected] Rudin" and some famous abstract algebra textbook (say, Dummit & Foote's "Abstract Algebra") cold, you're way ahead of most any undergrad math major in the world! Because standards on undergrad math majors are not that high, nor that brutal the world over no matter what they say. If, additionally, you can solve any given problem in a book like, say, Hatcher's "Algebraic Topology" or any other famous grad level textbooks on, say, differential geometry or, uhh, functional analysis, you're officially in the big leagues. Again, if you're worried about being delusional about your proofs, you can always present them on MSE.

[3] "Book of Proof" by Richard Hammach. It's online free.

[4] "Discrete Math" by Susanna Epp

[5] "How to Think About Analysis" by Lara Alcock

[6] "Linear Algebra" by Kuldeep Singh

Step 1.5: Decide you're not making progress on the problem, look up the answer on MSE, say, "OK, I get that" and go on.

Alternate: Ask a question, get a not-quite-right answer, and find yourself completely stuck two chapters further in with no way of figuring out where you went wrong.

> I keep seeing this and I don't quite understand how this one works. > I don't see how the process above is delusional.

Because those that are just starting to learn math don't take your approach to learning.

I had a lot of bad habits that I had to break when I was learning math that really caused me to do poorly in many classes. If you are coming at it from a more qualitative field, then it's very easy to read the book and come away with nothing from it.

I'm taking a discrete math course and I was trying to offer up some advice on the school's subreddit to someone struggling in the class. They mentioned something about me taking the easier prof, so that's why I'm doing well. I said that I had fully worked at least 50 problems in each chapter we covered and asked how many they had done. The response was I went to lecture, read the notes once, and attempted the homework exercises; I didn't know you had to do some much work in this class.

That of course assumes the community college is serious about its mission to educate. Most of the students just want to pass because the math course is required for this or that vocational program, and in this age it's wiser to humour the students and wave them through.
Concrete Mathematics by Graham/Knuth/Patashnik is still a great resource on the kind of mathematics and mathematical thinking we need in CS, but I'm not sure if it is fully accessible with a high-school level of Maths.

To be perfectly honest, I doubt I would've ever gotten through college-level maths without being forced to do it, as it can be very frustrating and difficult in the beginning. Unless you are quite confident in your self-discipline and enthusiasm to learn maths, rather than books I'd recommend something interactive (online course, forums, challenges).

If you are interested in a starting point to learn mathematics that are relevant for CS, I'd start with propositional logic and boolean algebra, as well as proofs via induction.

Art of Computer programming starts at a high school level.

It's very rigorous and considered one of the more difficult reads. But if you start at chapter 1 page 1, it covers all the math you'll ever need for the rest of the books (which is sufficient maths to reach masters or even PH.d level comp sci)

I know I've recommended it to high schoolers. A lot of math is just getting used to the nomenclature and vocabulary. The sooner you get used to rigor the better

AoCP is an absurdly inefficient way to learn algorithms that 99.999% of people won’t need
Most algorithm books don't cover the math like summations or generating functions.

Chapter one of TAOCP for better or worse, is a very rigorous mathematics introduction.

I'm not recommending it for it's algorithms (which are unfortunately somewhat out of date). I'm recommending it because it's an incredible mathematics introduction, albeit a very difficult one.

Can you elaborate on "out of date"? I've seen a lot of books considered out of date because of their publishing date, but to what's exactly being compared to be considered so?
The obvious example for me is the chapter on tape merging
Modern "RAM" is far faster at sequential than it is at random access.

So tape merging is in fact, useful again strangely enough. That's one of the sections that suddenly and surprisingly has regained relevance.

Well, Volume 4 was released in 2016 and is not out of date at all. Its a very good read, but on an obscure subject.

But Volume 1 has lots of out-of-date advice and is somewhat of a shame, because its otherwise an excellent introduction to computing + the mathematics needed to understand computing. For example, the assembly language is based on the 1960s computers, such as decimal computing and 6-bit numbers (based on the days of old, before 8-bits were standardized).

Functions are introduced by self-modifying code first and foremost: by rewriting "jump" instructions at the end of functions as a return. No one does this anymore: pretty much all compilers do the stack-thing instead. (Push return address onto a stack register).

The Fascicle on MMIX updates a lot of those sections to a modern-like 64-bit assembly language. However, the sections on cofunctions, arrays, garbage collection aren't part of that update... and should be updated (Knuth's discussion on these concepts is great, but are told in an "old way" based on 1960s tech)

Volume2: Seminumerical Algorithms (chapter 3 / 4) is again, a decent introduction to the subject. But the RNG stuff is fully obsolete. The statistical tests may have passed muster in the 1970s or 1980s, but today's statistical tests (aka: PractRand) go above and beyond what Knuth discusses.

There's a lot of interesting discussions in the randomness chapters: such as the efficacy of multiplication when it comes to bit-mixing (and I feel like modern RNGs are sleeping on that tidbit), but modern RNGs are generally based on a simpler sequence of ADD / XOR / SHIFT instructions based around the concept of permutations / perfect bijections.


Ironically, I consider the section on "tape sorting" to be "suddenly up-to-date" again. Modern RAM acts more like a tape (sequential is far faster than random), meaning that thinking of sorting problems in terms of external-sort is surprisingly relevant.

Given that today's cache is 768MB (see AMD's Milan-X CPUs: expected to be a ~$5000 CPU-server chip), we see that L3 cache basically serves as the RAM from Knuth's time, while today's DDR4 RAM really acts as the fast-sequential / slow-random layer that Knuth studied so much.

TAOCP is probably the best book if you approach it as infotainment/puzzles casual reading on the weekend reading about the history of trees and their mathematical properties kind of reading not anxiety filled interview passing cramming. Even autodiff online algorithms is in there something heavily used right now.
I've bought them and looked through it but if someone asks how they should go about learning algorithms for leetcode there are so many better options thank Knuth. That is years of effort to get through.
This is a good starting point:
I had exactly the same issue with this book. It brought back memories of seeing teachers solve problems on the board and skipping some obvious (to the teacher at least) step.

This prompted me to check out khan academy. Man, that is an incredible resource. I really envy the schoolchildren of today that have instant access to this incredibly smart tutor, who can be rewinded at the touch of a button.

Check out the course 6.042J from MIT (Mathematics for Computer Science).

I'm not sure if this is universally true or not, but the algorithms courses at the universities I'm familiar with require a course in discrete math as a prerequisite.

You can find Discrete and Combinatorial Mathematics (an Applied Introduction), 5th Edition, Ralph P. Grimaldi online and an answer key can be found online as well. (This book covers two discrete math courses. Chapters 1-5, 7, 8, 12 is a first course in discrete math. I'm not sure what chapters the second course covers, but that requires linear algebra as a prerequisite.)

It's not perfect, but it's a start. I think you need to be familiar with some high school algebra, exponents, and logarithms. You can find some review information in the appendix. If you have troubles with recalling that information, then you can try Khan academy. (It really is an if you don't use it, you lose it situation with much of math.)

You're probably aware of this already, but most people don't read the book and come away with the knowledge required to solve the problems. You'll need to work through the examples in the chapter, be able to recall the definitions and theorems, and then work the exercises at the back of the book.

I think the discussion of proof methods is pretty poor in the book. You can find many intro to proof method type supplemental notes online to help fill in the details.

There really is so much information out there that you can pretty much always find an alternative explanation or viewpoint for undergrad level material. Many profs will post their own lecture notes, homework, and solutions. There are some math forums that have explanations. So find a book you're reasonably comfortable with and supplement it with extra material.

Skiena's Algorithm Design Manual:

Far more readable than the usual text (Cormen), the first half is a guide on how to select and design algorithms for the problems you encounter, and the second half is a whistle-stop tour of hundreds of well-known algorithms. The tour helped me a lot with X->Y esque issues where I was building bad solutions because I didn't know anything better could exist.

Incidentally, there's a lot more to CS theory than algorithms and data structures, but if you're asking on HN for a generic CS theory book, I reckon it's most likely an algorithms and data structures book that you're after.

I'm going to disagree slightly with your choice (which was also my choice at first). While A.D.M. has all the topics you would be interested in, I think the book assumes that you have already groked the fundamentals behind, say, why a linked list is different from an array. For an absolute beginner, I would suggest the type of book that forces you to go through every step of deleting an item from a list, which is something Skiena's book (luckily) doesn't do. The book is great for learning new ways to think about problems, but IMHO a beginner should learn the basic ways first.

"Introduction to Algorithms" by CLRS seems to be the default choice, and it seems to me to be a step in the right direction (based on the TOC).

I would also like to second your point that CS is more than algorithms and data structures. I feel Dijkstra would not approve of thinking about CS as "that thing you do after learning a programming language".

This is really helpful, thanks. It's been... a few years since I read Skiena, and I came to it from a maths background. I'll add the disclaimer in future that Cormen's easier to start with.
I found "Introduction to Algorithms" to be _waaay_ too dry to deal with in beginning, though I'd welcome something else to get through the detail.

Personally I'd use Cormen as "dictionary" to get into detail of stuff I first read in A.D.M.

I bought it and it was a counterfeit book. Pretty sure if you buy it there you will get either a counterfeit book or an international edition which has significantly lower print quality.

If it were me, I'd probably consult Cracking The Coding Interview[1], and the Robert Sedgewick Algorithms in C++ [2][3] books. That and maybe spend some time practicing on Leetcode, Hacker Rank, Project Euler, etc. Skiena's Algorithm Design Manual[4] could also be good.





Isn't this book too academical for any practical learning of algorithms and data structures?

I would recommend The algorithm design manual for more practical purposes.

His lectures from 2016 are also on YouTube:
> Isn't this book too academical for any practical learning of algorithms and data structures?

I don't think so, I've worked through it and I didn't find it that difficult/academic. But I actually don't read a lot of computer science books / textbooks so I don't really have much to compare it to other than mathematical texts which I do read a lot of.

If you don't like proofs or math then its probably not the best text to work through, on the other hand, if you like rigorously understanding the material I would highly recommend it.

Either way, from what I remember it gives psuedocode for just about everything and has lots of graphs and pictures for elucidating the material, so you could probably just skip the math if you have an allergy to corrolaries, theorems, and proofs. Admittedly, that extra insight is probably a lot of the reason I liked it so much.

10 years ago being 2008 - and the second edition also appears to be the most recent edition too; age of the edition though appears to have no impact on its value.

SOURCE: The Algorithm Design Manual 2nd ed. 2008 Edition

I can't recommend courses, because I don't have direct experience of any, but given what you say, my suggestion would be to take a bit of a pause from pragmatic problems, and dedicate some time to learn the foundations of computer science, in particular about algorithms and data structures. I'd recommend a couple of books: "The Algorithm Design Manual" by Steven Skiena if you want something not too theoretical, or "Introduction to Algorithms" by Cormen, Leiserson, Rivest, if you want a bit more breadth and theory:

As a second suggestion, I'd recommend to learn a language somewhat different from JavaScript-like (or C-like) languages, something that challenges your mind to think a little differently and understand and create higher order abstractions. There are many choices, but to avoid confusion and being my favourite, I'll point to one: read the "Structure and Interpretation of Computer Programs" by Abelson and Sussman. It teaches Scheme in a gentle and inspiring way but at the same time it teaches how to become a better programmer:

Or if you want made of dead trees:

I can't recommend it enough. If you read it, do the exercises, don't limit to read through them.

Maybe it's even better if you start with this, and THEN read the books on algorithms and data structures.

Enjoy your journey!

SICP has continually showed up on my radar and before this post it's what I was looking at getting into again but felt this the book might have been too "meaty" and maybe was out of vogue. I think I just need to delve into it and finish it. Awhile back I did the first couple chapters and it did seem to go quite well though it's not for the faint of heart and really requires hard focus and I'm okay with that! My hesitation was that I wasn't sure if it was a solid starting point. Looks like it might be!
It could have a bit of a "serious air", but don't let this intimidate you, it's not that academic. Also you don't need to read it all to grasp the most prominent benefits. Chapter 2 and 3 have a lot of juice (I remember in particular the part on generic operations and the symbolic algebra example in ch. 2 and the streams in ch. 3). If you decide to read it all, in the end you'll learn how to write an interpreter for the scheme language, and this will ingrain a very deep understanding on how an interpreter (and even a compiler to a degree) works. But as I said, write the code yourself while you read the book. It will be easier to follow and much more fun!
Skiena's Algorithm Design Manual is really great, it's pretty comprehensive.

Here's an often overlooked technique for older, self-taught engineers like me: study. Go get this book, The Algorithm Design Manual by Skienna. Also pick up a whiteboard, and a nice set of dry-erase markers.

Read the book, and do whatever exercises you can from the book on the whiteboard. Talk out loud, the way you will in the interviews. After a few weeks and 60 hours of doing this, you'll be ready to blow the minds of the people interviewing you.

When you go to your interview, you will bring your own markers. Then you don't have to deal with the fat, half dried out stuff you encounter during the interview. Also, warm up for an hour or two before you go to the interview, by doing problems from the book on the whiteboard, out loud. This helps you leave nothing to chance, and be ready for whatever they throw at you.

Yeah, it's a waste of time. But you have to play the game. Similarly, when they ask you why you left your last job, lie and tell them you'd accomplished all your goals there, got everything lined up and nailed down, and you're ready to make something happen somewhere else. Don't tell the truth if it's because your managers couldn't care less about doing what's best for the business. If you want to work at the circus, sometimes you gotta jump through some hoops. Big deal, you'll be ok!

Yes, the interview process is broken, but you can actually work at it and do well, even if you're old.

Buy this book even if you're not planning to take my advice and study. Even if you don't study, this should become one of your most treasured books. I myself was amazed at how many things turn out to be graph problems, and had a great time going through this book.


As an older self-taught engineer who went through interviews last year this is great advice. Other books I found particularly useful were:

Algorithms by Dasgupta, Papadimitriou and Vazirani:

And Elements of Programming Interviews by Aziz, Lee and Prakash:

Implement algos in a new language. Last time I went thru CLR using Haskell. I might do Go or Rust this time and contribute some algos to the community.
That's interesting. Did you use mutability, in ST or IO for example, to implement the algorithms?
> Here's an often overlooked technique for [...] engineers like me: study.

This is fantastic advice, for everyone.

Preparing for interviews isn't wasted time, because ultimately the goal is to land a job that furthers your own personal goals in some fashion.

I wouldn't recommend lying. If you're leaving a job, you should stand by your convictions. In my market, it's small and everyone knows everyone, so claiming you nailed everything down is easy enough to verify. Just remember one simple truth: "You are the only common link between all your failed jobs."

The difference between "I nailed it all down" and "everybody between myself and the CEO was an idiot" may simply be a matter of perspective. Let's say both are true. Focus on the former, rather than the latter, in interviews. Be positive. Maybe that's a better way to phrase it, rather than saying "Lie." Heaven's no, never lie during a job interview; that simply won't do at all!
The best lies are the lies that can't be in principle disproven. I try to be reasonably honest most of the time, but if the question is something like "why did you leave" I'm going to give the "right" answer, not the honest one.
> I'm going to give the "right" answer, not the honest one.

Curious what the "right" answer is?

Lawyers never lie. that would be unethical.

Instead, lawyers "speak colorably"; If one takes the pure white light of truth, and puts it through a prism, all of those colors in the spectrum of truth, while not 100% of the truth, still contain a very strong thread of it.

for example, I was in court recently settling a criminal charge for someone about two months ago, and that someone asked the crown prosecutor (during the hearing) why the crown has gone silent on the civil process settling the charges. The crown, unable to lie, or even acknowledge a commercial default, stated colorably that the paperwork was "not necessarily valid" in a criminal case. not only was this true, but this kept the prosecution in honor, the court in honor, and the defendant in honor, all while allowing him his "Section 11" remedy (canada criminal code).

I'd suggest using colorable language any time you feel the need to lie.

TL:DR - In the eyes of the law, telling a spectrum of truth is still considered telling the truth.

So what I told you was true... from a certain point of view.
Same here, I came in to post about that exact book.

There's also Pearls of Functional Algorithm Design which I have yet to read.

In general you've got stuff like Introduction to Algorithms ( and the Algorithm Design Manual ( both of which I have seen mentioned as good books. I'm in a grad school-level algorithms class that just started using the former (which is language agnostic, but we are doing our implementations in Java) and it looks pretty good to me.

Pathfinding is a much easier problem than circuit routing and can essentially be solved in O(n + k) where n is the number of nodes and k is the number of edges between nodes.

Circuit routing is an entirely different beast. A previously routed "shortest" trace from one node to another can obstruct a much shorter trace between two unrelated nodes. In this way it's similar to the traveling salesman problem, where early "greedy" choices made by the salesman can force him to make much less efficient choices later.

I remember circuit routing was an example in Skeina's Algorithm Design Manual [1], and believe he proved that it was indeed NP-complete, not polynomial like the general pathfinding problem.


> Pathfinding is a much easier problem than circuit routing and can essentially be solved in O(n + k) where n is the number of nodes and k is the number of edges between nodes.

What you are describing is the complexity for a single path. But there are lots of units that need to be placed and have their paths potentially interact to achieve some goal. This seems very analogous to circuit routing.

Fair enough, once you start needing to path many units at a time (where their movements can potentially conflict with each other), then it starts to sound a lot more like circuit routing.
Maybe but it's more traffic - ten units can find Independant paths to a goal. If paths intersect on a pcb you must reroute. If the units paths intersect t one waits till other moves then continues.

Maybe it's too simplistic but in the vein of the outrageous hack I like it.

I think that's basically what SC1/BW did. There was a professional game last year[1] where one player (Jaedong, probably the best Zerg at the end of BW) had one unit blocking a ramp in his base, and something like 30 hydralisks stacked up behind it. He was attacking the enemy so he didn't notice at first and I think he probably lost his main army but then found a huge second army that had been stuck and just rolled the poor guy.


"Pathfinding is a much easier problem than circuit routing"

I'm not sure I agree with that, the mechwarrior talk was pretty informative and the variability of terrain and dynamic obstacles made for some interesting challenges. It was particularly interesting when they talked about 'squad walking.' (going into a line in tight spaces etc) When I was thinking about writing my own RTS I did some simple experiments and certainly got a feel for it being quite complicated.

I was confused by your original comment. You're absolutely right though; trying to path a squad of multiple units so that their routes don't conflict is much harder. I can see how it could be very similar to circuit routing.

Heck, it probably has the same basic time complexity and is amenable to the same algorithmic solutions.

For anyone interested in this subject I'd highly recommend the Algorithm Design Manual by Steven Skiena[0]. He goes over this in pretty good detail in the first ~1/4 of the book. This was my first introduction to Algorithm Complexity Analysis and by the end of that section I already found myself looking at my code in a different light.


I would recommend the Introduction to Algorithms by Cormen. It covers not only the complexity analysis but also describes the most important algorithms, data structures and classical problems solutions.
For anyone trying to buy "The Algorithm Design Manual" (or at least add it to their Amazon wish-list with a dreamy sigh), It seems like the "correct" version is here:

I was a bit flummoxed at first because doesn't tell you how to buy the thing, and the Kindle edition appears to be out of date (based on the first edition, obsoleted by the second edition from 2010).

Sorry about that.

I should have linked to the Amazon page in the first place (who am I kidding?). You linked to the correct version.

I have just started reading the bible of algorithms:

Not a quick win but a comprehensive, in-depth algorithm book :-)

I've heard good things about that book, but to be fair The Bible Of Algorithms can only be Knuth's TAoCP.
The bible is definitely TAoCP, but its a little long to read before an interview, maybe select sections.
If you're interested in glossaries of this type, there's a great one (with pictures!) in the back of The Algorithm Design Manual by Steven Skiena.

HN Books is an independent project and is not operated by Y Combinator or
~ [email protected]
;laksdfhjdhksalkfj more things ~ Privacy Policy ~
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.