Name: Advanced data structures
ISBN: 9780521880374

Advanced data structures

This text closely examines ideas, analysis, and implementation details of data structures as a specialised topic in applied algorithms. It looks at efficient ways to realise query and update operations on sets of numbers, intervals, or strings by various data structures, including: search trees; structures for sets of intervals or piece-wise constant functions; orthogonal range search structures; heaps; union-find structures; dynamization and persistence of structures; structures for strings; and hash tables. Instead of relegating data structures to trivial material used to illustrate object-oriented programming methodology, this is the first volume to show data structures as a crucial algorithmic topic. Numerous code examples in C and more than 500 references make Advanced Data Structures an indispensable text.

What Hacker News says

rramadassNov 2021

There are literally hundreds of threads with this topic on the Web. Most of them contain the same standard references which IMO are not always the best for people without much mathematical maturity and wishing to learn from first principles. That said, here are my recommendations for them (pdfs of almost all are available online and they can also be purchased cheaply as used books);

* 1) Functions and Graphs and 2) The Method of Coordinates by I.M.Gelfand et. al. - These give you the basics on functions and how to visualize them which is crucial for understanding.

* Introductory Logic and Sets for Computer Scientists by Nimal Nissanke - Nice succinct introduction to various required topics for Comp. Sci.

* Compared To What?: Introduction to the Analysis of Algorithms by Gregory Rawlins - This is a classic book which takes you by hand and walks you through Algorithm Analysis and the reqd. mathematics. You will find this more approachable than most other text books and well worth a study.

* How to Think about Algorithms by Jeff Edmonds - Practical techniques without too much mathematical formalism.

* Data Structure Techniques by Thomas Standish - A Classic text; good adjunct to more modern texts.

* Advanced Data Structures by Peter Brass - Nice succinct text but not necessarily "advanced".

One final point; try to get a Algorithms and Data Structures book with code in the language with which you are most familiar. That way you understand the mapping from "Abstract Algorithm" to "Concrete Language Implementation" which is not always trivial.

thread

DeathArrowApr 2020

Those books cover a part of topics I've studied at the University:

The Art of Computer Programming by Donald Knuth

Introduction to Algorithms by Thomas Cormen

An Introduction to Formal Languages and Automata by Peter Linz

Probability and Statistics by by Morris H. DeGroot

Operating Systems: Internals and Design Principles by William Stallings

Understanding Cryptography by Christof Paar

Database Systems: Fundamentals of Design, Implementations and Management by by Peter Rob

Principles of Concurrent and Distributed Programming: Algorithms and Models by M. Ben-Ari

Introduction to Graph Theory by Richard Trudeau

Advanced Data Structures by Peter Brass

Ones and Zeros: Understanding Boolean Algebra, Digital Circuits, and the Logic of Sets by John Gregg

An Introduction to Algebraic Structures by Joseph Landin

Theory of Computation by S.N. Sivanandam

You can always find more on https://cstheory.stackexchange.com/ or on some universities websites.

thread

rramadassJun 2019

Read books; follow the worked out examples very closely until you completely understand them. Then try programming it on your own from your understanding and memory. You have to put in the time and effort. I suggest studying books where complete implementations are given in a language of your choice and only later studying books with pseudo-code (i.e. go from specific to general). Also the chosen language should be simple without obscuring the core logic in OO/Functional syntactic sugar and structure (C is ideal here). The following are a few chosen books from my collection (used copies of all can be had for cheap online);

1) Data Structures and Program Design in C by Kruse, Leung and Tondo.

2) Algorithms in C (Parts1-4 and Part5 two-volume set) by Robert Sedgewick.

3) Compared to What? An Introduction to the Analysis of Algorithms by Gregory Rawlins.

4) How to think about Algorithms by Jeff Edmonds.

5) Advanced Data Structures by Peter Brass.

Finally, study the ideas, concepts and techniques behind the C++ STL library to see how to design Data Structures and Algorithms in a clean and independent manner and yet can couple them as reqd. in myriad ways for actual usage.

thread

todd8Oct 2016

Depending on your level of programming ability, one algorithm a day, IMHO, is completely doable. A number of comments and suggestions say that one per day is an unrealistic goal (yes, maybe it is) but the idea of setting a goal and working through a list of algorithms is very reasonable.

If you are just learning programming, plan on taking your time with the algorithms but practice coding every day. Find a fun project to attempt that is within your level of skill.

If you are a strong programmer in one language, find a book of algorithms using that language (some of the suggestions here in these comments are excellent). I list some of the books I like at the end of this comment.

If you are an experienced programmer, one algorithm per day is roughly doable. Especially so, because you are trying to learn one algorithm per day, not produce working, production level code for each algorithm each day.

