Data Structures
Data structures comprise a significant portion of the programming. Choosing the correct one to use for any particular application can be a challenging task, but it can also significantly affect the application’s performance or effectiveness.
Lab 4-2 used the vector data structure to store bid data. This approach allowed it to be easily modified by sorting algorithms. Furthermore, since vectors can be resized, unlike arrays, bids could be easily added to them or removed as necessary. In Lab 5-2, a hash table structure allowed data to be quickly added and retrieved. This approach is particularly effective in situations where elements must be added and removed often and can be effectively hashed by a hash function.
A tree structure, used in Lab 6-2, can be useful in a situation where one needs to store large amounts of data items that can be ordered and must be accessed in random order. More specifically, a binary search tree, by imposing particular limitations on the way these elements are stored, allows this data to be accessed efficiently. Most importantly, when elements are added to or removed from the structure frequently and in a random order, a binary search tree naturally creates an efficient and ordered means of storing them. Using this structure is efficient because entries can be added and removed in random order. Other structures would potentially have to be sorted on each addition, which is a relatively slow procedure.
Algorithms
Algorithms are a similarly critical part of solving programming challenges. For instance, search algorithms are necessary when interacting with data structures that expose multiple elements. In some cases, such as with a linked list, inefficient algorithms, such as linear search, are the only suitable solution, as demonstrated by the program from Lab 3-2. Lab 4-2 demonstrates that two algorithms can be different in terms of speed while achieving the same results. The same set of data can be sorted using insertion sort, an O(N2) algorithm, or QuickSort, an O(N log N) algorithm. In practical terms, QuickSort sorts the same sample set of data in ½ to ⅔. The time insertion sort does the same.
Hash and chaining algorithms, used with the hash table data structure, allow easy random access to data, demonstrated in Lab 5-2. In addition to facilitating data storage, hashing functions see common use in uniquely identifying data without revealing it. Ideally, this results in a function that creates a unique key that changes significantly with minor changes in the input. This usage is seen in data security to confirm that a file has not been tampered with or corrupted in any way, as well as safely storing user passwords.
Lab 6-2: Binary Search Tree
This program implemented a binary search tree data structure to store bid information in an ordered, quickly searchable manner. It worked to the extent necessary for the assignment — it read bid data from an external CSV file, stored it in a binary search tree, and allowed entries to be added, searched, and removed. These functions use a binary search tree-specific algorithm related to binary search to find requested nodes. As a demonstration program, it only allowed the user a limited interface that prevented him or her from adding a new bid or choosing a target for search or removal operation. However, internally those functions were fully implemented as Insert, Remove, and Search, all taking a bid ID as their argument. This is a modular approach that allows the program to be easily modified — the user operations described above can easily be added without interfering with existing functionality, for instance.
The program is designed to work with an internal Bid structure. However, with minimal modification, the data structure can be adapted to store any type of data as long as individual elements have unique identifiers. Internally, this identifying field is the only property with which the data structure and algorithm interact. Therefore, they can be reused for a different project or a different data type.
Finally, the program’s code was annotated, explaining the purpose of each step in the data structure and algorithm declaration. Thus, a new programmer looking to understand or modify the code will find it easy. For example, the use of a generally undesirable while (true) loop is justified and explained by “a suitable parent node will always be found.” Similarly, step-by-step comments are provided for the tree search function.
Conclusions
Ultimately, data structures and algorithms play a critical role in a programmer’s work. While their general implementation is generally available as common modules or built into modern programming languages, choosing the one appropriate to the task is a challenging process. Data structures have a significant impact on how a program stores, processes, and accesses data. For instance, the stack and queue structures allow new elements to be added quickly and ensure they are accessed in a specific order, but they do not allow access to arbitrary elements. Different algorithms can achieve the same results from the same data at different speeds. For example, insertion sort and QuickSort both arrange arbitrary elements in ascending or descending order. However, as an O(N log N) algorithm, QuickSort does so significantly faster than insertion sort, which is O(N2) — up to two times as fast in one of the course’s programs.
This course’s most important lesson is the significance of the difference that a good or bad algorithm can make. In applications that process vast amounts of data in real time, such as analytics software, database servers, or games, this difference in performance can be enormous, even if the individual operations are relatively simple. Therefore, in such applications, the developer will likely have to examine his or her code at a lower level and implement custom algorithms and data structures.