Computer Science 302
Data Structures
Spring 2005
Assignments

Revised May 20, 2005

Tuesday, January 18, 2005

Today we will broadly discuss the course as a whole.

We will then

Thursday, January 20, 2005 Today, we talk generally about the course.

Tuesday, January 25, 2005

Today, we talk 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 27, 2005

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.

Tuesday, February 1, 2005

Today, I will continue discussing "big O," "big Omega," and "big Theta." I may also introduce "little o."

At the beginning of class, I will prove to you that log(n!) = Theta(n log n). This is needed for the (very important) theorem that any decision model program for sorting n items takes Omega(n log n) comparisons.

We will spend some time analyzing some code fragments, giving answers in terms of O, Omega, and Theta.

Thursday, February 3, 2005

Homework 2 is due today. This is an entirely written homework, to be written in your own handwriting and handed in to me at the beginning of class.

Today I will spend some time going over the answers to Homework 2, and will show you other techniques for analyzing the time complexity of a code fragment.

Remember: the problem of determining the asymtotic time complexity of a code fragement is uncomputable. (This fact will be proved in my CS 456 class.) Thus, no matter how many techniques we learn for analyzing the complexity of a code fragement, there will always be some code fragment that we cannot analyze. We just do the best we can by learning many techniques.

Tuesday, February 8, 2005

Because of the power failure yesterday, it may not be possible to return homeworks that otherwise would have been returned today. (Even though power was restored at 2:30, the system did not come back up until later, and the building had been ordered closed by the Provost, and all the classified staff were sent home.)

We didn't get as far as we should have last Thursday, so we will continue discussion the problem of analyzing code fragments.

Thursday, February 10, 2005

I will return some homework.

We will finish up what was left hanging on analyzing code fragments on Tuesday. I will then introduce some sorting algorithms, and show how to analyze them.

Tuesday, February 15, 2005

Today we will continue our discussion of sorting algorithms.

I will also give hints on how to solve Homework 3.

Thursday, February 17, 2005

Today we will spend most of the time with sorting. I plan to show you a number of sorting algorithms, but not all, as some of them are so complex they require additional material, that we haven't gone over yet, to understand.

The file Homework 3 has been modified to include some more hints, so take another look at it. (The assignment has not been changed.)

Tuesday, February 22, 2005

Today we will continue to discuss sorting.

Our second topic will be additional hints for Thursday's homework. Latest hints added February 22.

Thursday, February 24, 2005

The algorithm given in More hints fails to give the correct convex hull under very special conditions, which you do not expect to occur, and which do not occur in any of the examples I gave you, or any example you are likely to make up, but which may easily occur in practical applications. What are they? How do you modify the algorithm to correct that flaw?

The above question is not trivial. When, in the 1960s, a brand-new radar system for detecting Soviet missles was turned on for the first time, it shortly detected a huge armada of missles coming over the horizon. Strangely, the impact ellipses of the oncoming missles did not appear on the display map. Should they have awakened President Kennedy, who would have to make the awful decision whether to launch a counter-attack? Experts were suspicious for several reasons: 1) The system had just been turned on. 2) The Soviets did not have anywhere near that many missles. 3) No impact ellipses were predicted. 4) Khrushchev, the leader of USSR, was in New York at the time, so he would have been killed, too. 5) There were other (secret) reasons for doubting an attack at that time.
Experts solved the problem in 90 seconds, and did not even awaken the President.
Solution will be given in class. (Hint: The problem was caused by a very common event, known to everyone, that the programmers had not even thought of. Kudos to anyone who figures it out before I give the answer.)

Tuesday, March 1, 2005 Homework 3 is due today. This is another programming assignment. Do not wait until Monday night to start working on it. More hints.

I want to reiterate that you are under no obligation to use the methods that I have explained in class to do this assignment. In fact, I am more impressed with a student who finds his own way of doing the assignment than one who uses methods I present. But, the requirement that your solution take O(n log n) time remains. (Partial credit may be given for a slower program which is correct.)