Some algorithms are really families of algorithms and can take more than a day of study, hash based look up tables come to mind. First there are the hash functions themselves. That would be day one. Next there are several alternatives for storing entries in the hash table, e.g. open addressing vs chaining, days two and three. Then there are methods for handling collisions, linear probing, secondary hashing, etc.; that's day four. Finally there are important variations, perfect hashing, cuckoo hashing, robin hood hashing, and so forth; maybe another 5 days. Some languages are less appropriate for playing around and can make working with algorithms more difficult, instead of a couple of weeks this could easily take twice as long. After learning other methods of implementing fast lookups, its time to come back to hashing and understand when its appropriate and when alternatives are better and to understand how to combine methods for more sophisticated lookup methods.

I think you will be best served by modifying your goal a bit and saying that you will work on learning about algorithms every day and cover all of the material in a typical undergraduate course on the subject. It really is a fun branch of Computer Science.

A great starting point is Sedgewick's book/course, Algorithms [1]. For more depth and theory try [2], Cormen and Leiserson's excellent Introduction to Algorithms. Alternatively the theory is also covered by another book by Sedgewick, An Introduction to the Analysis of Algorithms [3]. A classic reference that goes far beyond these other books is of course Knuth [4], suitable for serious students of Computer Science less so as a book of recipes.

After these basics, there are books useful for special circumstances. If your goal is to be broadly and deeply familiar with Algorithms you will need to cover quite a bit of additional material.

Numerical methods -- Numerical Recipes 3rd Edition: The Art of Scientific Computing by Tuekolsky and Vetterling. I love this book. [5]

Randomized algorithms -- Randomized Algorithms by Motwani and Raghavan. [6], Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Michael Mitzenmacher, [7]

Hard problems (like NP) -- Approximation Algorithms by Vazirani [8]. How to Solve It: Modern Heuristics by Michalewicz and Fogel. [9]

Data structures -- Advanced Data Structures by Brass. [10]

Functional programming -- Pearls of Functional Algorithm Design by Bird [11] and Purely Functional Data Structures by Okasaki [12].

Bit twiddling -- Hacker's Delight by Warren [13].

Distributed and parallel programming -- this material gets very hard so perhaps Distributed Algorithms by Lynch [14].

Machine learning and AI related algorithms -- Bishop's Pattern Recognition and Machine Learning [15] and Norvig's Artificial Intelligence: A Modern Approach [16]

These books will cover most of what a Ph.D. in CS might be expected to understand about algorithms. It will take years of study to work though all of them. After that, you will be reading about algorithms in journal publications (ACM and IEEE memberships are useful). For example, a recent, practical, and important development in hashing methods is called cuckoo hashing, and I don't believe that it appears in any of the books I've listed.

[1] Sedgewick, Algorithms, 2015. https://www.amazon.com/Algorithms-Fourth-Deluxe-24-Part-Lect...

[2] Cormen, et al., Introduction to Algorithms, 2009. https://www.amazon.com/s/ref=nb_sb_ss_i_1_15?url=search-alia...

[3] Sedgewick, An Introduction to the Analysis of Algorithms, 2013. https://www.amazon.com/Introduction-Analysis-Algorithms-2nd/...

[4] Knuth, The Art of Computer Programming, 2011. https://www.amazon.com/Computer-Programming-Volumes-1-4A-Box...

[5] Tuekolsky and Vetterling, Numerical Recipes 3rd Edition: The Art of Scientific Computing, 2007. https://www.amazon.com/Numerical-Recipes-3rd-Scientific-Comp...

[6] https://www.amazon.com/Randomized-Algorithms-Rajeev-Motwani/...

[7]https://www.amazon.com/gp/product/0521835402/ref=pd_sim_14_2...

[8] Vazirani, https://www.amazon.com/Approximation-Algorithms-Vijay-V-Vazi...

[9] Michalewicz and Fogel, https://www.amazon.com/How-Solve-Heuristics-Zbigniew-Michale...

[10] Brass, https://www.amazon.com/Advanced-Data-Structures-Peter-Brass/...

[11] Bird, https://www.amazon.com/Pearls-Functional-Algorithm-Design-Ri...

[12] Okasaki, https://www.amazon.com/Purely-Functional-Structures-Chris-Ok...

[13] Warren, https://www.amazon.com/Hackers-Delight-2nd-Henry-Warren/dp/0...

[14] Lynch, https://www.amazon.com/Distributed-Algorithms-Kaufmann-Manag...

[15] Bishop, https://www.amazon.com/Pattern-Recognition-Learning-Informat...

[16] Norvig, https://www.amazon.com/Artificial-Intelligence-Modern-Approa...

thread