Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Current draft of The Art of Computer Programming pre-fascicle 6a [ps]

www-cs-faculty.stanford.edu

Post reply on HN
Print view View original

41–50 of 116 posts

Re: Current draft of The Art of Computer Programming pre-fascicle 6a [ps]

#41

Post by schoen »

taosat wrote: post #21
nmrm wrote: post #2

There's some speculation about where the next breakthroughs will come from at the end of the chapter; it will be interesting to look back in 10-20 years and see if Knuth was correct.

A surprising tidbit: Knuth believes that P=NP is true, but the algorithm to solve NP is unknowable - footnote on page 1 (pdf page 9). Proponents of RSA, DHE crypto - take note.

I also liked the Fermatesque "exercise 223 is also currently unsolved, although I've rated it only '40' because I once thought of an answer (which I have since forgotten!)".

Re: Current draft of The Art of Computer Programming pre-fascicle 6a [ps]

#42

Post by JustSomeNobody »

japhyr wrote: post #36

I just picked up my father's old copy of vol. 1, Fundamental Algorithms . It's amazing that a book published in 1973 (second edition) can still be worth studying. I'd like to work from the copy I have, largely for sentimental reasons. My father passed away a few years ago, and it feels really good to work from the same book he studied decades ago. Is it reasonable to study the second edition, or should I buy a copy o…

Very little has changed in the fundamental ways we write software in the past decades.

Re: Current draft of The Art of Computer Programming pre-fascicle 6a [ps]

#44

Post by leephillips »

japhyr wrote: post #36

I just picked up my father's old copy of vol. 1, Fundamental Algorithms . It's amazing that a book published in 1973 (second edition) can still be worth studying. I'd like to work from the copy I have, largely for sentimental reasons. My father passed away a few years ago, and it feels really good to work from the same book he studied decades ago. Is it reasonable to study the second edition, or should I buy a copy o…

Knuth is a mathematician, and these are, mainly, books discussing mathematical results. Math is eternal - only the notation changes. You can, and, until recently, many did, learn geometry directly from Euclid.

Re: Current draft of The Art of Computer Programming pre-fascicle 6a [ps]

#45

Post by taosat »

Danltn wrote: post #40
lambda wrote: post #25

For anyone curious, this section is on SAT solving. It's section 7.2.2.2 of TAOCP, and is over 300 pages long. Pretty thorough for a section of backtrack, within a section on generating all possibilities, within a full chapter on combinatorial searching.

For what it's worth, I went to a presentation by Knuth on this exact section with a SAT expert who frequently commented how (for the presentation at least), significant amounts of relevant material had not been mentioned, and some techniques introduced were not particularly close to the state of the art, or good for educational purposes. What I'm saying is that there's plenty of literature on SAT Solving already, and…

Could you convince this SAT expert to review Knuth's fascicle and send his comments to Knuth? or blog about it for everyone's benefit?

Re: Current draft of The Art of Computer Programming pre-fascicle 6a [ps]

#46

Post by wslh »

leephillips wrote: post #44
japhyr wrote: post #36

I just picked up my father's old copy of vol. 1, Fundamental Algorithms . It's amazing that a book published in 1973 (second edition) can still be worth studying. I'd like to work from the copy I have, largely for sentimental reasons. My father passed away a few years ago, and it feels really good to work from the same book he studied decades ago. Is it reasonable to study the second edition, or should I buy a copy o…

Knuth is a mathematician, and these are, mainly, books discussing mathematical results. Math is eternal - only the notation changes. You can, and, until recently, many did, learn geometry directly from Euclid.

Indeed he would need to change the books if there is a breakthrough in some of the algorithm areas described, but TAO is an excellent way to "quicky" move to the state of art in many areas.

Re: Current draft of The Art of Computer Programming pre-fascicle 6a [ps]

#47

Post by IvyMike »

lallysingh wrote: post #3

ps.gz? It's 2015!

I suspect someone like Knuth might attract quite a bit of mail from "math cranks" [0]; this tiny little hurdle might actually discourage a few of them.

[0] https://empslocal.ex.ac.uk/people/staff/mrwatkin/isoc/crank.... (this an an excerpt from a paywalled NYT article here: http://www.nytimes.com/library/national/science/020999sci-ma... )

Re: Current draft of The Art of Computer Programming pre-fascicle 6a [ps]

#48

Post by codeshaman »

If this is art then I'll have to admit - after 20 years of learning and practicing programming, I'm still a mechanic (or craftsman), not an artist.

I will not be able to read and understand this book fully and I probably won't even try, unless I'm locked in a cell with it.

Although I've helped build software used by millions, what I did was stitch together things that are too brilliant (or insane) for me to fully understand. And I assume that most of my colleagues did the same.

There are pylons of brilliance on the shoulders of which everyone builds, and Knuth must be one of the strongest.

Thank you Mr Knuth for holding so much weight on your shoulders.

Re: Current draft of The Art of Computer Programming pre-fascicle 6a [ps]

#49

Post by taeric »

codeshaman wrote: post #48

If this is art then I'll have to admit - after 20 years of learning and practicing programming, I'm still a mechanic (or craftsman), not an artist. I will not be able to read and understand this book fully and I probably won't even try, unless I'm locked in a cell with it. Although I've helped build software used by millions, what I did was stitch together things that are too brilliant (or insane) for me to fully und…

You should try it, at the least. It is surprisingly approachable and a lot of fun. I make no claims to be proficient in even a majority of the exercises.

I will add that learning algorithms in the way he presents them has been hugely successful in really understanding working with abstractions. Not just inventing the cheap abstractions of giving names to things; but really understanding how you can abstract some problems onto others and use common tools in solving them.

Re: Current draft of The Art of Computer Programming pre-fascicle 6a [ps]

#50

Post by bluecalm »

>>These so-called "SAT solvers" are able to handle industrial-strength problems, involving millions of variables, with relative ease, andthey've had a profound impact on many areas of research such as computer-aided verification.

I would be very interested in hearing of industrial/practical applications of those. Anyone with some experience?

Post reply on HN