• Course Introduction

        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 donation. 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 their donors, it can create a model of the average donor that contributes to the non-profit--say, for example, based on size of gift and location--so that it can better determine who is most receptive to its mission. In this case, size of gift and location are the "data” of the donor model. If the non-profit were to use this model, it would be identifying 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 (i.e. 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++

        This unit will introduce students to Abstract Data Types and will make the important distinction between an Abstract Data Type and a Data Structure. Students will also learn about arrays (a specific type of Data Structure) and the abstracted form of the array data type in C++.

        Completing this unit should take approximately 4 hours.

      • Unit 2: Introduction to Stacks and Queues

        This unit will introduce you to two basic Data Structures--Stacks and Queues--and identify the operations that must be provided with each Stack and Queue implementation. Students will also learn how arrays and circular arrays can be used to implement a Stack and a Queue and discuss the advantages and disadvantages of their use.

        Completing this unit should take approximately 3 hours.

      • Unit 3: Pointers and References in C++

        In this unit, students will cultivate a deeper understanding of how variables are declared and represented in memory. Students will also learn about pointers and how they can be used to reference certain memory locations.

        Completing this unit should take approximately 3 hours.

      • Unit 4: Dynamic Memory Allocation

        We will now learn about dynamic memory allocation. Frequently, we know neither the size of the data nor the Data Structure when implementing programs and Data Structures. By learning about dynamic memory allocation, you will understand how to request memory during runtime. We will also discuss the risks of memory allocation and de-allocation, learning about memory leaks and dangling pointers, among other potential drawbacks. You will learn how to prevent these risks by utilizing the full capabilities of the C/C++ language to increase memory use efficiency.

        Completing this unit should take approximately 1 hour.

      • Unit 5: Linked Stacks, Queues, and Lists

        In Unit 2, we discussed three common uses of abstract data types: lists, stacks, and queues, which we implemented via arrays. Now that we have discussed memory pointers in detail, we can see how to move through contiguous and non-contiguous memory. As our applications become increasingly complex and use greater volumes of data, it will become more difficult to allocate contiguous memory for all the data, or even to know how much memory to allocate. That is where linked data structures come into play. We can allocate contiguous memory relatively easy for a particular object (class or structure instance). When that object is no longer needed, it can be deallocated and the memory used for something else. If it is needed in relationship to another object, inter-object links can be created. Thus, we can have lists, stacks, and queues of constantly varying lengths as data arrives or its usefulness in active memory ends.

        Completing this unit should take approximately 1 hour.

      • Unit 6: Algorithm Efficiency

        There are a number of parameters that developers must consider when designing Data Structures. One of the most important parameters relates to the efficiency of the algorithms (i.e. searching algorithms) that can be used on the Data Structures. This unit will explain how to measure an algorithm's efficiency, identify problems that arise when taking these measurements, and present ways of representing algorithm efficiency.

        Completing this unit should take approximately 2 hours.

      • Unit 7: Searching and Sorting Algorithms

        In this unit, students will learn to apply searching and sorting algorithms to arrays. Students will also learn how to conduct worst-case and best-case analysis for these algorithms, determine their efficiency, and assign them generalized Big O notations.

        Completing this unit should take approximately 1 hour.

      • Unit 8: Hash Tables, Graphs, and Trees

        This unit will identify various problems that computer scientists encounter when using array indexes and present Hash Tables as a solution. Students will learn about different Hash Tables categories, identifying their respective performance efficiencies. The unit will conclude with an introduction to graphs and special graph types known as trees and binary trees. We will learn how to implement these new Data Structures, discuss operations that accompany them, and identify different ways of traversing, searching, and sorting them.

        Completing this unit should take approximately 4 hours.