Computer Science 302
Data Structures
Spring 2007
Assignments

Revised May 9, 2007

Tuesday, January 16, 2007

This is the first day of class.

Read the list of data structure topics provided by the James Oravec, the TA for this course. You should be familiar with these topics by the end of the semester.

I will give a brief introduction of why this course is important and what you should expect from this course.

As a review read the preface and chapter 1 of your Weiss book.

Start reading chapter 2.

You will be introduced to algorithm analysis today. Some examples of analysis will be given in class.

On your own, try to work problems 2.1, 2.2, 2.3, 2.5, and 2.7 by next class.

Thursday, January 18, 2007

You should be done reading the preface and chapter 1. You should be close to finishing chapter 2.

I will spend time answering any questions about the problems from last class.

Today, I will continue lecturing on algorithm analysis and Big-O notation.

On your own, try to work problems 2.8, 2.10, 2.11, 2.12, 2.13, 2.14, 2.21, 2.29 and 2.34 by next class. Some of these problems are difficult and you should start working on them as soon as possible.

Tuesday, January 23, 2007

You should be done reading Chapter 2 of your textbook. Start reading Chapter 3.

I will collect Homework 1 from you today.

Today we will begin discussion of the material of Chapter 3, lists, stacks, and queues.

For fun and on your own, try to program bubble sort, insertion sort, and selection sort. Report the time complexity of each of these algorithms next class.

Thursday, January 25, 2007

Today we will continue our discussion of abstract data types, introducing stacks and queues.

Tuesday, January 30, 2007

Today we will continue our discussion of stacks and queues.

I will collect Homework 2 from you today.

Thursday, February 1, 2007

Today we will continue our discussion of stacks and queues.

We will introduce several implentations of stacks and queues.

Tuesday, February 6, 2007

Today we will discuss the maximum subsequence sum problem, showing different algorithms for the same problem that have vastly different time complexities.

We will also discuss the programming homework that is due tonight.

Homework 3 is due at midnight tonight.

Thursday, February 8, 2007

Today, we will introduce several algorithms for sorting a list.

Here are some algorithm that you will be expected to know before the exam:
Easy to learn:

• Bubblesort.
• Selection sort.
• Insertion sort.
• Merge sort.

Harder to learn:

• Quicksort.
• Heapsort.
• Polyphase mergesort.
• Binary tree insertion sort (sometimes known as binary tree sort).

Additional sorting algorithms of interest:

• Radix sort.
• Shell sort.

Tuesday, February 13, 2007

We will continue our discussion of sorting.

• What is the comparison model of computation?
• What is an in situ sorting algorithm?
• What is a comparison-exchange sorting algorithm?
• What is a sorting network?
• What is the theoretical lower bound of the time complexity of any sorting algorithm which uses the comparison model of computation?

We will introduce the concept of divide and conquer. Our first divide and conquer algorithm will be mergesort.

Thursday, February 15, 2007

Homework 4, updated is due in class today.

Tuesday, February 20, 2007 Homework 5 is due at midnight tonight.

Thursday, February 22, 2007

Examination today.

Tuesday, February 27, 2007

I will talk about priority queues today. A stack and a queue are priority queues, but there are others.

If time permits, I will define quicksort today.

Thursday, March 1, 2007

Today I will hand back the exam, and go over the problems in the exam.

Tuesday, March 6, 2007

Homework 6 is due at midnight tonight.

Today, we will introduce heaps.

We will also learn how to use a queue to a shortest path between two vertices in a graph.

If time permits, we will learn heapsort. An animation.

Thursday, March 8, 2007

Today, I will go over algorithms for greatest common divisor, longest monotone subsequence, and maximum subarray sum.

Tuesday, March 20, 2007

Homework 7 is due at midnight tonight.

I will spend today's lecture discussing the homework assignment.

Correction: the < href=http://en.wikipedia.org/wiki/Euclidean_algorithm> Wikipedia entry on Euclid's algorithm is not wrong, since it is stated, as an input condition, that the parameters are non-negative. (I didn't notice this condition, which is stated several lines above the pseudo-code.) However, you must write a function where the parameters can be any integers.

By the way, according to the Wikipedia site, Euclid himself did not invent Euclid's algorithm. It was published first in Euclid's elements around 300 BC, but may have been known 200 years earlier.
More generally, I've been told that many of Euclid's theorems are not due to Euclid personally, but that his book is composed of the work of a number of mathematicians.

Thursday, March 22, 2007

There will be an examination today, where the only questions will be to write C++ code. These questions will all be taken from Homework 7. This examination will not replace the second mid-term exam, which will take place as scheduled, on April 17.

Tuesday, March 27, 2007

Today, we will go over heapsort and polyphase mergesort.

Thursday, March 29, 2007

We will continue with polyphase mergesort, as I did not quite finish.

We will go over binary tree insertion sort.

We will discuss balanced binary search trees.

I will talk about balancing a binary search tree by using randomization.

Treapsort.

Tuesday, April 3, 2007

Today, we will hand back and discuss the examination.

Thursday, April 5, 2007

Tuesday, April 10, 2007

If you turn in Homework 8 by midnight tonight you will get extra credit.

Today we will cover B-trees.

Thursday, April 12, 2007

Homework 8 is due at midnight tonight.

Today we will cover hashing and hash tables.

• Collision is when different items have the same hash value. We need to use some form of collision resolution:
  • It is impractical to make a hash table large enough to avoid collisions. For a discussion of this, see the birthday paradox.
  • Closed hashing uses open addressing.
  • Open hashing uses chaining.
  • Do you find that confusing? I do! I always have to check to make sure I have it right.
• Secondary hashing is a form of open hashing where each entry in the hash table contains (or points to) a secondary hash table. It can be used for really large applications.
• Perfect hashing has no collisions. Its use is limited to cases where all items in the hash table are known in advance. An example of such an application is for a compiler, which could make use of a perfect hash table which contains all the keywords of a given language to separate keywords from other identifiers.

If time permits, we will introduce a union-find algorithm using a disjoint-set data structure.

Tuesday, April 17, 2007

Examination today.

Thursday, April 19, 2007

Tuesday, April 24, 2007

Homework 9 is due in class today.

Thursday, May 3, 2007

Today, we will talk about memoization.

Sunday, April 29, 2007

Homework 10 is due at midnight tonight.

Tuesday, May 1, 2007

Today we will talk about implementations of the ADT array.

Part of this topic will be implementation of sparse arrays.

Thursday, May 3, 2007

Today, we will hand back homework papers, and go over the solutions to Homework 9.

Sunday, May 6, 2007

Tomorrow, I plan to put up links to study material for the final. Meanwhile, you can look at study materials for previous semesters, which you can access HERE . If you find questions about material that we didn't go over this semester don't be alarmed: I will not ask questions on the final about topics we didn't mention this semester.

Monday, May 7, 2007

I will put up the practice final in two parts. Here is Part I: (postscript) (pdf)

A study guide for the final.

More study links.

Tuesday, May 8, 2007

Here is Part II of the practice final: (postscript) (pdf)

Wednesday, May 9, 2007

It is now Wed May 9 19:36:30 PDT 2007, and I am logging out. If you have any more email questions about the final exam, please feel free to send them. I'll try to amswer them early tomorrow morning.

Thursday, May 10, 2007

Final Examination: 8:00 -- 10:00