Thursday, March 3, 2005

Examination today in class.

Tuesday, March 8, 2005

Thursday, March 10, 2005

Diagrams of quicksort and heapsort in postscript form, and in in pdf form.

Today we will start with a quick review of stacks and queues.

We will begin to discuss binary search trees.

Tuesday, March 15, 2005

Today we will start with continue our discussion of binary search trees.

Thursday, March 17, 2005

Today we will continue our discussion of balancing schemes for binary search trees.

Today I will discuss the algorithms that you need to work it.

During the Spring break, I will be in Las Vegas, and available to answer questions by email.

Tuesday, March 29, 2005

Today I will devote most of the lecture to discussion of the programming assignments due next week.

Thursday, March 31, 2005

Today I will devote most of the lecture to continuing discussion of the programming assignments due next week.

Tuesday, April 5, 2005

Homework 4 is due today. This is another programming assignment. Do not wait until Monday night to start working on it. Hints.

Thursday, April 7, 2005

Homework 5 is due today. This is another programming assignment. Do not wait until Monday night to start working on it.

Tuesday, April 12, 2005

Examination today in class. Study guide.

Wednesday, April 13, 2005

The examination is graded. The median score is 105 out of 170. If the three absent students are assigned 0, the median score drops to 100.

Answer to the heapsort question.
Answer to the heapsort question, postscript.
Answer to the heapsort question, pdf.

Thursday, April 14, 2005

Today I will hand back the examination and discuss the problems.

We will then discuss data structures for storing graphs and sparse graphs, directed graphs and sparse directed graphs, and arrays and sparse arrays. In particular, we will discuss array implementations, linked implementations, and search structure implementations of those types.

Tuesday, April 19, 2005

Today we will introduce some additional data structures, including 2-3 trees (and 2-4 trees, 2-5 trees, 3-5 trees, etc.), tries, and B-trees, which implement the ADT search structure.

2-3 trees and their relatives are always balanced. Rather startingly, a trie is really a recursive hash table, where the hash function is a single symbol of the data item. This fact is not generally mentioned. B-trees are a generalization of 2-3 trees.

Question: How do you pronounce "trie"?

We will also discuss Assignment 6 if needed.

Thursday, April 21, 2005

Today we will discuss graphs and graph algorithms, including algorithms for visiting the vertices of a graph, and algorithms for finding shortest paths in a graph.

You might think that a graph would always be represented in a computer by somehow listing the vertices and edges. But this is not always the case. A graph could be virtual, i.e., you compute the vertices and edges on the fly, as needed. What would the graph look like for the well-known puzzle Rush Hour?

Tuesday, April 26, 2005

Today, we will continue or discussion of graph algorithms and their implementation.

If requested, I will devote 15 minutes to discussion of questions involving Homework 6.

Thursday, April 28, 2005

Today, we will continue or discussion of graph algorithms and their implementation. I will explain depth first search, breadth first search, and Dijkstra's algorithm.

If requested, I will devote 15 minutes to discussion of questions involving Homework 6.

Tuesday, May 3, 2005

Sample final, postscript version. Here is a pdf version. This will be the last version, i.e., there will be no more added problems. (But, if there is an error, I hope you'll let me know so I can correct it.)

Thursday, May 5, 2005

Homework 6 is due today.

Thursday (not Tuesday), May 12, 2005

Some people (including me) were unable to access faculty web pages (including this one) for the last 3 days from home. Because this problem was not visible from the Engineering building, the systems administrators thought they had solved it until I alerted them. Now, as of about 6 pm Thursday, May 5, it appears to be fixed. If anything like this should recur, send me email.

Final Examination: 8:00 -- 10:00

Monday, May 16, 2005

Course grades have been assigned.

Monday, May 20, 2005

I submitted the grades electronically to the registrar (this is the first semester that we were required to do this) but it appears that they failed to get into the data base. One of the systems people has promised that this will be fixed tonight. It appears that three CS sections had the same problem, which did not originate in the CS office.