Computer Science 302
Data Structures
Fall 2008
Notes and Assignments

Revised December 9, 2008

Tuesday, August 28, 2007

This Wikipedia page gives an excellent summary of "Big O" notation, otherwise known as Landau notation. You've heard that Wikipedia is unreliable, and that's true. However, most of the articles are correct. I checked this one, and it hasn't changed since I checked it.
Read only down to, but not including, the section "Related asymptotic notation." Some of those further topics will be covered later.
Also, skip the section Infinitesimal Asymptotics, as that section does not apply to the usage of Landau notation in computer science.

Thursday, August 28, 2008

Due to an unusual situation, no office hours today.

Tuesday September 2, 2008.

Chitwan Gupta will be out of town this week.

Thursday, September 4, 2008

Chitwan Gupta will be out of town this week.

Turn in Assignment 1 at 8:30 AM today.

Answers.

Tuesday September 9, 2008.

Today, we will cover the remaining branch of the Master Theorem, but not spend much time on it.

We will return to recurrences later in the semester.

Today, we will start discussing sorting.

Thursday, September 11, 2008

We will discuss quicksort in detail.

We will discuss the theoretical lower bound for sorting.

Tuesday, September 16, 2008

Turn in Assignment 2 electronically by midnight tonight.

Thursday, September 18, 2008

Examination today.

Tuesday, September 23, 2008

Today we will discuss arrays, stacks, and queues.

Thursday, September 25, 2008

Today we will discuss implementation of stacks and queues.

Tuesday, September 30, 2008

Today we will discuss binary trees.

Thursday, October 2, 2008

Today we will discuss search structures.

We will show how to find the shortest path in a graph using a queue.

Tuesday, October 7, 2008

Today we will briefly review the method for working Assignment 3.

We will continue our discussion of binary search trees.

Thursday, October 9, 2008

Turn in Assignment 3 electronically by midnight tonight.

Tuesday, November 4, 2008

Today we will discuss Array as an abstract data type.

If time permits, we will go over the linear time algorithm for finding the median.

Thursday, November 6, 2008

Turn in Assignment 4 electronically by midnight tonight.

Thursday, November 13, 2008

Turn in Assignment 5 in class today.

Here is the same assignment in pdf format.

Examination today.

Thursday, December 4, 2008

Turn in Assignment 6 electronically by midnight tonight.

Thursday, December 11, 2008

Final Examination today, 8:00 to 10:00.

Some helpful links on data structures.

The practice final in pdf format.

The practice final in postscript format.