CIS 114                                                     Summer 2005


                            Homework 4
			    ----------

- General Instructions (GI) for all Homeworks:

SEE HOMEWORK ONE.  ALL INSTRUCTIONS WILL BE ENFORCED.

THIS HOMEWORK IS DUE TUESDAY JUNE 21st AT 6:00 PM.


Q1 (lecture 19)

Isn't it strange that in the linked list implementation of the Queue
we are pointing to the LAST element, instead of the first element?
Explain in two or three sentences why this makes sense.

Q2 (lecture 20)

List all the methods of the Queue ADT.  Only the headers, not the body.
But don't cut and paste them.  Type them yourself.  Make sure you understand
what each one is doing.


Q3 (lecture 21)

This lecture shows a table implementation.  Explain what its advantages
and disadvantages are.


Q4 (lecture 22)

What is

O(25*N + 48)
O(N-square + N)   [square means to the power of 2, of course]
O(N-cube + 5 * N-square)


Q5 (lecture 23)

Sort the following numbers by Selection Sort.
That means:  Show the array after every single step.
Say where you are swapping.

18 14  20  10 6



Q6 (lecture 24)

Sort the following numbers by Bubble Sort.
That means:  Show the array after every single step.
Say where you are swapping.

18 14  20  10 6