Topic Name Description
Course Introduction Page Course Syllabus
Page Course Terms of Use
1.1: Abstract Data Types Page John DeNero's Composing Programs: "Data Abstraction"

Read this section, which expands the discussion and illustrates with native built-in types. The discussion in 2.2.1 is true of all native built-in types, and the tiny bit of Python code at the end of 2.2.1 should be easily understandable. Each of the built-in types have their own methods, which apply to them and which operate appropriately according to their type. Also, their internal representation is hidden at the code-level perspective.

Page Stanford University: Julie Zelenski's "Programming Abstractions: Sort Template with Callback"

While all languages include abstract data types in the form of native data types and their operations, there is also the matter of user-defined compound types. These abstract data types are introduced this video, which you should watch starting at 44:30. This begins a language-agnostic discussion that is very valuable.

Page Stanford University: Julie Zelenski's "Programming Abstractions: Abstract Data Types"

The discussion from the previous video continues in this lecture. Watch from the beginning until 7:00.

Page Derrick Robinson's "Intermediate C++"

Read these sections, which discuss the foundation of ADTs and the way they are implemented in C (as structures) and C++ (as classes). The Standard Template Library (STL) is now officially part of C++. The STL continues a natural progression from structures (data only) to classes (data plus operations on that data) to a library of trusted classes that implement often-needed data/method containers. Since the STL is largely data-type agnostic, templates begin to be very useful.

Page Stanford University: Keith Schwarz's "Programming Abstractions: Standard Template Library"

This lecture introduces the C++ Standard Template Library (STL) from 21:08 to 29:25. STL is a formal part of the C++ language, and is a set of class templates for many important and commonly-used program components. It is very much worth your while to be familiar and practiced with this library.

1.2: Contiguous Implementation Page Data Structures: "Arrays"

Read this introduction to the contiguous data structure type, which arrays are an example of. "Contiguous" refers to the memory occupied by the data structure being grouped serially by address. For instance, if an integer occupies four bytes, those four bytes are guaranteed to begin at the memory address of the first byte and end at the memory address of the fourth byte, so that those four bytes occupy memory addresses M, M+1, M+2, and M+3. One only has to reference address M to get the entire value of the integer. The same is true of contiguous arrays of any dimension. The cells of the array are guaranteed to occupy serially-grouped (contiguous) memory. Otherwise, the array can not be allocated.

1.3: Non-Contiguous Implementation Page Virginia Tech: "C++ Programming Tutorial in Chemistry: Memory Allocation"

Arrays can be implemented so that they do not occupy contiguous memory. The addressing is the same. For instance, A[r][c] still addresses the c'th column of the r'th row of array A. However, as we will see later in the course, one can not use the address of A[0][0] as the starting point for calculating the address of A[r][c]. The reason we use this type of array allocation is to delay allocating memory until it is needed. We can also easily get rid of array rows that contain data no longer needed. This is not possible with arrays allocated using native declaration syntax <type> A[numRow][numCol] since that approach allocates an entire block of memory for the array at one time. Read the linked page. Pay special attention to the "Matrix" section. You will notice that individual rows do occupy contiguous memory, but the array itself does not.

1.4: Introduction to Memory Pointers Page Karlina Ray Beringer's "Introduction to Pointers"

A pointer variable is a variable whose value is a memory address. Memory pointers can be very complex and few programmers really understand them, even though they are involved in many uses, from simple to complex. Pointers are an essential topic in C/C++, since they offer many opportunities for run-time improvement and ease of access to linked data structures. However, using pointers can also produce obscure code that is hard to understand. Misuse of pointers can also seriously corrupt memory during program execution, and these kinds of errors are very hard to track down. Even so, direct memory access is central to C/C++. As your compound data types become more multifaceted and are used within increasingly involved operations, a good understanding of pointers becomes even more important. Watch this video to get an excellent introduction to pointer variables.

1.5: Linked Lists Page York College: Don Hake and David Hovemeyer's "Singly and Doubly-Linked Lists"

Read this page to learn about singly and doubly linked lists and their implementation.

Page Stetson University: Joshua Eckroth's "Linked Lists"

Study the code examples on this page to see the how linked lists are implemented in C/C++.

URL W3Resource: "C Programming Exercises: Linked Lists"

