CS201: Elementary Data Structures

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.

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.

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

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.

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.

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.

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.

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.

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

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

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

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

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

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

Attempt these exercises to gauge your understanding of arrays.

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.

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. 

Read this introduction to stacks and queues.

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

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.

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

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

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

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

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:

Read this article. As it explains:

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

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.

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.

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.

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

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.

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.

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.

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

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.

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

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.

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.

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.

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.

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

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.

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.

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.

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

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

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.

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

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.

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

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.

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.

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.

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.

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.

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.

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.

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

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.

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

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

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

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.

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

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.

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.

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.

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

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

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.

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

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.

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.

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

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.

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

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.

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.

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.

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.

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