Data structures and algorithms (DS&A) is an integral part of computer science. All written software stores and manipulates information (data) in one form or another. Data structures are standardized, efficient, and robust ways of temporarily storing information in memory. An algorithm, defined as a sequence of precise programming steps, allows us to further manipulate stored data in order to achieve meaningful results. Sorting, searching, and merging are just some of the algorithms commonly used nowadays, bundled into readily available development platforms. Similarly, the developer's toolset features a huge variety of data structures to choose from. Although a programming task may be achievable by more than one structure or algorithm (or specific implementations of them), choosing the right one may have a tremendous impact on efficacy, efficiency and scalability.
A typical data structures and algorithms course may involve any combination of the following topics:
- Arrays and Lookup Tables
- Linked Lists
- Circular Linked Lists
- Double Linked Lists
- Priority Queues
- Hash Tables (Dictionaries), Maps, and Graphs
- Binary Trees and Heaps
- Advanced Data Structures, Collections, and Generics
- Fixed (Immutable) and Variable (Dynamic) Size Implementation of Data Structures
- Implementation of Data Structures in Various Programming Languages, with C/C++ and Java being the most common.
- Pointers and Pointer Arithmetic
- Abstract Data Types (ADTs)
- Detailed Comparison of Available Data Structures
- Sort Algorithm Implementation and Comparison, such as Quick Sort, Bubble Sort, and Insertion Sort
- Search Algorithms and Techniques such as Linear Search, Binary Search Tree, Brute Force Search, and Heuristics
- Algorithm Analysis (Performance, Complexity)
- Big O Notation (e.g. O(n) and O(n log n))
- Algorithmic Thinking and Algorithm Design
Most recent books on data structures and algorithms tend to be platform and language-specific. For a general introduction to DS&A concepts, read Aho's Data Structures and Algorithms. For a Java-oriented introduction, both Lafore's Data Structures and Algorithms in Java and Carrano's Data Abstraction and Problem Solving With Java are a great starting point. For C/C++, Weiss' Data Structures and Algorithm Analysis in C++ is an excellent choice. Donald Knuth has contributed significantly to the development of the field with his findings, analyses and ideas published in the various volumes and fascicles of the computer science masterpiece The Art of Computing Programming. You can find academic resources on the topic by searching into conference proceedings and journals published by the ACM, IEEE, Springer, Elsevier, or papers indexed publicly by Google Scholar.
In some fields of knowledge there is a seminal work against which all other effort is compared, and that happens to be the case here. The title of the work, The Art of Computer Programming, is the masterpiece of Donald E. Knuth, professor emeritus at Stanford University. In fact, the intended seven-volume set, a work in progress, is so famous it has its own acronym, TAOCP.
The history of the development of The Art of Computer Programming is as interesting as the work itself. Knuth, an expert in compilers, began writing a book on compiler design in 1962, and when the first draft was finished in June of 1965, the hand-written manuscript was 3,000 pages. The original plan for a single volume of 12 chapters was quickly abandoned and replaced with a new plan for seven volumes, each with just one or two chapters. The first three volumes were published in 1968, 1969, and 1973. The work seemed to have a life of its own, however, and grew at such a pace that the fourth volume demanded further subdivision into what will be at least four separate subvolumes. The first installment of Volume 4 was not published until February 2005.
As early as 1976, Knuth was already going back to produce a second edition of Volume 2, and with the creation of more recent editions of existing volumes and the incomplete work that remained, The Art of Computer Programming became his lifelong endeavor. To date, only preliminary work has been completed on Volume 5. If you visit Donald Knuth's website, you will see statements about the present plans to publish Volume 4 as at least four separate subvolumes, the estimated arrival time of Volume 5 in 2015, and perhaps the most interesting of all: "As I write Volumes 4 and 5, I'll need to refer to topics that belong logically in Volumes 1, 2, and 3 but weren't invented yet when I wrote those books. Instead of putting such material artificially into Volumes 4 or 5, I'll put it into fascicle form."
Despite the length of time that's passed since Knuth began work on The Art of Computer Programming, the material remains authoritative. After reading the comments on his website, one can very much appreciate the term "life's work." Knuth is now 72, and the world can collectively hope that he is around long enough to complete all seven volumes. By that time, however, it will probably have turned into 10.
To fulfill our mission of educating students, our online tutoring centers are standing by 24/7, ready to assist students who need help with data structures and algorithms.