Week 5, continued

Last time, we introduced this data structure called a linked list. This is a singly linked list, because there’s only one pointer between any pair of nodes.

Linked lists solve some of the problems we had with arrays - in particular, that arrays are fixed in size.

Linked lists do come with their own tradeoffs, though.

What are the operations that are important over a collection of items, like an array or a linked list? We need to be able to delete items, insert items, and search for items. How do we implement these on linked lists?

Recall the stack data structure that we mentioned last time. A stack canonically supports two operations: push (add an element to the top of the stack) and pop (pull an element off the top of the stack).

We can code up a stack as follows:

typedef struct
{
    int numbers[CAPACITY];
    int size;
}
stack;

So in memory, we then have the following (assume for the moment that the constant CAPACITY has been set with #define to 5, and size starts at 0 before we’ve put anything in the stack):

numbers
---------------------
|   |   |   |   |   |
---------------------
size
-----
| 0 |
-----

Now if we want to push the number 50, where should we put it in the array?

numbers
----------------------
| 50 |   |   |   |   |
----------------------
size
-----
| 1 |
-----

Let’s add a few more:

numbers
------------------------
| 50 | 51 | 61 |   |   |
------------------------
size
-----
| 3 |
-----

Now what happens if we pop an element? pop takes no arguments, and should just return the most recently added element of the stack (which in this case is 61).

We need to remove 61 from the numbers array, and decrement size.

This stack implementation has a problem - we can’t resize the numbers array, so it has a strict capacity of CAPACITY.

Instead, we can implement a stack this way:

typedef struct
{
    int* numbers;
    int size;
}
stack;

You should also be familiar with queues, the other abstract data structure we introduced last time.

Unlike a stack, which implements push and pop (values are added to the top and taken off the top), a queue has operations enqueue (add an element to the back of the queue) and dequeue (take an element off the front of the queue).

We can implement a queue like this:

typedef struct
{
    int front;
    int numbers[CAPACITY];
    int size;
}
queue;

If we enqueue the same numbers as before, it looks similar:

numbers
------------------------
| 50 | 51 | 61 |   |   |
------------------------
size
-----
| 3 |
-----
front
-----
| 0 |
-----

So how do we dequeue? We want to remove 50 (numbers[front]) and decrease the size, but just decrementing the size no longer tells us exactly what’s going on. We also need to keep track of where the front is, which we do by incrementing it:

numbers
------------------------
| 50 | 51 | 61 |   |   |
------------------------
size
-----
| 2 |
-----
front
-----
| 1 |
-----

Suppose we add more values, so now our queue looks like this:

numbers
----------------------------
| 50 | 51 | 61 | 121 | 124 |
----------------------------
size
-----
| 4 |
-----
front
-----
| 1 |
-----

Just as with the stack, we can give ourselves more size flexibility by switching out the explicit array for instead a pointer that we can assign with malloc:

typedef struct
{
    int front;
    int* numbers;
    int size;
}
queue;

We watch a short video in which Jack learns about queues and stacks.

Now that we have pointers - addresses of locations in memory - let’s look in more detail at what your computer’s memory looks like.

Each program is given its own area of memory (in fact, establishing the illusion that it has access to the entirety of your computer’s memory, even if multiple programs are running at once), which is laid out like this:

-----------------------------
|                           |
|           text            |
|                           |
-----------------------------
|      initialized data     |
-----------------------------
|     uninitialized data    |
-----------------------------
|           heap            |
|             |             |
|             |             |
|             v             |
|                           |
|                           |
|                           |
|             ^             |
|             |             |
|             |             |
|           stack           |
-----------------------------
|   environment variables   |
-----------------------------

Today, we’ll focus on the heap, another chunk of memory where variables are stored if assigned with malloc (or any of the Get functions from the CS50 Library, since those use malloc and the like under the hood).

Here’s a program that illustrates one way bad things can happen, particularly if you have malicious users:

#include <string.h>

void f(char* bar)
{
    char c[12];
    strncpy(c, bar, strlen(bar));
}

int main(int argc, char* argv[])
{
    f(argv[1]);
}

The implication is this diagram of a zoomed-in version of the bottom of the program’s stack:

|  unallocated stack space  |
-----------------------------
| c[0] |                    |
| ---- |                    |
|                           |
|         char c[12]        |
|                           |
|                   | ----- |
|                   | c[11] |
-----------------------------
|         char* bar         |
-----------------------------
|                           |
-----------------------------
|       return address      |
-----------------------------
|   parent routine's stack  |

What happens if we pass in a string with char* bar longer than c? You would overwrite char* bar and, even worse, the return address. Then the program would go back to, well, anywhere in memory that bar specified. When bad guys are curious if a program is buggy or exploitable, they send lots of inputs of different lengths, and when it causes your program to crash, then they have discovered a bug.

In particular, the best case might look something like this:

|  unallocated stack space  |
-----------------------------
|  h   |  e   |  l   |  l   |
| ---- | ---- | ---- | ---- |
|  o   |  \0  |             |
| ---- | ---- |             |
|         char c[12]        |
|                           |
|                           |
-----------------------------
|         char* bar         |
-----------------------------
|                           |
-----------------------------
|       return address      |
-----------------------------
|   parent routine's stack  |

But what about "attack code" that looks like this?

                |  unallocated stack space  |
  Address       -----------------------------
  0x80C03508 -> |  A   |  A   |  A   |  A   |
                | ---- | ---- | ---- | ---- |
                |  A   |  A   |  A   |  A   |
                | ---- | ---- | ---- | ---- |     char c[]
                |  A   |  A   |  A   |  A   |
                -----------------------------
                |  A   |  A   |  A   |  A   |     char* bar
                -----------------------------
                |  A   |  A   |  A   |  A   |
                -----------------------------
                | 0x08 | 0x35 | 0xC0 | 0x80 |    return address
                -----------------------------
                |   parent routine's stack  |

So in short, this bug came from not checking the boundaries of your array, and since the computer uses the stack from bottom up (think trays from Annenberg being stacked on a table), while arrays you push on the stack are written to from the top down, this is even more of a concern. And though there are ways and entire languages around this problem, the power of C comes with great responsibility and risk. If you ever read articles about "buffer-overflow attacks," then they’re probably talking about this.

One problem with linked lists that we mentioned on Monday and earlier today is that we don’t have random access to elements of the list, so searching for a value within a linked list requires O(n), linear time.

We claimed that we can construct a data structure that will give us O(log n) (logarithmic) lookup time, and even one that will give us O(1) (constant) lookup time.

If we have the numbers 22, 33, 44, 55, 66, 77, and 88, and we want to search for a value among them in logarithmic time, we can go back to what we learned in Week 2, throw them in an array, and use binary search:

------------------------------------
| 22 | 33 | 44 | 55 | 66 | 77 | 88 |
------------------------------------

But we can store our data in a cleverer way that still leverages the power of binary search without restricting us to a fixed number of elements like an array does.

Let’s introduce the general idea of a tree, a data structure in which nodes are connected in descending layers of children, growing downward like a family tree:

One specific kind of tree is a binary search tree:

We can implement a binary search tree with a struct, just as we did for previous data structures:

typedef struct node
{
    int n;
    struct node* left;
    struct node* right;
}
node;

We can write a search function on a binary search tree like so:

bool search(int n, node* tree)
{
    if (tree == NULL)
    {
        return false;
    }
    else if (n < tree->n)
    {
        return search(n, tree->left);
    }
    else if (n > tree->n)
    {
        return search(n, tree->right);
    }
    else
    {
        return true;
    }
}

Stepping away from trees, consider the German flag - or any similarly simple flag. If we’re storing this in an image format, it seems kind of a waste to store all the black pixels, then all the red pixels, then all the yellow pixels. What redundancy can we eliminate here?

Rather than remember the color of every pixel, we could encode just the leftmost column of the flag, and somehow indicate that this column should be repeated as many times as necessary to fill in the rest of the flag.

What about the French flag, where the bars are vertical rather than horizontal? We can imagine a similar approach, storing one row and repeating it as many times vertically as necessary to fill in the flag.

This will result in somewhat better compression for the German flag than the French flag, because there’s more horizontal redundancy.

When we compress video, we can do similar removal of redundancy by remembering only "key frames" and in between storing only what’s changed between those frames, throwing away the information that’s the same between frames.

But how do we compress text? Recall that text can be stored as ASCII, in which each character is 8 bits, or 1 byte. But not all characters are used equally frequently, so we might be able to get better information density if we use a smaller number of bits for more common characters (like E) and a larger number of bits for less common characters (like W).

There’s a method of compression called Huffman coding that uses the frequency of different characters while avoiding this problem of needing lots of extra space to separate characters. Imagine we have the following string that we want to compress:

"ECEABEADCAEDEEEECEADEEEEEDBAAEABDBBAAEAAAC
DDCCEABEEDCBEEDEAEEEEEAEEDBCEBEEADEAEEDAEBC
DEDEAEEDCEEAEEE"

A hash table is a data structure divided into "buckets" - imagine we’re sorting a deck of cards by suit; then our buckets would be hearts, diamonds, clubs, and spades.

Let’s consider a stack of blue books, like the ones used for exams; each has a student’s name on it. We can hash the blue books by each student’s first initial.

Let’s formalize this idea. The following is an array with the index of each row on the left:

This is one implementation of a hash table, a higher-level data structure, which could use an array or linked list or some other fundamental ingredient as a building block to making a more useful final result.

We can simply declare a hash table with something like char* table[CAPACITY];, in which case it will be an array with size CAPACITY, but we might call a hash table an abstract data type that is layering on top of this array.

Insertion starts by being Ο(1) since the array is empty and you can jump to the correct location immediately, but once your data set becomes larger, insertion becomes Ο(n) since we have to move down the array looking for a spot. If your array is big enough and your data is sparse enough, you get the advantage of constant time, but the risk makes linear probing imperfect.

Instead of a hash table, we can use another type of tree, called a trie or retrieval tree.

These tries use a lot of memory since each node allocates space for so many indices, and most of that space will be empty, at least initially when we have few strings.

But we gain speed and spend less time, since insertion time will be Ο(1), since no one has an infinitely long name. The longest word in the dictionary for the problem set will be 40-something letters long, but it will be constant and not depend on how many other names are in this data structure. The running time will now depend on the length of the string, which is asymptotically Ο(1).

Lookup of a name in a trie is equally fast regardless of how many other names are in the trie! It depends only on the length of the name.

Quiz 0 is next Wednesday!

There will be a lecture on Monday streamed live from Yale, because Monday is not a University holiday at Yale (although it is at Harvard).