Try some of these exercises to get hands-on practice with linked lists.

1.6: Arrays Page W3Resource: "Arrays in C"

Read this introduction to arrays in C/C++.

Page York College: Don Hake, David Hovemeyer, and Deepti Jindal's "Arrays"

Read this page, which covers additional features of arrays and gives some example code.

Page Seneca College: Elnaz Delpisheh's "Arrays"

Read this page, which includes graphical representations of arrays that illustrate their arrangement in contiguous memory.

URL W3Resource: "C Programming Exercises: Arrays"

Attempt these exercises to gauge your understanding of arrays.

2.1: Introduction to Lists File Virginia Tech: Clifford Shaffer's "Data Structures and Algorithm Analysis: Lists"

Read this short section about lists. Lists of things are common in everyday life. Organizing data that way in a computer's memory is one way we can get software to mimic a person's approach to task performance. When looking at  stacks and queues, we start with lists because lists are what stacks and queues manipulate.

2.2: Implementing Lists with Arrays File Virginia Tech: Clifford Shaffer's "Data Structures and Algorithm Analysis: Array-Based Lists"

Read this section, which introduces arrays and then discusses a specific implementation that uses arrays. Do not read the section on linked lists; we will cover them later in the course. 

2.3: Overview of Stacks and Queues Page York College: David Hovemeyer's "Stacks and Queues"

Read this introduction to stacks and queues.

2.3.1: Introduction to Stacks Page Wikipedia: "Stacks"

Read this introduction to stacks, which are also known as last-in/first-out lists.

File Virginia Tech: Clifford Shaffer's "Data Structures and Algorithm Analysis: Stacks"

Read section 4.2 on stacks. You will notice that this section is not nearly as long as the section on lists; this is because stacks are based on lists.

Page University of Delhi: "Data Structures: Stacks"

Equation parsing is one application of stacks, as explained on this page.

Page GeeksForGeeks: "Stack Data Structure"

This page illustrates the basics of stacks via a simple program.

2.3.2: Introduction to Queues Page Wikipedia: "Queues"

Read this introduction to queues, which are also known as first-in/first-out lists.

File Virginia Tech: Clifford Shaffer's "Data Structures and Algorithm Analysis: Queues"

Read section 4.3 on queues, which discusses some modifications to the list implementation that help to facilitate queues.

Page University of Delhi: "Data Structures: Queues"
Job scheduling is one application of queues, as explained on this page.
3.1: Review of C-Native Variables Page Wikipedia: "C Data Types"

Although this is not a language course, you should review these concepts, since an understanding this material is required before studying memory pointers. As described here, "In the C programming language, data types are declarations for memory locations or variables that determine the characteristics of the data that may be stored and the methods (operations) of processing that are permitted involving them."

Page Wikipedia: "Words in Computer Architecture"

Read this article. As it explains, "In computing, a word is the natural unit of data used by a particular processor design. A word is a fixed-sized piece of data handled as a unit by the instruction set or the hardware of the processor. The number of bits in a word (the word size, word width, or word length) is an important characteristic of any specific processor design or computer architecture."

3.2: Review of Pointers Page Stanford University: Julie Zelenski's "Programming Abstractions: Backtracking Pseudocode"

We touched on pointers earlier; this video reviews that material. Watch from 35:51 until the end.

3.3: Pointing to Memory Page Stanford University: Julie Zelenski's "Programming Abstractions: Pointers"
This video expands on the discussion of pointers presented earlier in this unit.
3.4: Pointers for Scalars, Vectors, and Functions Page Peter Hosey's "Everything You Need to Know about Pointers in C"

This article discusses scalar, vector, and function pointers. Scalars occupy varying amounts of memory. For instance, an integer may occupy four bytes and a double may occupy eight bytes. Some compilers allow for extensions, such as long int and long double. These increase the memory occupied by that type of variable, and the value's accuracy and/or numeric range. You can also use different compilers on the same machine, and the same compiler may behave differently on different machines. Always check the compiler's documentation relative to your machine. In any case, a pointer incremented by 1, for instance, will always point to the next cell of a vector or array of that pointer's type.

3.5: Pointers for Arrays Page Virginia Tech: "Memory Allocation"

