Topic  Name  Description 

Course Syllabus  Course Syllabus  
Course Terms of Use  
1.1: Abstract Data Types  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. 
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. 

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

Abstract Data Types in 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. 

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  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  Memory Allocation in C++  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  Pointers in C++  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  Singly and DoublyLinked Lists  Read this page to learn about singly and doubly linked lists and their implementation. 
Examples of Linked Lists  Study the code examples on this page to see the how linked lists are implemented in C/C++. 

Linked List Programming Exercises  Try some of these exercises to get handson practice with linked lists. 

1.6: Arrays  Arrays in C  Read this introduction to arrays in C/C++. 
Additional Features of Arrays  Read this page, which covers additional features of arrays and gives some example code. 

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

Array Programming Exercises  Attempt these exercises to gauge your understanding of arrays. 

2.1: Introduction to Lists  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  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  Stacks and Queues  Read this introduction to stacks and queues. 
2.3.1: Introduction to Stacks  Stacks  Read this introduction to stacks, which are also known as lastin/firstout lists. 
More on 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. 

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

The Stack Data Structure  This page illustrates the basics of stacks via a simple program. 

2.3.2: Introduction to Queues  Queues  Read this introduction to queues, which are also known as firstin/firstout lists. 
More on Queues  Read section 4.3 on queues, which discusses some modifications to the list implementation that help to facilitate queues. 

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

3.1: Review of CNative Variables  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." 
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  Backtracking Pseudocode  We touched on pointers earlier; this video reviews that material. Watch from 35:51 until the end. 
3.3: Pointing to Memory  Pointers  This video expands on the discussion of pointers presented earlier in this unit. 
3.4: Pointers for Scalars, Vectors, and Functions  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  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  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  Pointers  Work through these exercises to get some handson experience with pointers. 
4.1: C++ Memory Allocation  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. 
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  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. 
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  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. 
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  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  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. 
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. 

Other Ways to Use Linked Lists  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. 

DoublyLinked Lists  Doublylinked lists have many applications, and it is useful to have knowledge of their implementation. 

5.2: Linked Stacks  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. 
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  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. 
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  Algorithm Efficiency  What is "algorithm efficiency"? This article gives a solid explanation. 
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  BigO  BigO analysis is a formal notation for discussing algorithm efficiency. This article introduces that notation. 
6.3: Discussions on Algorithm Efficiency  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  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  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  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  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  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. 
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  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. 
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  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  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, Bubble Sort, and Selection Sorts  Binary Search, Bubble Sort, and Selection Sort  Watch this lecture about binary search, bubble sort, and selection sort methods. You need to be aware of various approaches to solving sorting requirements. 
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  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. 
Recursive Quicksort in C++  This recursive implementation of quicksort in C++ closely mirrors the one discussed in the lecture, which used Python. 

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

Open Addressing and Cryptographic Hashing  Watch this lecture, which foregoes chaining as a means of handling collisions and uses tableprobing instead. 

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

8.2: Graphs  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. 
Graphs and Network Flows  Review these slides, which discuss different graph representations and the efficiency of various representations. 

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

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

Study Guide  CS201 Study Guide  
Course Feedback Survey  Course Feedback Survey 