Topic outline

  • 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.

    Page: 1
  • 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++.

    Page: 1
  • 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.

    Page: 1
  • 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.

    Page: 1
  • 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, students 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. Students will learn how to prevent these risks by utilizing the full capabilities of the C/C++ language to increase memory use efficiency.

    Page: 1
  • Unit 5: Linked Stacks, Queues, and Lists

    This unit will introduce students to three new types of Data Structures: Linked Stacks, Queues, and lists. We will discuss their respective operations and learn how the use of node classes and pointers can provide us with a means of implementing them.

    Page: 1
  • 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.

    Page: 1
  • 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.

    Page: 1
  • 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.

    Page: 1
  • Optional Course Evaluation Survey

    Please take a few moments to provide some feedback about this course at the link below. Consider completing the survey whether you have completed the course, you are nearly at that point, or you have just come to study one unit or a few units of this course.

    Link: Optional Course Evaluation Survey (HTML)

    Your feedback will focus our efforts to continually improve our course design, content, technology, and general ease-of-use. Additionally, your input will be considered alongside our consulting professors' evaluation of the course during its next round of peer review. As always, please report urgent course experience concerns to and/or our Discourse forums.

  • Final Exam

    Quiz: 1