Read this section on matrices. It shows how what we learned about pointers for vectors applies to building arrays. Essentially, we are building vectors of vectors. In the C/C++ sense, the first dimension points to the rows and the second dimension points to columns for a particular row. You will note that the vector of row pointers exists in contiguous memory, and that the columns for each individual row also exists in contiguous memory. However, it is not true that the array, as a whole, exists in contiguous memory. Thus, it is not possible to calculate a single memory pointer to a particular [r][c] cell of the array.

3.6: Pointer Arithmetic Page Wikipedia: "C Syntax - Pointers"

Read these sections. Two-dimensional matrices are very common in computer programming. This article expands on the previous one by getting specific about 2D matrix pointer arithmetic. Generalize your understanding of pointer arithmetic and you will see how it applies to data stored in contiguous memory. For instance, if you declare a pointer to a byte (unsigned char) you can march your way through any object that exists in contiguous memory.

3.7: Working with Pointers Page Paul Gribble's "Pointers"

Work through these exercises to get some hands-on experience with pointers.

4.1: C++ Memory Allocation File Massachusetts Institute of Technology: Geza Kovacs' "Memory Management"

Read these slides starting from Slide 13, "Scoping and Memory". These slides introduce how C++ is used to allocate and manage memory. Be sure you study memory allocation and management carefully, since it becomes increasingly important as data volume grows and as your program runs for longer periods of time.

Page Chris Szalwinski's "Dynamic Memory"

Allocating memory is not sufficient; you also have to manage it. Pay special attention to the methods and terminology on this page. There are some interesting exercises at the end of this page that you should attempt to complete.

4.2: C Memory Allocation Page Hootnest: "C Data Structures"

Memory allocation is not just for native data types; they work for user-defined types as well. Read this discussion, which uses C, but note that in C++ new and delete work as well.

Page York College of Pennsylvania: David Hovemeyer's "C Pointers and Dynamic Memory Allocation"

You shouldn't feel limited by C++ new and delete. The C-language memory allocation methods are also effective.

4.3: Memory Fragmentation Page Memory Management: "Stacks and Heaps"

Memory fragmentation can result from dynamic memory allocation, or memory allocated at runtime instead of compile-time. Read the section on heaps to get a good definition.

Page Optimizing C++: "Allocations and Deallocations"

It is possible to allocate and deallocate memory so that, even though there is sufficient memory overall, it has become so fragmented (chopped into pieces) that sufficient contiguous memory can no longer be found. At that point, no more memory allocations can take place. C/C++ does not have a native garbage-cleanup capability, so you either have to use a library to try to get it done or be careful in your allocations. This article gives advice on that topic; it is part of a larger discussion on optimization in C++.

4.4: C/C++ Based on "Unsafe" Types Page University of Washington: Keunwoo Lee's "Unsafe Languages"

C/C++ allows memory allocated for one type of variable to be recast as another type of variable; which gives us the term "unsafe types". This kind of casting makes sense in a lot of cases but no sense in other cases. It can be very powerful but must be used with caution, as this article explains.

5.1: Linked Lists File Virginia Tech: Clifford Shaffer's "Data Structures and Algorithm Analysis: Linked Lists"

Read this section on linked lists. Understanding this topic is essential to understanding linked stacks and linked queues, since those are special uses of linked lists.

Page Chris Szalwinski's "Introduction to Linked Lists"

This section introduces the basic concept of lists and how lists are used as stacks and queues. Read this page to get an introduction to the concept of a node. A node is a component within a list of objects that are related in some way. Our particular concern is with lists, stacks, and queues. The article discusses nodes from that perspective.

Page ChessProgramming: "Linked List"

We have looked at some code implementations, but it is worth examining at another approach, since there are many ways to use linked lists, and some are better than others depending on the application. Do not let yourself become dependent on one specific ways of doing things.

Page Chris Szalwinski's "Doubly-Linked Lists"

Doubly-linked lists have many applications, and it is useful to have knowledge of their implementation. 

5.2: Linked Stacks File Virginia Tech: Clifford Shaffer's "Data Structures and Algorithm Analysis: Linked Stacks"

Read this section on linked stacks, which expands linked lists so that stacks can be implemented. We ignore recursion since, while academically elegant, it leads to uncertain memory-use expansion and is thus not suited for many industrial applications.

Page An Algorithm a Day: "Implement a Stack using a Linked List"

