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

Advanced Data Structures

courses.csail.mit.edu

Post reply on HN
Print view View original

101–110 of 148 posts

Re: Advanced Data Structures

#101

Post by importantbrian »

shanusmagnus wrote: post #43
Koshkin wrote: post #39

Often shied away from as too complicated, this book deserves the obligatory mentioning: Knuth's The Art of Computer Programming . Although not using Python and perhaps being too analytical and detailed for an average programmer's taste, the book is the single biggest classic treatise on algorithms and data structures. At the other end of the spectrum - accessible and brief, I find Dasgupta et al. 's Algorithms a refr…

This book is often recommended, but I would dearly love to know how many of its recommenders have actually read it.

I don't think the point of this book is to read it cover to cover, or in this case cover to cover to cover to cover...since it's going on 4 volumes now. I think it's meant more as a reference. Pull it off the shelf and read the relevant section when you need it.

Re: Advanced Data Structures

#102

Post by vram22 »

vram22 wrote: post #100
abecedarius wrote: post #97

Earlier quoted context omitted.

Re: programming languages, it's worth mentioning that a Sanskrit grammarian invented something like context-free grammars around 2500 years ago: https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form#Histo...

Cool. I knew about Panini as a grammarian, but don't think I knew the part you mention about context-free grammars.

An interesting thing from that Wikipedia article:

"The name Pāṇini Backus form has also been suggested in view of the fact that the expansion Backus normal form may not be accurate, and that Pāṇini had independently developed a similar notation earlier."

So that may be one of the (few or common?) cases where something was named (or considered being named) after a person thousands of years after the person existed :)

Re: Advanced Data Structures

#103

Post by graycat »

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!

Thanks.

Given a directed graph with on each arc a maximum flow and a cost per unit of flow, how to find the least cost flows for a given total flow? That is linear programming. The simplex algorithm takes on a special form, and a simplex basic solution corresponds to a spanning tree. A simplex pivot is adding an arc to the tree to yield a circuit, and getting the cost of sending a unit of flow around the circuit evaluates that new arc. Etc.

W. Cunningham defined a strongly feasible basic solution which avoids cycling.

IIRC, D. Bertsekas has a good (polynomial) algorithm for that problem.

I didn't see such mentioned in your table of contents.

On my 14" screen, your PDF files would be much easier to read if the maximum number of characters per line was about 50.

Re: Advanced Data Structures

#104

Post by titanomachy »

jerf wrote: post #42
amelius wrote: post #40

This is very nice. But right now as a programmer, I am using data-structures more on an as-needed basis. Sometimes it is difficult to find the right data-structures for the job. So then it would be nice to have a resource that provides the functionality of data-structures as a black box. Learning these would make more sense than learning also all of the gory technical details upfront.

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"?

Re: Advanced Data Structures

#105

Post by nhatbui »

> If you haven't taken 6.854, you must have a strong understanding of algorithms at the undergraduate level, such as receiving an A in 6.046, having had a relevant UROP, involvement in computer competitions, etc.

Quite the pre-reqs...

Re: Advanced Data Structures

#106

Post by eequah9L »

Ar-Curunir wrote: post #67
bmon wrote: post #7

Earlier quoted context omitted.

I think it's more likely to be in something much more baremetal, given the topic. My university (UNSW) teaches a similar course with C.

No, it's more likely going to be in LaTeX, given the Erik Demaine's highly theoretical inclinations.

He talks about projects at the beginning of the second session, and implementation (of something that hasn't yet been implemented) is one of the possibilities.

Re: Advanced Data Structures

#108

Post by excelangue »

kyteland wrote: post #89
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…

Jeff is also a great professor. If you ever get the chance to take a course with him, do it. You won't regret it. I had him for both 173 and 373 back in the day, and credit his teaching style for the immense amount of material I picked up. Also, this: http://jeffe.cs.illinois.edu/teaching/pikachu.html

I'm currently taking 374 (the new 373). Unfortunately Jeff isn't leading my lectures, but the couple times he's subbed in were excellent. Really looking forward to taking 473 with Jeff next semester!

Re: Advanced Data Structures

#109

Post by 0x54MUR41 »

mej10 wrote: post #30
0x54MUR41 wrote: post #28

Thank you for sharing this. Anyone would recommend resources for learning fundamental of data structures? Book, video, or courses are welcome. I don't care the programming languages that are used for implementations. I am OK with C.

The Algorithm Design Manual by Steven Skiena Really enjoyed that book! It intersperses real world use cases which helps when your motivation starts to wane and has a warmer tone than most algorithm books. That being said, it is still pretty rigorous and will take a lot of work to get through it all. Whichever resource you choose, make sure it has exercises and do them! Even if you can't 100% figure some of them out j…

Thanks a lot.

I like your advice.

Re: Advanced Data Structures

#110

Post by 0x54MUR41 »

sn9 wrote: post #31
0x54MUR41 wrote: post #28

Thank you for sharing this. Anyone would recommend resources for learning fundamental of data structures? Book, video, or courses are welcome. I don't care the programming languages that are used for implementations. I am OK with C.

Skiena's book is excellent and is definitely one to get. Another would be Sedgewick's Algorithms . He has a pair of courses on Coursera [0] that follow his 4th edition which uses Java. You're in for such a treat! Learning data structures and algorithms is so fun and really changes the way you think about programming. [0] https://www.coursera.org/learn/introduction-to-algorithms

Thank you for your recommendation and advice. I will go for Skiena's book since a lot of people recommend it.
Post reply on HN