Advanced Data Structures • Hacker News Board

Re: Advanced Data Structures

#131

Post by bonzini » Sat, Nov 05, 2016, 2:06 PM UTC

ludwigschubert wrote: post #125

Jun8 wrote: post #79

Earlier quoted context omitted.

Looks great, thanks a lot! While causally browsing I noted the following in the 8-queens backtracking example: "The following recursive algorithm, essentially due to Gauss (who called it “methodical groping”), ..." Hilarious, especially given the current situation. I'd like to know what his original German term was.

Oh this is a fun rabbit hole to go down: Gauss indeed wrote "methodisches tatonniren"[1], the latter of which is not a common German word, nor does it suggest grouping. I believe it to be an expression used at the time which was borrowed from French "tâtonner", which means "fumble", to describe a step-by-step process, "approaching" a solution. The closest I get in modern German is "herantasten", which in turn does no…

The word "tâtonner" should be the same as Italian "procedere (proceed) a tastoni", since usually the circumflex accent in French correspond to an "s" in Italian.

The meaning is "feel your way"---proceed carefully and at every step feel what is around you, as if you were walking on complete darkness.

Re: Advanced Data Structures

#132

Post by hackerboos » Sat, Nov 05, 2016, 2:29 PM UTC

fmardini wrote: post #107

A very underrated book and one of my favorites is Udi Manber's Introuction to Algorithms, highly recommended

I used that book for my dissertation. it had best explanation of the knapsack algorithm if I recall correctly.

Re: Advanced Data Structures

#133

Post by shanusmagnus » Sat, Nov 05, 2016, 3:23 PM UTC

vram22 wrote: post #92

hvmonk wrote: post #77

Earlier quoted context omitted.

off the topic, but what made you curious about Sanskrit?