We've seen several code implementations thus far, but it is worth looking at another approach, since there are many possible approaches. Some are better than others, depending on the application. Do not let yourself become set on one specific way of doing things.

5.3: Linked Queues File Virginia Tech: Clifford Shaffer's "Data Structures and Algorithm Analysis: Linked Queues"

Read Sections 4.3.2 and 4.3.3 on this page. The discussion is short, since queues are not much different from stacks. While the difference is subtle, it is important in many applications.

Page Steven Ford's "q Module"

This is another approach to linked queues. As with linked lists and linked stacks, don't get too attached to any one implementation.

6.1: The Importance of Algorithm Efficiency Page Chemeketa Community College: "Algorithm Efficiency"

What is "algorithm efficiency"? This article gives a solid explanation.

Page Massachusetts Institute of Technology: Eric Grimson and John Guttag's "Introduction to Efficiency"

Watch this lecture from 31:30 until the end. It expands on our introduction to algorithm efficiency, and will give you a good sense of what computer efficiency is and why it is important.

6.2: Big-O Analysis Page Chemeketa Community College: "Big-O"

Big-O analysis is a formal notation for discussing algorithm efficiency. This article introduces that notation.

6.3: Discussions on Algorithm Efficiency File Virginia Tech: Clifford Shaffer's "Data Structures and Algorithm Analysis: Algorithm Analysis"

For an excellent discussion on this topic that ties many pieces together, read Chapter 3. It is important to understand how to determine the resource complexity of an algorithm so that you can make worthy implementation choices. Those choices have to be based on all resources employed by the algorithm, to include time, memory, data interchange, hardware, etc.

6.4: Measuring Algorithm Efficiency Page Massachusetts Institute of Technology: Erik Demaine's "Introduction to Algorithms"

Watch this video to learn about the mathematics behind Big-O analysis. This type of discussion is important as your algorithms' complexity increases.

6.5: Space-Time Tradeoff Page Wikipedia: "Space-Time Tradeoff"

Most discussion on algorithm efficiency speaks to run-time, efficiency in CPU utilization. However, especially with cloud computing, memory utilization and data exchange volume must also be considered. This page gives a brief introduction to this topic.

7.1: Peak Finding via Vector Search Page Massachusetts Institute of Technology: Srini Devadas' "Algorithmic Thinking and Peak Finding"

This lecture introduces search algorithms. It also reviews what we have learned about time-complexity. These lectures use Python for illustration, but we will present code in C++. The point of the lectures is to understand the background of the various approaches; don't focus on Python specifically. This contrasts with other teaching approaches that start with the syntax of a particular language.

We begin with this particular lecture, since it introduces concepts that are important to understanding search and sort, graphs and hashing, and the scalability of various approaches. Though we will look at some other lectures in this series, the entire lecture series covers more than this course's purview, so we will not directly engage with all of them. However, you may wish to check out the course page for the original course at MIT, if you'd like more information on what is covered here.

"Complexity" refers to ALL resources consumed by an algorithm, although most people speak only of runtime (processing time, time to run successfully to completion). Refer to our earlier discussion on time/memory tradeoffs. You must consider the overall cost of running an algorithm. For instance, memory is expensive in cloud computing, so you have to be careful about saving time by using algorithms that are memory-intensive. You also have to consider other resources such as network utilization as data is transferred from one place to another. As you work, continue to think in this manner.

Searching, sorting, graphs, and hashing, using arrays or other data structures, are typically discussed in the context of recursion. While these are "academically elegant" and arguably easier to explain, recursion is memory inefficient. Generally, it assumes that large amounts of memory are available. However, that is rarely the case in industrial applications, especially with embedded systems. Additionally, the memory cost for cloud-based systems is high. Constant expansion of memory use with recursive approaches can eat up a lot of money very quickly. Thus, recursion will not be emphasized here.

7.2: Models of Computation and Document Distance Page Massachusetts Institute of Technology: Erik Demaine's "Models of Computation and Document Distance"

Here we emphasize the fact that a computer program is not an algorithm. Rather, a computer program is just one way of expressing an algorithm. Computer languages are just a means of expressing in syntax what we want the computer to do. Understanding this important nuance is essential as you delve into the algorithms we explore in this unit. For instance, sorting is not a matter of computer programming but a matter of algorithm development. It is true that ultimately, the computer has to be made to carry out the task at hand. However, we must start with an algorithm (what we want the computer to do), not with a computer program (how we make a computer do something). Otherwise, the computer becomes a limitation instead of an aid. This lecture also discusses document distance, which will be important for several examples in later lectures.

