6 ms·

On my off hours, I’ve been working through volumes 4A and 4B. They are really wonderful, I highly recommend them. They’re not practical for the vast majority of

• pcranaway 2y ago
  given that they are not very partical, how do you make sure to retain what you read? do you take notes? (asking as someone who only recently started reading cs-related literature)
  • pastage 2y ago
    I feel that there is no good answer to this. For me It is more about the parts of the solution than the big problems. Some of the big solutions stay but it is mostly how you fit things together that stays with me. Everyone works differently here, e.g. I tend to reuse lots of things other people reimplement them there are drawbacks with both types of learning. I read a lot of code.
  • OskarS 2y ago
    Implementing an algorithm like Dancing Links is a hugely rewarding experience as a programmer. You learn by doing.
• fjfaase 2y ago
  I have made an implementation of the original Dancing Links algorithm, but for some large problem, more than a million rows and 104 columns with an average of about sixteen positions per row, it is killed because it takes too much memory. I wonder if the updated algorithm is using less memory. My guess is that this large problem has about a hundred million solutions. So, even if it finds a hundred solutions per second, it still would require about ten days to finish. The problem, I am working on, is the number of solutions to the 'Fancy Tetris Houten Puzzel' where all pieces of the same color touch are connected by at least one side touching another side of a piece with the same color. I have been thinking about other algorithms for solving this Exact Cover problem that are less memory sensitive.
  • mafuy 2y ago
    From a rough estimation, it should not run out of memory with these constraints. The matrix should be about 1m rows * 16 cells/row * (4 pointers/cell + overhead?) * 8 bytes/pointer = approx 1 GB. That's quite little. The dynamic memory is negligible with 104 cols, avg search depth should only be around 104/16.
  • OskarS 2y ago
    It does improve memory usage! In the version in the paper, each item has four links, in the book version they only have two. So memory usage is roughly cut in half.
• mafuy 2y ago
  How did Dancing Links change from the paper? When I implemented it I could not see anything that could possibly be changed, so any improvement would be surprising and wonderful to me.
  • OskarS 2y ago
    You know in the sparse matrix, every item has four links (left, right, up and down)? In the version in the book, each item only has two links, up and down. The left/right links become implicit, because he stores the items contiguously in an array (so right of item 14 is item 15), and inserts "spacers" so you know when a row ends and the next one begins. This doesn't algorithmically improve the runtime, but it uses half the memory and gives it much better cache behaviour (btw: this is sometimes a charge levied at Knuth, he only cares about algorithms and not practical runtime when it comes to things like cache coherency. This is ludicrous, as this example shows.) That's the change to the "basic" algorithm, but he then goes on to add a bunch of new features to basic Dancing Links, modifying it so that it's suitable for different kinds of constraint solving (adding required rows, things like that). If you've implemented Dancing Links in the past, you owe it to yourself to check out the book version! He also has hundreds of really great exercises about it.
    • taeric 2y ago
      In addition, I'd also recommend looking at his implementations, directly. https://www-cs-faculty.stanford.edu/~knuth/programs/dlx6.w https://www-cs-faculty.stanford.edu/~knuth/programs/dlx6.w, for example.
• bandana 2y ago
  I was not aware of an update to this algorithm, I'll have to look it out. The original dancing link is one of my favorite papers, you can really see Knuth's love for algorithms (it's not in every paper you see sentences like "This process causes the pointer variables inside the global data structure to execute an exquisitely choreographed dance"). I'm using it to generate crosswords (the horizontal and vertical words forming an exact cover of the grid).
  • mangodrunk 2y ago
    Is this the paper? https://arxiv.org/abs/cs/0011047 https://arxiv.org/abs/cs/0011047
    • bandana 2y ago
      Yes that's the one ! I found it when I was trying to solve the tetraminos in The Talos Principle without looking for a game guide... I agree with OskarS it is a rewarding algorithm to implement.
  • OskarS 2y ago
    I cannot recommend checking out Volume 4B enough, then. He goes much deeper, improves the algorithm, adapts it to different constraint problems, and provides hundreds of really cool exercises (including word problems like crosswords, I think). It's the best.
• billfruit 2y ago
  Does it still use the Mix computer and assembler? Does these make the material clearer or more hard to understand at this point of time?
  • anticensor 2y ago
    He now uses MMIX, a modified version of MIX with RISC characteristics.
    • deleted 2y ago
      [deleted]
  • taeric 2y ago
    I the core book, he typically sticks to pseudocode. And with the later sections, most of the implementations he does to check ideas are with cweb. In that vein, I highly recommend reading some of his programs directly. You can find them here: https://www-cs-faculty.stanford.edu/~knuth/programs.html https://www-cs-faculty.stanford.edu/~knuth/programs.html Expect code that will challenge some ideas on premature optimization. He codes much closer to the numbers than many are used to.
• colmmacc 2y ago
  Back in 2010 when we were building Amazon Route 53, we had a really big problem to solve. DDOS attacks. DNS is critical, and it uses UDP, which is a protocol that allows attackers to spoof their source IP address. We knew that DNS services are a common target for attacks from botnets; and our research at the time showed that our established competitors used large and expensive "packet scrubbers" to handle this. We budgeted out what we think it would cost to handle our scale and the price tag came to tens of millions of dollars. You might think that would be no problem for a big company like Amazon, but our total infrastructure budget for Route 53 was something like tens of thousands of dollars. At the edge, we were re-using CloudFront servers that had failed hard drives for our name servers; since we wouldn't need much storage, and our API servers were pretty modest. We had a team of about ~6 people. That's what "scrappy" looks like at AWS; spend nothing, minimize downside risk, get things done quickly. There was no way I was going to ask for tens of millions of dollars for packet scrubbers. Besides, they would take too long to arrive, and would make us too reliant on a vendor. Early on we had decided to run Route 53 name servers on its own dedicated IP range to give some measure of isolation. We could use dedicated network links to make sure that Amazon's other infrastructure wouldn't be impacted. But that wouldn't help Route 53's customers from sharing fate with each other. We didn't have a real plan beyond "When it happens, get really good filtering using our existing network and system tools". Early that summer, I was reading one of Knuth's recent fascicles for 4A and was swimming in combinatorial algorithms. One night it just "clicked" that by creating many virtual name servers, we could easily assign every customer to a unique combination of four of those virtual name servers. We could even control the amount of overlap; some quick math showed that we about two thousand name servers, we could guarantee that no two customer would share more than two name servers. That number is important because our experiments showed that domains resolve just fine even when two name servers are unreachable, but beyond that it starts to be a problem. The recursive search algorithm to assign the IPs was inspired directly by the algorithms in 4A; it gives customer domains two more independent dimensions of isolation. They also get 4 name servers from 4 independent "stripes", which correspond to the different TLDs we use for the name server names (co.uk, com, net, org). This guarantees that if one of those TLDs has an issue (like a DNSSEC mistake), only one of the name servers is impacted. They also come from 4 independent "braids", which can be used to ensure that no two name servers share certain network paths or physical hardware. I just wouldn't have known how to do any of this without reading 4A. And I even have a background in combinatorials; from statistics and cryptography. I've never been more excited by a solution; this approach gave us provable network IP level isolation between customer domains while costing basically nothing in real infrastructure. It's math. It wasn't completely free; we had to use 2,000 anycast IP addresses, and it turns out that we also had to register 512 domains for them because of how many TLDs require name servers to be registered and to have glue records; so that was a fun process working with our registrar. But we got it done. I named the approach "Shuffle Sharding", and it's more discovery than invention. Many multi-tenant systems that use some kind of random placement get a kind of shuffle sharding, and network filtering techniques like Stochastic Fair Blue use time-seeded hashing to similar effect. But I've never seen anything quite the same, or with the level of control that we could apply; I could even extend it to a kind of recursive nested shuffle shading that isolates at even more levels. For example if you want to isolate not just a caller, but a caller's callers when they are in some kind of "on behalf of" call pattern. Years later, I made a personal pilgrimage of gratitude to see a Knuth Christmas lecture in person, and sat in the front row. I still read every scrap of material that Knuth puts out (including the Organ pieces!) because I never know what it might inspire. All of this to say ... I do think his volumes are surprisingly practical for programmers; they broaden your mind as well as deepen your understanding. What more could you want.