Win a copy of Node.js Design Patterns: Design and implement production-grade Node.js applications using proven patterns and techniques this week in the Server-Side JavaScript and NodeJS forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Rob Spoor
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Henry Wong
  • Liutauras Vilda
  • Jeanne Boyarsky
Saloon Keepers:
  • Jesse Silverman
  • Tim Holloway
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Mikalai Zaikin
  • Piet Souris

Advanced data structures?

 
Marshal
Posts: 74059
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Where do ordinary data structures and algorithms end and advanced data structures begin?
 
Marshal
Posts: 5003
319
IntelliJ IDE Python Java Linux
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
When you add "consultant" to your job title and an extra zero to your day rate?
 
Campbell Ritchie
Marshal
Posts: 74059
332
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
...and don't get paid for months afterwards? Is that advanced in the sense of lent?
 
Author
Posts: 20
7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The extra zero to the paycheck is a nice one!

Seriously now, that's a good question.
The truth is that, of course, it's a bit of a subjective matter, up to a certain point.

There can be several criteria:
- Advanced structures usually build on more basic ones
- The time that it takes you to implement a DS/algorithm
- The amount of math that you need to understand to implement it (luckily NOT needed to use it - that's what books like mine are for, showing how to use these DSs without necessarily knowing their internals)
- How widely a DS is used or known
- How much of an improvement (in terms of running time or memory usage) an advanced DS can offer in comparison to basic ones (for instance, you can store strings in a binary search tree, but with tries you get several advantages).

And while, as always, someone's advanced can be someone else's basic, there is still a certain consensus in the community about for instance stack and queues being basic, and (say) "soft heaps" being advanced
 
Campbell Ritchie
Marshal
Posts: 74059
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
What's a soft heap? Is it one where inactive objects are automatically deleted?
 
Bartender
Posts: 361
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
What's extra in this book compared to other Data structures and Algorithms books?
Does it talk about stable algorithm?
Does it talk about modern day algorithm being used at Big tech? Like the algorithm that was discussed during Facebook whistleblower testimony in Washington D.C.?
Thanks in advance.
 
Greenhorn
Posts: 18
2
IntelliJ IDE Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Sharma Ashutosh wrote:What's extra in this book compared to other Data structures and Algorithms books?
Does it talk about stable algorithm?
Does it talk about modern day algorithm being used at Big tech? Like the algorithm that was discussed during Facebook whistleblower testimony in Washington D.C.?
Thanks in advance.



Also, I had a look at the index of the book and many "use cases" are more related to AI than to data structures to my knowledge.
How does the book tackle them? Is the focus kept on the A&DS or does it shift a lot on those topics (e.g.: genetic algorithms) as well?

Thanks and hear you soon,
- Cosimo
 
Marcello La Rocca
Author
Posts: 20
7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:What's a soft heap? Is it one where inactive objects are automatically deleted?



A soft heap is a really advanced data structure. It's an approximate priority queue, for which you can control the error rate: meaning that you trade speed - sub-logarithmic running time - for accuracy of the results returned by methods like top (aka findmin)

https://www.cs.princeton.edu/~chazelle/pubs/sheap.pdf

It's not on my book, but we discussed about adding it, at some point... it's one of those I'd love to include in a "Seriously Advanced Algorithms and Data Structures" follow up, should we have the chance to write it
 
Campbell Ritchie
Marshal
Posts: 74059
332
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Than kyou
 
Marcello La Rocca
Author
Posts: 20
7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Sharma Ashutosh wrote:What's extra in this book compared to other Data structures and Algorithms books?


Thanks for your question Sharma!
I'd say that the main trait of this book, so that we tried (hard) to build a bridge between textbooks and "hands-on", practical guides. My idea was to build each chapter in layers, and let the reader go as far as needed and desired: so we first talk about a problem, then show possible solutions to it, next introduce a data structure that can solve it in a better way, and show how to use it for this purpose. For the interested readers, we then proceed to explain the internals of the algorithm/data structure, explain how they work, and possibly talk about the math behind it (when it's appropriate).
The main focus of each chapter is to show practical problems that you can find in your daily job, or anyway in the real world (not just theoretical teasers for interviews/challenges) and show different ways to solve them. Then if you want to delve further, you can learn how these DSs work.


Sharma Ashutosh wrote:Does it talk about stable algorithm?


