[HN Gopher] Donald Knuth's 2024 Christmas Lecture: Strong and We...
___________________________________________________________________
Donald Knuth's 2024 Christmas Lecture: Strong and Weak Components
[video]
Author : esbudylin
Score : 348 points
Date : 2025-02-07 07:11 UTC (15 hours ago)
(HTM) web link (www.youtube.com)
(TXT) w3m dump (www.youtube.com)
| illegalmemory wrote:
| Thank you for sharing! It might be a bit off-topic, but videos
| like this remind me why I fell in love with computers in the
| first place. Thank you!!
| gjvc wrote:
| The whole "let me put TAOCP on pause while I create TeX just to
| create it properly" story always fills me with awe.
| monobot12 wrote:
| My takeaway is it's much easier to embark on huge side
| projects as a tenured professor.
| WillAdams wrote:
| Agreed.
|
| I'm also incredibly grateful --- I was gifted a NeXT Cube by
| my brother-in-law when I was in college studying graphic
| design, and I was incredibly put out by the paucity of nice
| typography features in Quark XPress and Aldus Pagemaker when
| I came across TeXview.app and remembered checking out the
| book _TeX and Metafont_ from the local college library when I
| was a senior in high school --- built that into a career and
| a series of presentations at TUG conferences where I got to
| meet him.
| varjag wrote:
| The TAoCP itself is a side project from his original goal of
| writing a book on compilers.
| blipvert wrote:
| Gotta shave some Yaks
| fuzztester wrote:
| Did he complete the compilers book, or even start it? I
| know he has worked on TAoCP for a huge amount of time, and
| on TEX too.
| lukaslalinsky wrote:
| I was in San Francisco a few years back and I was amazed to learn
| that Donald Knuth not only still lives, but it still giving these
| once a year lectures in Stanford. Going there, finding the right
| building in the university, and then seeing this man speak about
| things I could only barely follow gave me such a memorable
| evening. What a legend Donald Knuth is.
| sheetjs wrote:
| Knuth is also still reviewing TAOCP-related email and issuing
| reward checks. A teammate received a reward check for 1 hex
| dollar last month after finding an error in Seminumerical
| Algorithms. Along with the check, there was a printout of the
| original email with hand-written annotations.
| WillAdams wrote:
| Note that it's no longer an actual check --- instead one gets
| a certificate of deposit at The Bank of San Seriffe:
|
| https://www-cs-faculty.stanford.edu/~knuth/boss.html
|
| (I got a physical check for $2.88 for a typo and a point of
| improvement in _Digital Typography_ --- need to find another
| so I can get an account....)
|
| If that was not included in your geography lessons see:
|
| https://legacy.geog.ucsb.edu/the-semicolonial-island-
| nation-...
| shagie wrote:
| https://en.wikipedia.org/wiki/Knuth_reward_check
|
| And one of my favorite quotes on the subject:
|
| > Intelligence: Finding an error in a Knuth text.
| Stupidity: Cashing that $2.56 check you got.
|
| > -- Seen in a Slashdot signature, quoted by Tess O'Connor
| ( https://www.stgray.com/quotes/programmingquotes.html )
| WillAdams wrote:
| Some of the checks added up to quite a bit more than that
| (if there's ever another error check for TeX it will be
| for $327.68), and one notable at a TeX User's Group
| conference stated that he had cashed a check for $40.96
| and was grateful to DEK for it, since it put food on his
| table when he was a poor starving grad student.
| anigbrowl wrote:
| Knuth is as amazing as ever.
|
| Very surprising and disappointing that nobody at Stanford could
| get it together on the sound recording end to give this the
| clarity is deserves. It sounds like it was recorded on a
| dictaphone in someone's pocket. I'm not talking about Knuth's
| old-guy voice; listen to how bad it is when he stops to take an
| audience question.
| actionfromafar wrote:
| Maybe everyone around are so used to seeing him they sometimes
| forget he's a National Treasure. :-)
| xeonmc wrote:
| So what you're saying is, we need Nicholas Cage to abduct him
| to preserve the appreciation?
| petalmind wrote:
| Funny that Nicolas Cage comes up in this context. Here is a
| trivia snippet from
| https://www.imdb.com/title/tt23468450/trivia/:
|
| > During an interview, Osgood Perkins recalled a story from
| production where he learned Nicolas Cage has a particular
| skill that he says no other actor possesses: the ability to
| recognize how high or low he is able to speak without
| messing up the audio. According to Perkins: "The sound guy
| came over to me one day...(he) comes up to me a couple of
| days into Nic being on set and he's like 'Oz, I've never
| seen anything like it. When Nic is mic'd, I'm watching the
| dials, when Nic goes big, he goes _right_ to the line.
| Anything more, a decibel or two over that, and it would be
| hard to use. Then he goes down, he goes soft and his
| whispering and he 's barely talking, he goes right to the
| line. Anything past that line, you wouldn't be able to use
| it. He knows where the lines are. It's the craziest thing
| I've ever seen in my life'."
|
| Maybe Cage can contribute to the sound design problem
| actually.
| OskarS wrote:
| 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 programmers, but the way he
| designs and writes about algorithms is remarkable, truly unique.
| The Dancing Links implementation in 4B in particular (updated
| significantly from his famous paper) is like a work of art, it's
| such an intricate and gorgeous data structure, and blazing fast
| as well. Man still got it, in his 80s.
| pcranaway wrote:
| 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 wrote:
| 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 wrote:
| Implementing an algorithm like Dancing Links is a hugely
| rewarding experience as a programmer. You learn by doing.
| fjfaase wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| In addition, I'd also recommend looking at his
| implementations, directly. https://www-cs-
| faculty.stanford.edu/~knuth/programs/dlx6.w, for example.
| bandana wrote:
| 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).
| OskarS wrote:
| 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 wrote:
| 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 wrote:
| He now uses MMIX, a modified version of MIX with RISC
| characteristics.
| taeric wrote:
| 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
|
| Expect code that will challenge some ideas on premature
| optimization. He codes much closer to the numbers than many
| are used to.
| colmmacc wrote:
| 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.
| jjice wrote:
| These are the kinds of stories I love from HN! Stories of
| theory meeting practice are my absolute favorite.
|
| My dad got me a set of TAoCP a few years back as a birthday
| gift (before 4b) and I realized that I do not have the
| background to even begin on 1 (at least not without some
| daily devotion of time). Maybe I'll have to take some more
| time and try again.
| graememcc wrote:
| Do thank your colleagues in the retail arm over on .co.uk for
| me.
|
| On launch, they very briefly mislisted the updated TAOCP 1-4B
| box set at PS33 (~ $40), and to my surprise and delight,
| honoured it!
| jkaptur wrote:
| > 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...
|
| It's frankly unbelievable how frequently this happens.
| "Swimming around" in these concepts inspires solutions that
| otherwise seem to come from nowhere.
| kupopuffs wrote:
| you saved millions and all you can get are these free bananas
| vrnvu wrote:
| I had to check... 87 years! Donald Knuth was born January 10th,
| 1938
|
| Wow.
| djmips wrote:
| I can dream...
| larodi wrote:
| He's dressed in something very vivid and lively, which kind of
| looks like the sort of world/ethnic dress you had in villages
| back in the day, but I can't tell whether is Iranian or Slavic or
| where in between...?
|
| Anyone care to guess better than myself?
| velo_aprx wrote:
| It kinda looks somewhat like sami clothing to me
| PaulRobinson wrote:
| I can't find the source, but I remember seeing him wearing this
| at another talk and him explaining that it was a hand made and
| stitched shirt inspired by a native group he had had some
| interaction with. The memory is really fading, may have
| involved his wife too. I can't find it, but there is an
| explanation out there somewhere. He wears it a lot at talks
| he's done since mid-2010s, it seems.
|
| Incidentally I was next to him as he was trying to stand on a
| window ledge to get sight of the Olympic torch coming into the
| square in front of Manchester Town Hall in 2012. I spoke to
| him, and reached out for him for a moment as I thought he was
| about to fall through the window, but he was all good. He came
| across as a very curious man, bright with questions and
| intelligence and younger than his years.
|
| We were both attending an event celebrating the centenary of
| Alan Turing, and I was surprised to find myself in a room with
| him, Gary Kasparov, Fred Brooks, Vint Cerf and many other
| luminaries of computer science. The Olympic torch came into the
| square outside during a lunch break, and he just couldn't help
| but take a look - he was the only there who seemed excited
| about it. He gave a talk at the dinner that night, and I saw
| him again in Manchester on another date when 4B had just been
| published, and he vaguely recognised me from the previous event
| when I asked him to sign it.
|
| I recount this story, because I think his shirt hints at a much
| more eclectic and curious mind - I definitely have seen
| evidence of it in other places.
| jhncls wrote:
| Donald's novel "Surreal Numbers" was written during one week of
| a long stay in Norway [0]. So, maybe there he got his
| admiration for traditional Sami clothing.
|
| [0]: https://youtu.be/jB0aeePskBg
| x187463 wrote:
| He wears it almost every year. You can go back to at least 1997
| in this playlist.
|
| https://www.youtube.com/playlist?list=PLoROMvodv4rOAvKVR_dyC...
| fuzztester wrote:
| Reminds me of either Larry Wall or Peter Norvig who wear
| colorful bush shirts. Hawaiian in the case of Norvig, I think I
| read somewhere a while ago.
| janvdberg wrote:
| Anecdote: In 2022, while visiting San Francisco, I had the chance
| to explore the campus. Wandering through the quiet, empty halls
| of the summer buildings, I was just about to leave when I
| unexpectedly came across Knuth's office [1]. I had to do a double
| take--it was surprisingly small for someone of his stature. Yet,
| in a way, it felt perfectly fitting, a reflection of his
| unassuming nature.
|
| https://janvandenberg.blog/wp-content/img_1813-scaled.jpg
|
| About the checks: I have not 1 but 2 checks. Small typos, nothing
| big: but wonderful to have these two documents.
| adakbar wrote:
| is he still use that office? I thought he mostly spent his time
| in his home office
| jagged-chisel wrote:
| Looks like a recent move or temporary office. Box of random
| items, basic paper name "plate," stacks on the desk ...
| capnahab wrote:
| Nice that he has a slide rule on the desk (under the front
| basket) looks like a K&E Deci-Lon case.
| postexitus wrote:
| That's a pretty cool office - not sure what other types of
| offices are available in the campus, but still. (Typing from
| the open office of hell)
| AndrewOMartin wrote:
| God bless whoever did the subtitles. Knuth's clarity of thought
| is unsurpassed, but, for me at least, actually hearing him speak
| is like the opposite of ASMR.
| jsbg wrote:
| I once met Knuth and asked him why he thinks that P = NP. He
| answered something about the fact that approximation solutions
| bridge the gap. Never meet your heroes!
| cjohnson318 wrote:
| Okay, but what did you reasonably expect?
| olddustytrail wrote:
| I wonder how many moronic questions Knuth has to endure? I
| guess this was just one more.
| Decabytes wrote:
| The thing I find most inspiring about Donald Knuth is his decades
| long commitment and discipline. As a serial project, language,
| and distro hopper, I have a lot I could learn from him
| esturcke wrote:
| I love how he handles questions:
| https://youtu.be/Hi8r_63LGyg?t=827. He takes the time to
| understand what was being asked and answers very clearly.
| b8 wrote:
| I got to talk to him once and he's a nice guy. Cool of him to go
| on Lex Fridman's podcast too.
___________________________________________________________________
(page generated 2025-02-07 23:00 UTC)