7.3: Why Sort? Insertion Sort and Merge Sort Page Massachusetts Institute of Technology: Srini Devadas' "Insertion Sort and Merge Sort"

Why bother with sorting data? This lecture discusses that question and then goes into two different sorting methods. You will notice that many search algorithms assume sorted data, especially with the large data volumes that are common today.

Page Massachusetts Institute of Technology: Eric Grimson and John Guttag's "Divide and Conquer Methods, Merge Sort, and Exceptions"

Watch this lecture to learn about the divide-and-conquer approach to sorting and its application to merge sorts. This approach is especially worthwhile when multiple computing cores are available, either with or without shared memory. Each divided component can be exercised independent of the other components. The merge step brings it all together. Divide-and-conquer applies to more than just sorting methods, but we focus on that in this lecture.

7.3.1: Big-O Analysis of Merge and Insertion Sort Page York College of Pennsylvania: David S. Babcock's "Insertion Sort"

Read this efficiency analysis of insertion sort. The pseudocode is easily reformatted for C/C++. Efficiency analysis is important when selecting solution methods appropriate for the application and situation.

Page York College of Pennsylvania: David S. Babcock's "Merge Sort"

This page presents an efficiency analysis of merge sort. It will help you choose the sorting algorithm appropriate to your project's requirements and situation. For instance, if data arrives over time, insertion sort using linked lists may well be the best choice. You certainly do not want to re-sort the entire collected data just to add one element. Most demonstrations of sorting methods assume that a large block of data already exists and that the task is to sort that data block. The case of data arriving over time is rarely considered but that is often the case in modern industrial and commercial applications. The "Internet of Things" (IoT) is a prime example, as is ongoing retail sales.

7.3.2: Merge and Insertion Sort in C/C++ Page Examples of Insertion and Merge Sorts in C++

Since the lectures in this unit use Python, review these examples of Insertion and Merge sorts in C++.

7.4: Linear Search Page Harvard University: "CS50: Linear Search"

Linear search is the most basic of search methods. Watch these videos to see how this simple search method works and how it is programmed in C/C++. You may wish to view the original link to find other useful material.

7.5: Fibonacci Search Page Keith Schwarz's "Fibonacci Search"

Fibonacci search expands on linear search in that the steps are greater than one. The comments in this C++ implementation explains.

7.6: Binary Search, and Bubble and Selection Sorts Page Massachusetts Institute of Technology: Eric Grimson and John Guttag's "Binary Search, Bubble and Selection Sorts"

Watch this lecture about binary search, bubble sort, and selection sort methods. You need to be aware of various approaches to solving sorting requirements.

Page Programming Simplified: "Binary Search, Bubble Sort, and Selection Sort in C++"

Since the lectures in this unit use Python for illustration, review these examples in C++.

7.7: Quicksort Page Massachusetts Institute of Technology: Erik Demaine and Charles Leiserson's "Quicksort and Randomized Algorithms"

Watch this lecture until 18:44 for an explanation of Quicksort. If you watch through the end, you will be led through a deep analysis that derives Big-O for this algorithm.

Page Crazy for Code: "Recursive Quicksort in C++"

This recursive implementation of quicksort in C++ closely mirrors the one discussed in the lecture, which used Python.

Page Remi Dufour's "Non-recursive Quicksort in C++"

This is a non-recursive version of Quicksort for C/C++. The variable "recursive" is used to show where recursion would normally take place. We present this since the lectures in this unit use Python for illustration.

8.1: Hash Tables Page Massachusetts Institute of Technology: Erik Demaine's "Hashing with Chaining"

This lecture introduces the concept of key/value pairs and how to search for them via hash functions. Chaining is used to handle collisions, which are when multiple values share the same key.

Page Massachusetts Institute of Technology: Erik Demaine's "Table Doubling and Karp-Rabin"

This lecture expands upon the previous one to introduce the possibilities of running out of space in the hash table or of having chains that are too long. In those cases, we would want to increase the size of the hash table; this lecture discusses how to do that effectively.

