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.

## Topic outline

- Course Introduction
- 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.** - 1.1: Abstract Data Types
Read this article.

You should read the "Data Abstraction" and "The Definitions in an ADT" sections of the reading to get a good understanding of Abstract Data Types. An ADT is a mathematical model that captures the problem domain in order to translate it into a program; some examples of ADTs include queues, lists, stacks, trees, graphs, and sets.

You should read the "Implementation Details" section of the reading to get a good understanding of how one can go about implementing Abstract Data Types. Since an ADT represents a mathematical model, an implementation of these models makes them accessible to computer programs. At this point you should think about what data types would be needed and what operations you would be performing on these data types. All of this is explained in the reading through the use of a class ADT.

- 1.2: Data Structures
- 1.2.1: Contiguous Implementation
Read this page for an introduction to the contiguous data structure type, of which arrays are an example.

- 1.2.2: Linked Implementation
Read this page to get a good understanding of C++ pointers and their usage.

Read this page to get an understanding of different types of linked lists, including endogenous and exogenous linked lists. Endogenous linked lists store links within the data. Typically, most linked lists store links outside of the data. Endogenous linked lists are useful in system programming tasks. Most linked lists store links outside of the data; these types of linked lists are called "exogenous" linked lists. In this reading we study doubly-linked lists and cyclic lists as examples of exogenous linked lists.

- 1.3: Arrays
Read this article. An array is a series of elements of the same type placed in contiguous memory locations that can be individually referenced by adding an index to a unique identifier. The number of elements in the array leads to the concept of the dimension of an array, and each item stored in there is an element. In this subunit we study how to access the elements of an array within the bounds of the dimensions of an array.

At any point of a program in which an array is visible, we can access the value of any of its elements individually as if it were a normal variable, and thus we are able to both read and modify its value.

Multidimensional arrays can be described as "arrays of arrays." For example, a two-dimensional array can be thought of as a matrix of elements that are of a uniform data type. But multidimensional arrays are not limited to two dimensions. We look into some examples of multidimensional arrays and their implementation in C.

Please complete all questions in this quiz.

- 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.** - 2.1: Introduction to Stacks
Read this page. A stack is characterized by two fundamental operations, called "push" and "pop." The push operation adds a new item to the top of the stack, or initializes the stack if it is empty. The pop operation removes an item from the top of the stack. We will study how to implement these stack operations. Earlier, we looked into abstract data types. A stack can have any abstract data type as an element. This subunit covers how the elements of a stack can be implemented and used in the stack operations discussed above.

A stack typically has a small number of operations performed on it. The nature of the pop and push operations mean that stack elements have a natural order. Elements are removed from the stack in the reverse order to the order of their addition; therefore, the lower elements are those that have been on the stack the longest. All of these are important aspects of stack construction.

Watch this lecture to gain an understanding of stacks.

- 2.2: Array-Based Implementation of a Stack
Read this page. Earlier, we covered the elements of a stack. Here we cover the order of elements of a stack when it is built using an array in programming languages like C++ and Java. Here we cover how the operations on a stack modify the stack, but we can still keep track of these elements when the stack is built using an array in programming languages like C++ and Java.

- 2.3: General Presentation of a Queue
This article covers append, empty, and serve operations on a queue. It also includes an array-based implementation of a queue with constant shuffling.

Click on the purple arrow (located in the upper left hand side) to move forward. Around the 5th click, a pop-up message will appear indicating that Java will run. Please be patient; the pop-up will disappear and you can read the example code. Please read the information provided in the above link in its entirety.

The first few slides cover the array implementation with constant shuffling and periodic moving. A queue is characterized by fundamental operations such as append, empty, and serve. Unlike a stack, in a queue, the addition of entities to the rear terminal position and removal of entities from the front terminal position makes it a first-in first-out (FIFO) structure. This subunit covers how to implement these queue operations using arrays, and with the concept of periodic moving.

The last two slides cover the circular array implementation of the queue. A queue and its operations can also be implemented as a circular array, which we cover in this section. Like in a stack, the elements of a queue can be constructed using any abstract data type.

- 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.** - 3.1: Programming Abstractions
Watch this video to gain an understanding of programming abstractions such as pointers, recursive data, and linked lists.

- 3.2: Pointing to Memory
The declaration, use, and dereferencing of pointers is covered in the sections "Reference Operators," "Dereference Operators," "Declaring Variables of Pointers Types," and "Pointers and Arrays" sections of the reading. A pointer references a location in memory, and obtaining the value at the location a pointer refers to is known as "dereferencing the pointer." Several languages support some type of pointer. Here we look into the fundamentals behind pointing to an item in the memory.

The pointer arithmetic involving adding a number to a pointer variable, and adding a number to a dereferenced pointer array, are covered in the "Pointer Initialization," "Pointer Arithmetic," and "Pointers to Pointers" sections of the reading. When you are pointing to something in memory, you need to be able to continue to point to the right item depending on the need for computation. This requires advancing pointers and taking steps back if needed. All of this needs pointer arithmetic. Knowledge of pointer arithmetic separates those who passably know C from those who know C really well. It's said that a good programmer understands pointers very well, while an average programmer finds anything with more than one pointer difficult to manage. This unit will help you make progress towards becoming a good programmer.

