Computer Science 302
Data Structures
Spring 2006
Assignments

Revised May 9, 2006

Tuesday, January 17, 2006

Today we will broadly discuss the course as a whole.

We will also about the meaning of "big O". Although the concept was defined way over a hundred years ago, it is a very useful concept for complexity analysis today.

Thursday, January 19, 2006

Today, I will continue discussing "big O," "big Omega," and "big Theta." Although these concepts use exactly the same ideas as "big O," Omega and Theta were not introduced until fairly recently. The majority of students have trouble distinghishing O, Omega, and Theta, so I'll go over it very slowly to make it as clear as possible.

I will introduce you to techniques for asymptotically estimating the number of steps your program executes while running.

We will discuss the maximum subarray sum problem introduced in Section 2.4 of your textbook. This is a simple example of a problem where the choice of algorithm has a large effect on the running time.

Tuesday, January 24, 2006

Homework 1 is due today.

Today I will continue the discussion of the maximum subarray problem, and discuss related complexity issues. I will use mergesort as an example.

Thursday, January 26, 2006

Try to work (but do not hand in) Practice Problems 1.
Today we will introduce a few simple sorting algorithms.

I will also briefly mention the standard data structures "stack" and "queue," in preparation for a formal introduction next time.

Tuesday, January 31, 2006

Today we will discuss the concept of an abstract data type. We will then introduce the abstract data types stack and queue. Both stacks and queues are special cases of priority queues.

I will discuss array implementations of both stacks and queues. If time permits, I will discuss linked list implementations of stacks and queues, as well.

Thursday, February 2, 2006

Homework 2 is due today.

Tuesday, February 7, 2006

Today we will spend some time discussing Homework 3.

We will review material in Chapter 3 of your textbook.

Thursday, February 9, 2006

Homework 3 is due today.

Today we will spend some time talking about recursion. A rather skilled programmer I know does not use recursion, saying that, "Nobody understands recursion."
Read this discussion.
The alternative to recursion is looping. But it is better to use recursion to handle recursive data structures, such as linked lists or binary trees.

If time permits, we will begin the material of Chapter 4.

Tuesday, February 14, 2006

Today we will continue our discussion of search structures, including binary search trees.

Today we will review search structures, including binary search trees and 2-3 trees, and discuss recursive insertion, deletion, and rebalancing by rotation.

Thursday, February 16, 2006

Tuesday, February 21, 2006

Today we will discuss AVL trees and treaps. Both use rotation to rebalance a binary search tree.

If time permits, we will discuss hashing.

Thursday, February 23, 2006

Homework 4 is due today.

First Examination today. (There will be a second mid-term examination later.)

Study Guide.

Tuesday, February 28, 2006

We will hand back the examination.

We will introduce hashing.

• What properties should a good hash function have? Hint: when you grind meat, potatoes, and carrots into a hash, each ladelful of hash has a mixture of all the ingredients.
• What are three applications of hashing in practice?
• One example of a hash function is one you've very likely encountered: for each person x, let h(x) be the string consisting of the last four digits of x's social security number. Another is the last four digits of x's telephone number. Both of these are commonly used for which application, of the three I mention above?
• Why would the first six digits of a person's phone number (the area code plus the exchange) be a bad hash function?

Thursday, March 2, 2006

Today we will jump forward and discuss graphs.

We will introduce the subject in an elementary way.

If time permits, we will introduce the discussion of heaps. That topic leads naturally into the algorithm heapsort.

Tuesday, March 7, 2006

Homework 5 is due today.

Today we will review several methods of sorting, including heapsort, quicksort, mergesort, and polyphase mergesort.

If time permits, we will discuss disjoint set data structures and the union-find problem.

Here is a simple problem that reduces to union-find. Given the set of edges of a graph, is it connected? If not, how many components does it consist of?

If time permits, we will discuss Kruskal's algorithm.

Thursday, March 9, 2006

We will finish up topics from last time, and discuss how to form a binary tree from its preorder and inorder traversals.

Tuesday, March 21, 2006

We have done a few things with graphs up to now, but today we will seriously begin graph algorithms (Chapter 9 in your textbook).

Thursday, March 23, 2006

Homework 6 is due today.

We will continue our discussion of graphs, implementations of graphs, and graph algorithms.

Tuesday, March 28, 2006

We will continue our discussion of graphs, implementations of graphs, and graph algorithms.

Thursday, March 30, 2006

Homework 7 is due today.

We will continue our discussion of graphs, implementations of graphs, and graph algorithms.

In particular, we will go over two algorithms for the single source minimum path problem, namely the Bellman-Ford algorithm, which works for any weighted directed graph with no negative cycle, and Dijkstra's algorithm, which works for any weighted directed graph with no negative edge.

Tuesday, April 4, 2006

Today, we will discuss greedy algorithms. We will start with a simple version of the traveler's problem. (Also known as the paragraph breaking problem.)

Kruskal's and Prim's algorithms are other examples of greedy algorithms that you know.

For the single pair minimum path problem, the greedy algorithm is not correct, and may result in a path which is very far from optimal.

We will introduce Huffman's algorithm for prefix coding. This algorithm is greedy, and gives an optimal solution.

Consider the 2-partition problem, namely to divide a set of weighted items into two disjoint sets, such that the total weight of each is as close to half the total weight as possible. There is a simple greedy "approximation" algorithm for this problem, which produces a solution that is "close" to optimal.
There is no known polynomial time algorithm for the 2-partition problem. But if there are n weights and all of them are integers in the range 1 .. N, there is a dynamic programming algorithm that takes O(nN) time.

Thursday, April 6, 2006

Second Examination today.

Study Guide.

Tuesday, April 11, 2006

We will go over the exam.

We will discuss depth first and breadth first search, and algorithms for finding components of a graph and strong components of a directed graph.

If time permits, we'll begin a discussion of implementations of arrays.

Thursday, April 13, 2006 We will continue our discussion of implementations of arrays.

We will discuss base addresses, offsets, row-major order, and column-major order for "regular" array implementation.

We will discuss ragged arrays.

There are several ways to implement sparse arrays. There is no universal best implementation. The choice depends on the application. Here are some possibilities:

1. For multidimensional arrays only: "array of search structure" (This includes "array of linked list" as a special case.)
2. For any dimension: "Search structure." (This includes "hash table" and "linked list" as special cases.)
3. A very fast implementation, to be used when time is important, but space is not. This method is worthwhile only if individual array items are of a structured type which is larger than a single word.

Tuesday, April 18, 2006

Today, we will continue our discussion of sparse arrays and their implementations.

Thursday, April 20, 2006

Today, we will discuss a very fast implementation of a sparse array, where fetch and store are done in constant time.

We will also discuss implementations of ragged arrays, in detial.

Example.

Tuesday, April 25, 2006

There will be several topics today, including

1. Finding the k^th smallest value in a set, using randomization.
2. The Closest Pair Problem.
3. Convex Hulls.

Thursday, April 27, 2006

Homework 8 is due today.

There will be several topics today, including

1. Finding the k^th smallest value in a set, deterministically.
2. The Closest Pair Problem.
3. Memoization. (No, that is not a mispelling!) We will show how to use memoization to speed up computing the n^th Fibonacci number.

Tuesday, May 2, 2006

Today I will introduce the subject of NP-completeness. (Everybody's heard of it, few can define it.)

There are many problems known to be NP-complete. One example is the clique problem.

If time permits, I might mention undecidable problems.

On the final exam, I do expect you to know of the existence of NP-completeness and undecidability, but I do not expect you to be able to work with those concepts, or even to define them properly. That material will be presented in a later course.

Thursday, May 4, 2006

A summary of some shortest path algorithms.

Radix sort is used in many practical applications, since it breaks the "n log n" barrier if the range of possible keys is known in advance to be appropriate. (Example: the key is a social security number.)

Patricia trees.

Min-max heaps.

Wednesday, May 10, 2006

Office hours 9:00 to 11:30 today.

Thursday, May 11, 2006

Please consider the combination of the following two documents to be your sample final:

Sample final from Spring, 2005, postscript version. Here is a pdf version.

Additional sample problems, postscript version. Here is a pdf version.

Final Examination: 8:00 -- 10:00

Monday, May 16, 2006

Monday, May 20, 2006