Topic  Name  Description 

Course Introduction  Course Syllabus  
Course Terms of Use  
1.1: Abstract Data Types  John DeNero's Composing Programs: "Data Abstraction"  Read this section, which expands the discussion and illustrates with native builtin types. The discussion in 2.2.1 is true of all native builtin types, and the tiny bit of Python code at the end of 2.2.1 should be easily understandable. Each of the builtin 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 codelevel perspective. 
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 userdefined compound types. These abstract data types are introduced this video, which you should watch starting at 44:30. This begins a languageagnostic discussion that is very valuable. 

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. 

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 oftenneeded data/method containers. Since the STL is largely datatype agnostic, templates begin to be very useful. 

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 commonlyused program components. It is very much worth your while to be familiar and practiced with this library. 

1.2: Contiguous Implementation  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 seriallygrouped (contiguous) memory. Otherwise, the array can not be allocated. 
1.3: NonContiguous Implementation  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  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 runtime 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  York College: Don Hake and David Hovemeyer's "Singly and DoublyLinked Lists"  Read this page to learn about singly and doubly linked lists and their implementation. 
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++. 

W3Resource: "C Programming Exercises: Linked Lists"  Try some of these exercises to get handson practice with linked lists. 

1.6: Arrays  W3Resource: "Arrays in C"  Read this introduction to arrays in C/C++. 
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. 

Seneca College: Elnaz Delpisheh's "Arrays"  Read this page, which includes graphical representations of arrays that illustrate their arrangement in contiguous memory. 

W3Resource: "C Programming Exercises: Arrays"  Attempt these exercises to gauge your understanding of arrays. 

2.1: Introduction to Lists  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  Virginia Tech: Clifford Shaffer's "Data Structures and Algorithm Analysis: ArrayBased 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  York College: David Hovemeyer's "Stacks and Queues"  Read this introduction to stacks and queues. 
2.3.1: Introduction to Stacks  Wikipedia: "Stacks"  Read this introduction to stacks, which are also known as lastin/firstout lists. 
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. 

University of Delhi: "Data Structures: Stacks"  Equation parsing is one application of stacks, as explained on this page. 

GeeksForGeeks: "Stack Data Structure"  This page illustrates the basics of stacks via a simple program. 

2.3.2: Introduction to Queues  Wikipedia: "Queues"  Read this introduction to queues, which are also known as firstin/firstout lists. 
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. 

University of Delhi: "Data Structures: Queues"  Job scheduling is one application of queues, as explained on this page. 

3.1: Review of CNative Variables  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." 
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 fixedsized 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  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  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  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  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  Wikipedia: "C Syntax  Pointers"  Read these sections. Twodimensional 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  Paul Gribble's "Pointers"  Work through these exercises to get some handson experience with pointers. 
4.1: C++ Memory Allocation  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. 
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  Hootnest: "C Data Structures"  Memory allocation is not just for native data types; they work for userdefined types as well. Read this discussion, which uses C, but note that in C++ new and delete work as well. 
York College of Pennsylvania: David Hovemeyer's "C Pointers and Dynamic Memory Allocation"  You shouldn't feel limited by C++ new and delete. The Clanguage memory allocation methods are also effective. 

4.3: Memory Fragmentation  Memory Management: "Stacks and Heaps"  Memory fragmentation can result from dynamic memory allocation, or memory allocated at runtime instead of compiletime. Read the section on heaps to get a good definition. 
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 garbagecleanup 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  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  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. 
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. 

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. 

Chris Szalwinski's "DoublyLinked Lists"  Doublylinked lists have many applications, and it is useful to have knowledge of their implementation. 

5.2: Linked Stacks  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 memoryuse expansion and is thus not suited for many industrial applications. 
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  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. 
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  Chemeketa Community College: "Algorithm Efficiency"  What is "algorithm efficiency"? This article gives a solid explanation. 
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: BigO Analysis  Chemeketa Community College: "BigO"  BigO analysis is a formal notation for discussing algorithm efficiency. This article introduces that notation. 
6.3: Discussions on Algorithm Efficiency  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  Massachusetts Institute of Technology: Erik Demaine's "Introduction to Algorithms"  Watch this video to learn about the mathematics behind BigO analysis. This type of discussion is important as your algorithms' complexity increases. 
6.5: SpaceTime Tradeoff  Wikipedia: "SpaceTime Tradeoff"  Most discussion on algorithm efficiency speaks to runtime, 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  Massachusetts Institute of Technology: Srini Devadas' "Algorithmic Thinking and Peak Finding"  This lecture introduces search algorithms. It also reviews what we have learned about timecomplexity. 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 memoryintensive. 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 cloudbased 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  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  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. 
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 divideandconquer 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. Divideandconquer applies to more than just sorting methods, but we focus on that in this lecture. 

7.3.1: BigO Analysis of Merge and Insertion Sort  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. 
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 resort 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++  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  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  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  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. 
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  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 BigO for this algorithm. 
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. 

Remi Dufour's "Nonrecursive Quicksort in C++"  This is a nonrecursive 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  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. 
Massachusetts Institute of Technology: Erik Demaine's "Table Doubling and KarpRabin"  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. 

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

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  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. 
Lehigh University: Ted Ralphs' "Graphs and Network Flows"  Review these slides, which discuss different graph representations and the efficiency of various representations. 

CodeProject: "Finding Noncyclical Paths between Arbitrary Pairs of Nodes"  This article explains how to find all noncyclical 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  The Daily Programmer: "C Program for DepthFirst Search in a Graph"  There are many ways to traverse a graph; this article focuses on depthfirst. This approach seeks a solution by going to the nodes furthest from the starting point. 
The Daily Programmer: "BreadthFirst 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 LowestCost Paths  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. 
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  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. 
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 forcefit someone's favorite tool to all situations. 

8.3: Trees  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. 
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. 

Virginia Tech: Clifford Shaffer's "Data Structures and Algorithm Analysis: NonBinary Trees"  Read this chapter, which extends the discussion on binary trees to those trees whose nodes have more than just two branches. 

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