How do you mean? Stable sorting algorithms? We don't explain those explicitly, but if I'm not mistaken stable sorting is mentioned a couple of times (also explaining why it's needed, when it is)

Sharma Ashutosh wrote:Does it talk about modern day algorithm being used at Big tech? Like the algorithm that was discussed during Facebook whistleblower testimony in Washington D.C.?


It does discuss algorithms used at big tech companies (well, I can swear I used some of them in such companies ), but not that kind of algorithms.
If you are referring, as I think, to the algorithms that are used to make recommendations and promote content to the users, those are usually complex ensembles that leverage several of the techniques described in the book (and many others not there, but that you can find for example in this great book by Luis Serrano: https://www.manning.com/books/grokking-machine-learning)
It does explain some foundational techniques and programming models, like MapReduce, or clustering, or gradient descent (used as the optimization technique behind supervised learning models)

Sharma Ashutosh wrote:Thanks in advance.


It's a pleasure, thanks to you for asking these questions!
 
Marcello La Rocca
Author
Posts: 20
7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Cosimo Damiano Prete wrote:
Also, I had a look at the index of the book and many "use cases" are more related to AI than to data structures to my knowledge.
How does the book tackle them? Is the focus kept on the A&DS or does it shift a lot on those topics (e.g.: genetic algorithms) as well?

Thanks and hear you soon,
- Cosimo



Hi Cosimo, thanks for your question!
Well, many data structures are used in AI, but I'd argue that doesn't make them fall exclusively in that field.
If anything I'd argue that is AI (here meant like ML) that is used a lot to solve some of the same problems for which these DSs are used.
You mention, for example, genetic algorithms: those are used a lot in optimization problems, but not necessarily in AI or ML. They have been used a lot to find approximate solutions to NP-complete and NP-hard problems, or for instance they were the first really successful technique to tackle protein folding. Which is now best solved using deep-learning (AlphaFold)

To answer your last question, I'd say the focus of the book is mostly on the A&DSs, but even more on the problems that they can help solving.
There are, however, a couple of chapters that are heavily focused on AI/ML: chapters 12 and 13, mostly about unsupervised learning and clustering.
 
Cosimo Damiano Prete
Greenhorn
Posts: 18
2
IntelliJ IDE Java Windows
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Marcello La Rocca wrote:

Cosimo Damiano Prete wrote:
Also, I had a look at the index of the book and many "use cases" are more related to AI than to data structures to my knowledge.
How does the book tackle them? Is the focus kept on the A&DS or does it shift a lot on those topics (e.g.: genetic algorithms) as well?

Thanks and hear you soon,
- Cosimo



Hi Cosimo, thanks for your question!
Well, many data structures are used in AI, but I'd argue that doesn't make them fall exclusively in that field.
If anything I'd argue that is AI (here meant like ML) that is used a lot to solve some of the same problems for which these DSs are used.
You mention, for example, genetic algorithms: those are used a lot in optimization problems, but not necessarily in AI or ML. They have been used a lot to find approximate solutions to NP-complete and NP-hard problems, or for instance they were the first really successful technique to tackle protein folding. Which is now best solved using deep-learning (AlphaFold)

To answer your last question, I'd say the focus of the book is mostly on the A&DSs, but even more on the problems that they can help solving.
There are, however, a couple of chapters that are heavily focused on AI/ML: chapters 12 and 13, mostly about unsupervised learning and clustering.



Hi Marcello.
All that sounds really interesting.

Do you cover basic A&DS as well (e.g., in an introduction or so)?

Cheers,
- Cosimo
 
Ranch Hand
Posts: 54
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Marcello!

In your reply to what are advanced data structures (in comparison to basic ones), you say that they build in top of the basic ones. For example, a d-ary heap would be an improvement (depending on the use case) of a binary heap.

Another definition for an advanced data structure or algorithm could be one where multiple basic data structures are combined (e.g. Tim Sort, where  the algorithm decides which sorting algorithm to use based in the nature of the input). Or a HashMap in Java, where a bucket is represented as a linked list or a red-black tree depending of the number of entries.

Does the book also cover examples of combined algorithms or data structures and how to analyse them?

Cheers,
Michael
 
Marcello La Rocca
Author
Posts: 20
7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Cosimo Damiano Prete wrote:

Hi Marcello.
All that sounds really interesting.

Do you cover basic A&DS as well (e.g., in an introduction or so)?

Cheers,
- Cosimo



Thanks Cosimo!
Yes indeed, we do cover some of the basics:
- Appendix C (and partly appendix D) is an introduction to basic DSs, from arrays versus lists, to hashing. It's not as in-depth as the rest of the book, but it's enough to get started.
- Appendix E is an intro to recursion
- Appendix F gives a brief summary of randomized algorithms and metrics (in particular for classification)

Cheers!
Marcello
 
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello Marcello,

Is the book helps to understand algorythms better in depth vs. Breadth?

I belive yes, but how?

What is a good approach to really understand and learn algorythm deeply?

Good luck with your new book!
Krisz
 
Campbell Ritchie
Marshal
Posts: 74059
332
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Kristian Jacobs wrote:. . . really understand and learn algorythm deeply? . . .

Once you have read about the algorithm, implement it. Try changing it, even introducing errors, and see what happens. See what happens if you introduce errors and use the algorithm on vital data.
 
Cosimo Damiano Prete
Greenhorn
Posts: 18
2
IntelliJ IDE Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Marcello La Rocca wrote:

Thanks Cosimo!
Yes indeed, we do cover some of the basics:
- Appendix C (and partly appendix D) is an introduction to basic DSs, from arrays versus lists, to hashing. It's not as in-depth as the rest of the book, but it's enough to get started.
- Appendix E is an intro to recursion
- Appendix F gives a brief summary of randomized algorithms and metrics (in particular for classification)

Cheers!
Marcello



Do you present and explain for every algorithm its complexity (in terms of big O) and the same for the operations provided by a particular data structure?
 
Campbell Ritchie
Marshal
Posts: 74059
332
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Cosimo Damiano Prete wrote:. . . explain for every algorithm its complexity . . .

I would have thought that was something basic which any book would cover; of course you need both time complexity and space (=memory use) complexity.
 
Marcello La Rocca
Author
Posts: 20
7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Cosimo Damiano Prete wrote:

Marcello La Rocca wrote:

Thanks Cosimo!
Yes indeed, we do cover some of the basics:
- Appendix C (and partly appendix D) is an introduction to basic DSs, from arrays versus lists, to hashing. It's not as in-depth as the rest of the book, but it's enough to get started.
- Appendix E is an intro to recursion
- Appendix F gives a brief summary of randomized algorithms and metrics (in particular for classification)

Cheers!
Marcello



Do you present and explain for every algorithm its complexity (in terms of big O) and the same for the operations provided by a particular data structure?



Yes indeed - as Campbell said, both running time and space. Also, when possible and useful, we present comparative analysis of these values across different data structures (for instance, the running time of dictionary operations for arrays, binary search trees, hash tables etc...)
 
Marcello La Rocca
Author
Posts: 20
7
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Kristian Jacobs wrote:Hello Marcello,


Kristian Jacobs wrote:
Good luck with your new book!
Krisz



Hi Krisz, thanks for your question and for the good wishes!

Kristian Jacobs wrote:
Is the book helps to understand algorythms better in depth vs. Breadth?

I belive yes, but how?


Yes indeed, in chapter 14 we explain both algorithms and try to explain how they work and where you should use one instead of the other. How? Well, we try to show real examples of situations where you want to use either (and other algorithms too, like Dijkstra and A*).

Kristian Jacobs wrote:
What is a good approach to really understand and learn algorythm deeply?


So yeah, I'd pretty much go with Campbell's advice here.

- Read about an algorithm
- Try it out with some example values, like on paper, to check your understanding of the steps
- Once you are confident, try to implement it in a language you are comfortable with
- Write tests for the cases you tried on paper, and maybe for the examples provided with the explanation you read (to have a baseline). Then try to find other edge cases that might challenge your implementation (remember the rule: "none, one, many"...)
- Share your code or find a challenge (leetcode, codewars and similar) that can be solved using this algorithm. This is useful both to better understand how it's used, and to further test your implementation.
- Optionally, try to improve the performance of your implementation: run some profiling to understand the pain points and where i could be improved.
 
Campbell Ritchie
Marshal
Posts: 74059
332
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Marcello La Rocca wrote:. . . comparative analysis of these values across different data structures . . .

Thank you; that is useful information to have.
 
Kristian Jacobs
Greenhorn
Posts: 9
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you for the advices Marcello!
 
Marcello La Rocca
Author
Posts: 20
7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You are welcome!
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic