Class 9: A New Hope

I wanted to take a minute to thank you for all of your hard work. I know that you've just been through the toughest part of the semester so far. Some of you might even be worried about your grades and whether or not all of this effort is worth it or needed. First, let me assure you that any poor performances so far can be made up for. The grading will be gentle and I'm well aware of how difficult this approach is. I ask that you give it your all and assess the value-add from a future perspective. Imagine yourself at the end of this learning, building out the first Augmented Reality face reader and swimming in coins like Uncle Scrooge. (Let's take a look at the "Make it stick" quotes now.)

Another benefit from this first project is that many of you tried algorithms for the arithmetic that were just too slow. This is probably the first time you've really felt that need for clever speed. Let's build on that gut feel as we move forward. Anyhow, thanks for your efforts.

We now begin part 2 of the course, moving from C++ to dealing with the Abstract Data Types. Part 3 will be trees.

Next Round:

The next set of deadlines is in. For this segment of the course (Abstract Data Types) we will have 2 homeworks:

• HW2 is due April 5th
• Project 2 is due April 14th
• HW3 is due April 19th
• Test 2 is April 19th

Abstract Data Types

We know how to work with arrays. We can even build dynamic arrays which resize. Linked Lists are the other basic data structure you've played with but not studied. These three are the basic (atomic) building blocks of this course.

We want to analyze the behavior of basic operations in arrays and linked lists (and all of the other data structures). But what "basic operations" do we care most about?

First let me point out an important dichotomy in computer science: users think differently than implementers.

From now on we will separate the interface from the implementation. That means we will implement many different ways of achieving the same basic behavior. This is the idea behind an abstract data type.

A Basic API: The List ADT

I like the term API, "Application Programming Interface". You use it to describe how a USER uses your code. For our data structures I want to think about roughly the following list of features:

• insert(value), toss value into our data structure
• remove(value) (different than remove(key) )
• find(key) (different than find(value) )
• first() head to the logical first
• last() head to the final thing
• successor(value) find the next logical value after value
• predecessor(value) previous logical value

Complexity Task 1: At your table, chat out the complexity (linear, log, or constant) of each of these six operations using an unsorted dynamic array. Feel free to keep a constant number of variables floating around to help.

Complexity Task 2: How do your answers change if the list is sorted (and you preserve the sorted property as you alter it)?

Singly Linked Lists

In all of our pointer-based implementations we will be keeping data in some sort of a node. This is basically just a wrapper of some data with space for some pointers.

In a singly linked list we will make a daisy chain of nodes. Each with a pointer to the next node.

Here is an example of a singly linked list:

Implement Task 3: Take a look at Prepend, now add an Append function that inserts a node at the end of the singly-linked list.

Removal Task 4: How you would remove a node from a singly linked list?

Complexity Task 5: What is the complexity of removal this removal?

Display Task 6: Add a display() function which goes to each node and prints that value. What is the complexity of this? Can you imagine another data structure doing any better?

The STL version

The highly optimized C++ Standard Template Library version of a singly-linked list is called a forward_list.

Launch Task 7: forward_list is a feature of C++11, so we'll need to move to cloud9 to test. Compile the above gist in cloud9.

Infer Task 8: What does the auto type do?

Timing Task 9: Use a loop to fill a forward_list with 1000000 random ints. Then sort the list. Time this, and increase the number to 2000000 random ints. What complexity do you think they achieve for sorting their singly linked list?

Thought Experiment

What if we insist that our linked list always stay sorted?

Complexity Task 10: What are the complexities of the ADT list functions when we have a sorted singly linked list?

Search Task 11: Why can't you get the cost of search to logarithmic time? Why can you in a sorted array?

Score Sheet:

So today the goal is to be able to fill in the following table: