<p>Does anyone known of a a good reference for canonical CS problems?</p>

<p>I'm thinking of things like "the sorting problem", "the bin packing problem", "the travailing salesman problem" and what not.</p>

<p><strong>edit:</strong> websites preferred</p>

[{'answer_id': 35534, 'author': 'Kyle Cronin', 'author_id': 658, 'author_profile': 'https://Stackoverflow.com/users/658', 'pm_score': 2, 'selected': False, 'text': '<p>You can probably find the best in an algorithms textbook like <a href="https://rads.stackoverflow.com/amzn/click/com/0262032937" rel="nofollow noreferrer" rel="nofollow noreferrer">Introduction to Algorithms</a>. Though I\'ve never read that particular book, it\'s quite renowned for being thorough and would probably contain most of the problems you\'re likely to encounter.</p>\n'}, {'answer_id': 35536, 'author': 'rcreswick', 'author_id': 3446, 'author_profile': 'https://Stackoverflow.com/users/3446', 'pm_score': 2, 'selected': False, 'text': '<p><a href="http://portal.acm.org/citation.cfm?id=578533" rel="nofollow noreferrer">"Computers and Intractability: A guide to the theory of NP-Completeness"</a> by Garey and Johnson is a great reference for this sort of thing, although the "solved" problems (in P) are obviously not given much attention in the book.</p>\n\n<p>I\'m not aware of any good on-line resources, but Karp\'s seminal paper <a href="http://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems" rel="nofollow noreferrer">Reducibility among Combinatorial Problems (1972)</a> on reductions and complexity is probably the "canonical" reference for Hard Problems.</p>\n'}, {'answer_id': 35638, 'author': 'cpm', 'author_id': 3674, 'author_profile': 'https://Stackoverflow.com/users/3674', 'pm_score': 2, 'selected': False, 'text': '<p>Have you looked at Wikipedia\'s <a href="http://en.wikipedia.org/wiki/Category:Computational_problems" rel="nofollow noreferrer">Category:Computational problems</a> and <a href="http://en.wikipedia.org/wiki/Category:NP-complete_problems" rel="nofollow noreferrer">Category:NP Complete Problems</a> pages? It\'s probably not complete, but they look like good starting points. Wikipedia seems to do pretty well in CS topics.</p>\n'}, {'answer_id': 37456, 'author': 'BCS', 'author_id': 1343, 'author_profile': 'https://Stackoverflow.com/users/1343', 'pm_score': 0, 'selected': False, 'text': '<p>@rcreswick those sound like good references but fall a bit shy of what I\'m thinking of. (However, for all I know, it\'s the best there is)</p>\n\n<p>I\'m going to not mark anything as accepted in hopes people might find a better reference.</p>\n\n<p>Meanwhile, I\'m going to list a few problems here, fell free to add more</p>\n\n<p><strong>The sorting problem</strong> Find an order for a set that is monotonic in a given way</p>\n\n<p><strong>The bin packing problem</strong> partition a set into a minimum number of sets where each subset is "smaller" than some limit</p>\n\n<p><strong>The travailing salesman problem</strong> Find a Hamiltonian cycle in a weighted graph with the minimum total weight</p>\n'}, {'answer_id': 88670, 'author': 'Leandro', 'author_id': 13035, 'author_profile': 'https://Stackoverflow.com/users/13035', 'pm_score': 2, 'selected': False, 'text': '<p>I don\'t think you\'ll find the answers to all those problems in only one book. I\'ve never seen any decent, comprehensive website on algorithms, so I\'d recommend you to stick to the books. That said, you can always get some introductory material on canonical algorithm texts (there are always three I usually recommend: <a href="https://rads.stackoverflow.com/amzn/click/com/0262032937" rel="nofollow noreferrer" rel="nofollow noreferrer">CLRS</a>, <a href="https://rads.stackoverflow.com/amzn/click/com/0201120372" rel="nofollow noreferrer" rel="nofollow noreferrer">Manber</a>, <a href="https://rads.stackoverflow.com/amzn/click/com/0201000296" rel="nofollow noreferrer" rel="nofollow noreferrer">Aho, Hopcroft and Ullman</a> (this one is a bit out of date in some key topics, but it\'s so formal and well-written that it\'s a must-read). All of them contain important combinatorial problems that are, in some sense, canonical problems in computer science. After learning some fundamentals in graph theory you\'ll be able to move to Network Flows and Linear Programming. These comprise a set of techniques that will ultimately solve most problems you\'ll encounter (linear programming with the variables restricted to integer values is NP-hard). Network flows deals with problems defined on graphs (with weighted/capacitated edges) with very interesting applications in fields that seemingly have no relationship to graph theory whatsoever. THE textbook on this is <a href="https://rads.stackoverflow.com/amzn/click/com/013617549X" rel="nofollow noreferrer" rel="nofollow noreferrer">Ahuja, Magnanti and Orlin\'s</a>. Linear programming is some kind of superset of network flows, and deals with optimizing a linear function on variables subject to restrictions in the form of a linear system of equations. A book that emphasizes the relationship to network flows is <a href="https://rads.stackoverflow.com/amzn/click/com/0471485993" rel="nofollow noreferrer" rel="nofollow noreferrer">Bazaraa\'s</a>. Then you can move on to integer programming, a very valuable tool that presents many natural techniques for modelling problems like bin packing, task scheduling, the knapsack problem, and so on. A good reference would be <a href="https://rads.stackoverflow.com/amzn/click/com/0471283665" rel="nofollow noreferrer" rel="nofollow noreferrer">L. Wolsey\'s</a> book.</p>\n'}, {'answer_id': 476713, 'author': 'Jason S', 'author_id': 44330, 'author_profile': 'https://Stackoverflow.com/users/44330', 'pm_score': 2, 'selected': False, 'text': '<p>You <strong>definitely</strong> want to look at NIST\'s <a href="http://www.nist.gov/dads/" rel="nofollow noreferrer">Dictionary of Algorithms and Data Structures</a>. It\'s got the <a href="http://www.nist.gov/dads/HTML/travelingSalesman.html" rel="nofollow noreferrer">traveling salesman problem</a>, the <a href="http://www.nist.gov/dads/HTML/byzantine.html" rel="nofollow noreferrer">Byzantine generals problem</a>, the <a href="http://www.nist.gov/dads/HTML/diningphilos.html" rel="nofollow noreferrer">dining philosophers\' problem</a>, the <a href="http://www.nist.gov/dads/HTML/knapsackProblem.html" rel="nofollow noreferrer">knapsack problem</a> (= your "bin packing problem", I think), the <a href="http://www.nist.gov/dads/HTML/cuttingStock.html" rel="nofollow noreferrer">cutting stock problem</a>, the <a href="http://www.nist.gov/dads/HTML/eightqueens.html" rel="nofollow noreferrer">eight queens problem</a>, the <a href="http://www.nist.gov/dads/HTML/knightstour.html" rel="nofollow noreferrer">knight\'s tour problem</a>, the <a href="http://www.nist.gov/dads/HTML/busyBeaver.html" rel="nofollow noreferrer">busy beaver problem</a>, the <a href="http://www.nist.gov/dads/HTML/haltingProblem.html" rel="nofollow noreferrer">halting problem</a>, etc. etc. </p>\n\n<p>It doesn\'t have the <a href="http://en.wikipedia.org/wiki/Firing_squad_synchronization_problem" rel="nofollow noreferrer">firing squad synchronization problem</a> (I\'m surprised about that omission) or the <a href="http://mathworld.wolfram.com/JeepProblem.html" rel="nofollow noreferrer">Jeep problem</a> (more logistics than computer science).</p>\n\n<p>Interestingly enough there\'s a blog on <a href="http://www.codinghorror.com/blog/archives/000951.html" rel="nofollow noreferrer">codinghorror.com</a> which talks about some of these in puzzle form. (I can\'t remember whether I\'ve read Smullyan\'s book cited in the blog, but he is a good compiler of puzzles &amp; philosophical musings. Martin Gardner and Douglas Hofstadter and <a href="http://en.wikipedia.org/wiki/Henry_Dudeney" rel="nofollow noreferrer">H.E. Dudeney</a> are others.)</p>\n\n<p>Also maybe check out the <a href="http://www.cs.sunysb.edu/~algorith/" rel="nofollow noreferrer">Stony Brook Algorithm Repository</a>. </p>\n\n<p>(Or look up "combinatorial problems" on google, or search for "problem" in <a href="http://mathworld.wolfram.com/search/index.html?query=problem" rel="nofollow noreferrer">Wolfram Mathworld</a> or look at <a href="http://en.wikipedia.org/wiki/Hilbert%27s_problems" rel="nofollow noreferrer">Hilbert\'s problems</a>, but in all these links many of them are more pure-mathematics than computer science.)</p>\n'}]
['https://Stackoverflow.com/questions/35528', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/1343/']