Algorithm design

What Hacker News says

1. quibonoJan 2023
   Computer Science is very broad so the answer will be different depending on what you'd like to focus on. Algorithms, data structures, systems, graphics, networking, more theoretical CS etc.

   That said, for algorithms I could recommend CLRS, Dasgupta's Algorithms, Kleinberg's Algorithm Design. For theoretical CS: Models Of Computation by J. Savage, Sipser's Introduction to the Theory of Computation. For OS: Computer Systems A Programmer's Perspective by Bryant and O'Hallaron, Operating Systems - Three Easy Pieces by Arpaci-Dusseau.

   Show morethread
2. pm90Jul 2022
   For the general case, the CLRS book is recommended, but I personally found Algorithm Design by Jon Kleinberg and Eva Tardos to be the best introduction in undergrad: https://www.amazon.com/Algorithm-Design-Jon-Kleinberg/dp/032...
   thread
3. dragontamerJan 2022
   The satisfaction problem is considered the "ultimate" problem to reduce into. Because SAT is very flexible in representation, is NP complete (and therefore a huge variety of problems map to it), and sometimes is efficient.

   You can't solve NP-complete problems efficiently, but SAT (and 3SAT) is basically the best attempt at that complexity class.

   -----------

   The constraint satisfaction problem is another one that is sometimes used.

   For example, Sudoku, Traveling Salesman, coloring problems and more all reduce into the 3SAT problem. However, a dedicated traveling-salesman solver will be faster than pretty much any general purpose 3SAT solver, but its still easier to use another person's solver than writing your own.

   ---------

   An intriguing "simpler" problem is the maximum-flow problem, which is surprisingly flexible and usable in many many algorithms. Its not as widely applicable as 3SAT is, but maximum-flow is "efficient" to solve (in P-time and P-space).

   ---------

   A good book into this (including these "cannonical" problems, like maximum flow or 3SAT) is "Algorithm Design" by Jon Kleinberg and Eva Tardos. This only covers the basics of course. 3SAT and constraint satisfaction are their own respective fields with basically their own branches of mathematics.

   A lot of Graph algorithms are also worth knowing. It seems like many, many problems map into graph algorithms (max-clique, topological sort, minimum spanning tree, etc. etc.)

   > A general solution for a "compiler" that can translate between any pair of problems feels unrealistic but I can imagine developing a mapping between, say, a tic tac toe game and simple chess positions where you could: (1) translate a tic tac toe position into a chess position (2) solve the chess position (3) translate the solution into a tic tac toe sequence

   Yup, that's a 3SAT solver for ya. It will solve the problem, eventually, but 3SAT is NP complete, so the heat-death of the universe may come about before the answer comes out.

   If you know your problem is less complex than NP-complete, you'll want to map it to some other problem that's got less complexity (so that the algorithm finishes faster).

   Show morethread
4. nayukiDec 2021
   "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.

   "Algorithm Design" by Jon Kleinberg, Éva Tardos.

   "Introduction to the Theory of Computation" by Michael Sipser.

   "Course notes for CSC B36/236/240: Introduction to the Theory of Computation" by Vassos Hadzilacos. http://www.cs.toronto.edu/~vassos/b36-notes/notes.pdf

   thread
5. dragontamerAug 2020
   "Algorithm Design" by Kleinberg & Tardos is pretty good. Chapter 6 is its Dynamic Programming chapter, and there are 9 examples in the chapter with pseudocode and analysis.

   Some of its dynamic programming examples: Weighted Interval Scheduling, Segmented Least Squares, Subset Sums / Knapsacks, RNA Secondary Structure, Sequence Alignment (aka: Diff), Shortest Path in Graphs.

   All in just a ~50 page chapter.

   The other chapters on Network Flow, Greedy Algorithms are also excellent.

   "Algorithm Design" is an advanced text, but that's how it covers more material than easier textbooks since it won't waste your time on the beginner level stuff.

   -------------

   Honestly, given the beginner-nature of the textbook here, I think they're doing a decent job. Dynamic programming isn't as fundamental as the stack / queue / sorting / searching etc. etc. that's being discussed in "Problem Solving with Algorithms and Data Structures".

   Dynamic programming is definitely something that should be reserved for more advanced textbooks (with maybe, at best, an introduction to the subject at this level).

   Show morethread
6. bjourneOct 2019
   Algorithm Design by Kleinberg and Tardos. It is a wonderful book especially because of the well-designed problem sets. Most of them come with answers too.
   thread