 | A reader requests that the formatting and layout of this book be improved. Good formatting makes a book easier to read and more interesting for readers. SeeEditing Wikitext for ideas, andWB:FB for examples of good books. Please continue toedit this book and improve formatting, even after this message has been removed. See thediscussion page for current progress. |
 | This book requires that you first read Data Structures. |
| This book requires that you first read Algorithms. |
This is a book to complement theData Structures book and theAlgorithms book, and assumes these books as prerequisites.
There are two conflicting goals in online book writing:
We've decided to do both. TheData Structures text and theAlgorithms text focus on just the fundamentals. This book (Advanced Data Structures and Algorithms) is a place for reference material. The idea is that a student in the span of a year or less can cover those fundamentals and then move on the advanced topics in this book.
While there is no content here yet, please feel free to start writing sections! Because this book is more of a reference, chapters can be more independent of each other. Further, you can assume the reader already knows the basic data-structures and algorithms.
As covered in the Algorithms book, by breaking an integer into two parts and treating it as a polynomial, we were able to derive a better-than-grade-school multiplication algorithm. Even more gains in efficiency can be made if we break the integer into three parts instead. However, we don't need to stop there: we can generalize the technique of polynomial multiplication and interpolation by breaking ann digit binary number into a degreen polynomial, which breaks the number up into its individual digits (and is the furthest we can divide such a number).
We noticed that evaluating the polynomial representations at points 1, -1, and 0 made the expressions easy, but if we are to use degree-2n polynomials, how can we come up with enough points to use? The trick is to evaluate the polynomial using complex numbers, in particular, by using "roots of unity": that is, complex numbers that are all distance 1 from the origin.
A Trie, also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is an ordered tree data structure often used to store an associative array where the keys are usually strings.Unlike abinary search tree, no node in the tree stores a complete key.
When dealing with lists, we normally have two choices: either we get indexed access but insertion with vectors, or indexing and insertion with linked lists. It'd be nice if we could find some middle ground, say with (amortized) running time for all operations. Well, Soren Sandmann has implementedGSequence, which uses a splay tree to achieve exactly that.[TODO: This structure doesn't have a widely accepted name yet. If someone can think of a better name, suggest it.]
I think B-tree algorithms give worst-case O(ln(N)) insertion, deletion, and access by name. Is GSequence better in some way? I've been told that some operating systems stored files and directories on disk as B-trees. --DavidCary 23:39, 21 July 2005 (UTC)
There's a number of balanced trees that give O(ln N) performance. The idea here is just wrapping a list interface around a tree. You might as well just say that you can use a tree since a list interface is only for implementation convenience.
There are various heap data structures that give O(log(N)) insertion, deletion and access by name.
I believe these are called random-access lists. Also, it is possible to get O(1) insertion and O(log N) indexing; e.g. Okasaki's skew-binomial random access lists. If there is an interest, I can upload a demonstration-quality implementation in Common Lisp.