Page Massachusetts Institute of Technology: Srini Devadas' "Open Addressing and Cryptographic Hashing"

Watch this lecture, which foregoes chaining as a means of handling collisions and uses table-probing instead.

File Virginia Tech: Clifford Shaffer's "Data Structures and Algorithm Analysis: Hashing"

Read this section on hashing, which presents a different perspective than the lectures above. This section uses C/C++ syntax.

8.2: Graphs File Virginia Tech: Clifford Shaffer's "Data Structures and Algorithm Analysis: Graphs"

In computer science, the term "graph" refers to a set of vertices (points or nodes) and of edges (lines) that connect the vertices. The creation and traversal of graphs is an important topic when learning to solve complex problems that involve numerous relationships. Read this chapter for an excellent discussion on graphs and graph traversal.

File Lehigh University: Ted Ralphs' "Graphs and Network Flows"

Review these slides, which discuss different graph representations and the efficiency of various representations.

Page CodeProject: "Finding Non-cyclical Paths between Arbitrary Pairs of Nodes"

This article explains how to find all non-cyclical paths in a graph. Creating a traversal that visits nodes only once while still reaching the goal is a part of creating efficient solutions.

8.2.1: Graph Searches Page The Daily Programmer: "C Program for Depth-First Search in a Graph"

There are many ways to traverse a graph; this article focuses on depth-first. This approach seeks a solution by going to the nodes furthest from the starting point.

Page The Daily Programmer: "Breadth-First Search"

Another way to traverse a graph is to seek solutions starting at the closest nodes. This article explains how that is accomplished.

8.2.2: Finding Lowest-Cost Paths Page The Daily Programmer: "Dijkstra's Algorithm"

Getting from one node in a graph to another while expending the least cost is important in many domains. This article discusses Dijkstra's algorithm and its implementation.

Page The Daily Programmer: "Bellman's Algorithm"

An alternative approach to path finding is Bellman's algorithm. This page explains that approach and its implementation.

8.2.3: Finding a Minimum Spanning Tree Page York College of Pennsylvania: David S. Babcock's "Minimum Spanning Trees - Kruskal's Algorithm"

For a graph's vertices (nodes) and weighted edges connecting the vertices, a minimum spanning tree contains only the minimum number of edges connecting all vertices while having the minimum total weight when compared to all sets of edges that connect all vertices. Note that there may be more than one set of edges that has the minimum sum of weights. This article explains Kruskal's method of obtaining a minimum spanning tree.

Page York College of Pennsylvania: David S. Babcock's "Minimum Spanning Trees - Prim's Algorithm"

Prim created another popular approach to creating a minimum spanning tree. Since there is an infinity of potential application requirements and situations, there is never any one best approach in computer science, regardless of any academic snobbery you may encounter. Your ability to solve problems depends on your creativity, objectivity, and flexibility. Do not be trapped by an attempt to force-fit someone's favorite tool to all situations.

8.3: Trees Page Hendrix College: Carl Burch's "Data and Procedure: Trees"

Trees are a special case of graph, where the graph's nodes do not have multiple references. Tree traversal is only in one direction, downward, from root (top) to leaves (bottom). Read this page for basic definitions and illustrations.

File Virginia Tech: Clifford Shaffer's "Data Structures and Algorithm Analysis: Binary Trees"

Most discussion about trees concerns binary trees, whose nodes have no more than two branches. Read this chapter, which offers background and practical applications for binary trees.

File Virginia Tech: Clifford Shaffer's "Data Structures and Algorithm Analysis: Non-Binary Trees"

Read this chapter, which extends the discussion on binary trees to those trees whose nodes have more than just two branches.

Study Guides Page Unit 1 Study Guide: Abstract Data Types and Arrays in C++
Page Unit 2 Study Guide: Introduction to Stacks and Queues
Page Unit 3 Study Guide: Pointers and References in C++
Page Unit 4 Study Guide: Dynamic Memory Allocation
Page Unit 5 Study Guide: Linked Stacks, Queues, and Lists
Page Unit 6 Study Guide: Algorithm Efficiency
Page Unit 7 Study Guide: Searching and Sorting Algorithms
Page Unit 8 Study Guide: Hash Tables, Graphs, and Trees
Course Feedback Survey URL Course Feedback Survey