I'm not the OP, but can comment about Sanskrit a bit. (I had studied Sanskrit in school.) [Edit:] As a third language, apart from English and Hindi. This is mostly all IMO, except where specified otherwise: - it's an interesting language, because it is the ancestor of many Indian languages (except the languages of the southern Indian states - Tamil, Telugu, Malayalam and Kannada - and their dialects - and except the…

Cool context! Thanks. I've often been tempted to learn Esperanto bc I've heard arguments made as to its general logical consistency. There's also a constructed language called Toki Pona [1] that is fascinating for similar reasons.

[1] https://en.wikipedia.org/wiki/Toki_Pona

Re: Advanced Data Structures

#134

Post by jerf » Sat, Nov 05, 2016, 3:24 PM UTC

titanomachy wrote: post #104

jerf wrote: post #42

Earlier quoted context omitted.

As you get into advanced data structures, you often need the gory technical details to make correct decisions about tradeoffs and usage. Succinct data structures, for instance, which are a specific thing and not just a generic adjective, are almost miraculously powerful, but you'd better understand exactly what the preconditions for using them are (which is a fairly mathematical discussion) and what the tradeoffs are…

I read some of the scribe notes on succinct data structures from the link, it jumped out at me as something interesting. But going from `O(n)` to `n + o(n)` doesn't seem especially game-changing -- what lead you to describe it as "miraculously powerful"?

The constant reduction is amazing, for those precise use cases you can afford to use them. Not all linear is created equal. O(10n) = O(n/10), but in practice the performance difference of the inner expressions can be a huge difference.

(Note that is a correct usage of the O notation; because of the fact that those two things are equal we generally just use O(n) because for clarity you might as well use the simplest member of the equivalence class defined by the O notation, but it is still valid to write O(n/10). It's just an error to treat it as anything other than equal to O(n).)

Re: Advanced Data Structures

#135

Post by bogomipz » Sat, Nov 05, 2016, 4:24 PM UTC

stuxnet79 wrote: post #56

I never hear anybody mentioning him but Jeff Erickson's 'Algorithms' textbook [1] has some of the most lucid explanations I've come across. CLRS is often times impenetrable and for the times I didn't like its explanation of something I turned to Jeff Erickson's book and it hasn't failed me yet. I'd urge anybody trying to solidify algorithms and data structures to take a look at it. [1] http://jeffe.cs.illinois.edu/te…

I had no idea about this. This looks fantastic! Theres a whole chapter on "advanced dynamic programming."!

I know people like to debate the merits of "thee algorithm book" be it CLRS or Desgupta etc. but I find that having many such books is extremely beneficial - occasionally one author will articulate a particular insight that will resonate for me in such a way that makes me believe I maybe hadn't completely internalized that thing before, despite having read similar content from other sources on many occasions and believing I had.

Anyway this looks like a great such addition to my personal canon. Thanks for sharing!

Re: Advanced Data Structures

#136

Post by bogomipz » Sat, Nov 05, 2016, 4:48 PM UTC

jefferickson wrote: post #71

stuxnet79 wrote: post #56

I never hear anybody mentioning him but Jeff Erickson's 'Algorithms' textbook [1] has some of the most lucid explanations I've come across. CLRS is often times impenetrable and for the times I didn't like its explanation of something I turned to Jeff Erickson's book and it hasn't failed me yet. I'd urge anybody trying to solidify algorithms and data structures to take a look at it. [1] http://jeffe.cs.illinois.edu/te…

Thanks for the shout-out! If you can't remember the long URL, http://algorithms.wtf also works. Please send me bug reports!

Hi, I looked at some of your lecture videos which also look great. You have a wonderful teaching style. Is there any possibility of these lecture videos getting on youtube? Watching is a little choppy. Cheers.

Re: Advanced Data Structures

#137

Post by make3 » Sat, Nov 05, 2016, 5:24 PM UTC

They better start close captioning or they will have to take the videos down

Re: Advanced Data Structures

#138

Post by vram22 » Sat, Nov 05, 2016, 5:58 PM UTC

shanusmagnus wrote: post #133

vram22 wrote: post #92

Earlier quoted context omitted.

I'm not the OP, but can comment about Sanskrit a bit. (I had studied Sanskrit in school.) [Edit:] As a third language, apart from English and Hindi. This is mostly all IMO, except where specified otherwise: - it's an interesting language, because it is the ancestor of many Indian languages (except the languages of the southern Indian states - Tamil, Telugu, Malayalam and Kannada - and their dialects - and except the…

Cool context! Thanks. I've often been tempted to learn Esperanto bc I've heard arguments made as to its general logical consistency. There's also a constructed language called Toki Pona [1] that is fascinating for similar reasons. [1] https://en.wikipedia.org/wiki/Toki_Pona

Interesting, will take a look.

Re: Advanced Data Structures

#139

Post by scns » Sat, Nov 05, 2016, 7:33 PM UTC

bonzini wrote: post #131

ludwigschubert wrote: post #125

Earlier quoted context omitted.

Oh this is a fun rabbit hole to go down: Gauss indeed wrote "methodisches tatonniren"[1], the latter of which is not a common German word, nor does it suggest grouping. I believe it to be an expression used at the time which was borrowed from French "tâtonner", which means "fumble", to describe a step-by-step process, "approaching" a solution. The closest I get in modern German is "herantasten", which in turn does no…

The word "tâtonner" should be the same as Italian "procedere (proceed) a tastoni", since usually the circumflex accent in French correspond to an "s" in Italian. The meaning is "feel your way"---proceed carefully and at every step feel what is around you, as if you were walking on complete darkness.

>proceed carefully and at every step feel what is around you, as if you were walking on complete darkness.

this would be a fitting translation of the german word "herantasten", which has nothing to do with groping btw

Re: Advanced Data Structures

#140

Post by susan_hall » Sat, Nov 05, 2016, 7:39 PM UTC

stuxnet79 wrote: post #56

I never hear anybody mentioning him but Jeff Erickson's 'Algorithms' textbook [1] has some of the most lucid explanations I've come across. CLRS is often times impenetrable and for the times I didn't like its explanation of something I turned to Jeff Erickson's book and it hasn't failed me yet. I'd urge anybody trying to solidify algorithms and data structures to take a look at it. [1] http://jeffe.cs.illinois.edu/te…

It is strange that neither Google nor Amazon can find this book:

https://www.google.com/search?q=Algorithms+Jeff+Erickson+sit...