- 3.3: Pointer Arithmetic
Please complete all questions in this quiz.

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

**Completing this unit should take approximately 1 hour.** - 4.1: Dynamic Memory Allocation
Review these slides.

The first two slides of the reading address the differences between static and dynamic allocations and discuss what a memory heap is, the need for references, and the new operator.

Until now, in all our programs, we have only had as much memory available as we declared for our variables, with the size of all of them to be determined in the source code, before the execution of the program. But what if we need a variable amount of memory that can only be determined during runtime, for example, a case in which we need some user input to determine the necessary amount of memory space?

In order to request dynamic memory we use the operator new, which is followed by a data type specifier and--if a sequence of more than one element is required--the number of these within brackets [ ]. It returns a pointer to the beginning of the new block of memory allocated.

Most applications request memory from the heap when they are running. It is possible to run out of memory (you may even have gotten a message like "Running Low On Virtual Memory") when running a program. So, it is important to return memory to the heap when you no longer need it.

Memory leaks when it is allocated from the heap using the new operator but not returned to the heap using the delete operator.

We can dynamically allocate memory for objects, which the last slide covers in some detail.

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

**Completing this unit should take approximately 1 hour.** - 5.1: Nodes in Linked Stacks and Queues
Read this page. The author provides information about nodes in Linked Stacks with examples in C programming language. It also covers the empty method, the push methods, and the pop method associated with a stack.

- 5.2: Linked Queues
This page covers the empty method, the append methods, the server methods, and the private attributes associated with linked queues. The page provides information about Linked Queues as a Class with examples in C++.

- 5.3: Lists with Arrays
Read this page. The author provides information about creating linked lists with arrays using examples from C++. You will learn about the fixed size implementation, the overhead in shuffling, and implementation of a list with nodes as a class.

- 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.** - 6.1: Algorithm Efficiency Measurements
Watch this video to gain an understanding of the basics of the algorithm.

- 6.2: Bounds, Comparing Algorithms, and Determining Asymptotic Bounds
Review these slides.

- 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.** - 7.1: Searching Arrays
This video covers linear and binary search. In linear search, we discuss a worst-case target at the end of the array and derive the efficiency of the algorithm. We also look into the efficiency of the binary search algorithm. Please watch the video in its entirety. You only need to watch the video; you can disregard the remainder of the text on the page. The video provides general information about Linear and Binary Search using examples from C++.

- 7.2: Bubble Sorts for Arrays
This video provides general information about bubble sort with examples in C++.

Bubble sort works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items, and swapping them if they are in the wrong order. The algorithm gets its name from the way smaller elements "bubble" to the top of the list.

- 7.3: Insertion Sorts for Arrays
This video provides general information about insertion sort with examples in C++. Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. It is not the most efficient sorting algorithm, but it has a simple implementation and is quite efficient for small data sets.

- 7.4: Selection Sorts for Arrays
Read this page for information about selection sort, using examples in C++. Selection sort works by first finding the smallest in the array and exchanging it with the element in the first position, then finding the second smallest element and exchanging it with the element in the second position, and continues in this way until the entire array is sorted. Selection sort is not difficult to analyze compared to other sorting algorithms since none of the loops depend on the data in the array. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

- 7.5: Merge Sorts for Arrays
Watch this video. Merge sort is a divide-and-conquer approach in which you produce a single sequence of items ordered according to some rule, from two or more previously ordered or unordered sequences, without changing the items' size, structure, or total number. Although more than one pass may be required for a complete sort, items are selected during each pass on the basis of the entire key.

Merge sort is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output.

- 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.** - 8.1: Categories of Hash Functions, Linear Probing, and Chaining
This video covers hash table data structure. The first part of the video covers the types of hash functions, collisions, and the idea of chaining to deal with collisions. Hash collisions are practically unavoidable when hashing a random subset of a large set of possible keys. For example, if 2,500 keys are hashed into a million buckets, even with a perfectly uniform random distribution, according to the birthday problem there is a 95% chance of at least two of the keys being hashed to the same slot. Therefore, most hash table implementations have some collision-resolution strategy to handle such events. Some common strategies are described below. This has led to the ideas of linear probing and chaining. The second half of the video looks into efficiency and performance issues related to the hash table data structure.

- 8.2: Graphs
This lecture covers simple graphs, vertices, edges, and links. It discusses the idea of paths in graphs. Several graph types, including directed and undirected, are discussed. After that, the lecture covers data structures such as the adjacency matrix, adjacency list, and hash-table based implementations of graphs.

- 8.3: Additional Graph Concepts: Walk, Trail, Path, and Circuits
Read the first two sections of the document to get an understanding of walk, trail, path, and circuits associated with graphs.

- 8.4: Binary Search Trees (BST)
This lecture covers the basics of BSTs, using linked-list data structure for BSTs, how to do traversals on BSTs, different types of traversals, sorting and searching on BSTs, and insertion and removal of items from BSTs.