• Course Introduction

        • Time: 38 hours
        • Free Certificate
        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 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 (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.

        • Course Syllabus

          First, read the course syllabus. Then, enroll in the course by clicking "Enroll me". Click Unit 1 to read its introduction and learning outcomes. You will then see the learning materials and instructions on how to use them.

        • Unit 1: Abstract Data Types and Arrays in C++

          This unit will introduce you to Abstract Data Types and will make the important distinction between an Abstract Data Type and a Data Structure. You 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 7 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 4 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 2 hours.

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

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

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

        • Study Guide

          This study guide will help you get ready for the final exam. It discusses the key topics in each unit, walks through the learning outcomes, and lists important vocabulary. It is not meant to replace the course materials!

        • Course Feedback Survey

          Please take a few minutes to give us feedback about this course. We appreciate your feedback, whether you completed the whole course or even just a few resources. Your feedback will help us make our courses better, and we use your feedback each time we make updates to our courses.

          If you come across any urgent problems, email contact@saylor.org.

        • Certificate Final Exam

          Take this exam if you want to earn a free Course Completion Certificate.

          To receive a free Course Completion Certificate, you will need to earn a grade of 70% or higher on this final exam. Your grade for the exam will be calculated as soon as you complete it. If you do not pass the exam on your first try, you can take it again as many times as you want, with a 7-day waiting period between each attempt.

          Once you pass this final exam, you will be awarded a free Course Completion Certificate.