Survey basic abstract data types, their associated algorithms, and how they are implemented. Topics discussed include the structures of stacks, queues, lists, sorting and selection, searching, graphs, and hashing; performance tradeoffs of different implementations; and asymptotic analysis of running time and memory usage.
When we use programming for problem-solving purposes, data must be stored in certain forms, or Data Structures, so that operations on that data will yield a specific type of output. Imagine, for example, that a non-profit is having trouble staying afloat and needs an increase in donations. It decides it wants to keep track of its donors in a program in order to figure out who is contributing and why. You would first need to define the properties that would define those donors: name, address, amount donated, date of donation, and so on. Then, when the non-profit wants to determine how to best reach out to its donors, it can create a model of the average donor that contributes to the non-profit – say, for example, based on the size of the gift and the location – so that it can better determine who is most receptive to its mission. In this case, the size of the gift and the location are the "data" of the donor model. If the non-profit were to use this model, it would identify real donors by first generating an abstract donor. This is an example of using Abstract Data Types. Abstract Data Types both take into account the Data Structure (the way in which data about donors is stored) and provide the necessary operations on that structure. In this course, we will discuss the theoretical and practical aspects of algorithms and Data Structures. We will also learn to implement Data Structures and algorithms in C/C++, analyze those algorithms, and consider both their worst-case complexity and practical efficiency.
- Unit 1: Abstract Data Types and Arrays in C++
- Unit 2: Introduction to Stacks and Queues
- Unit 3: Pointers and References in C++
- Unit 4: Dynamic Memory Allocation
- Unit 5: Linked Stacks, Queues, and Lists
- Unit 6: Algorithm Efficiency
- Unit 7: Searching and Sorting Algorithms
- Unit 8: Hash Tables, Graphs, and Trees
- Discuss the general-purpose nature of Abstract Data Types (ADTs):
- Describe ADTs; and
- Summarize specific data types (SDTs) within the context of ADTs.
- Explain elementary data types within the wider context of ADTs:
- Interpret the three elementary data types that are native to C/C++ (scalars, vectors, multi-dimensional arrays) within the context of ADTs;
- Demonstrate the use of scalars, vectors, and multi-dimensional arrays;
- Show how scalars are used to build vectors; and
- Show how vectors can be used to build multi-dimensional arrays.
- Identify the five basic Composite Data Types (CDTs):
- Define the five basic CDTs (lists, stacks, queues, trees, graphs, hash tables);
- Relate an application's requirements to an appropriate CDT; and
- Implement solutions to applications requiring one or more of the five basic CDTs.
- Examine algorithms to determine their computer-resource utilization:
- Define Big-O analysis;
- Explain why Big-O analysis is important to algorithm design and selection;
- Distinguish between Big-O analysis, counting program steps, and counting lines of executable code; and
- Organize search and sort algorithms according to their Big-O resource utilization growth curve.
- Contrast sequential and binary search techniques:
- Define sequential search and name its primary attributes;
- Define binary search and name its primary attributes; and
- Compare the resource utilization curves of sequential and binary search as data-size increases.