Lecture 13 - October 8, 2007

Handed back the results of running discrete_Set test programs and discussed good tests missing from some programs

• is setA a subset of setA?
• is setA a proper subset of setA?
• if tested setA - setB, should also test setB - setA
• should show the contents of the sets whose union you are finding AND the contents of the resulting set
• should show the contents of the sets whose intersection you are finding AND the contents of the resulting set
• when testing for set membership, should show the set contents as well as stating the result
• naming sets makes it easier to see what you have done
• programs should have an ending message "This program has ended normally"

We spent time implementing a few of the functions and procedures in the body of the specification

• Syntax check requires that there be a body for each procedure and function
• Every procedure has to have a begin, an end and at least one statement which can be null if procedure has no OUT parameters
• Every function has to return a value of the appropriate type
• You should clearly indicate when what you write is just a STUB

We talked about three different ways of implementing queues (two besides the current one) and what is needed in each

1. If implementing as an array - helpful to have SIZE - requires a lot of movement of data
2. If implementing as a circular array - need a HEAD and a TAIL -
3. If implementing as a linked list - must have a HEAD - having a TAIL shortens the time for insertions

We discussed that after writing the test program for the queue implemented as an array (1 above), that we will be writing other implementations (2, and 3 above) which can be tested by the identical test program. THINK ABOUT THAT!

We discussed that a Queue is a FIFO (first in first out) data structure.

We learned that a Stack is a LIFO (last in first out) data structure.

We listed the sub-programs that a Stack ADT would need

• makeEmpty
• isEmpty
• isFull
• addToStack (colloquially known as push)
• removeFromStack (colloquially known as pop)
• lookAtTheTopOfTheStack (colloquially known as peek)

NOTE: removeFromStack comes in two flavors

• returning the top element when deleting it
• just deleting the top element

We mentioned other data structures that we will learn about

• Heap
• Tree
• Binary Tree
• Every node has no more than two children
• We looked at one with values in it and indicated the order in which we put them into the binary tree
• Binary Search Tree
• A binary search tree consists of a root and a left sub-tree and a right sub-tree - each of which may be empty. All of the elements in the left sub-tree are less than the elements in the root and all of the elements in the right sub-tree are greater than the root. Each sub-tree is itself a binary search tree.
• We built one using the same values in the same order that we used for the binary tree.

Next time:

We will talk about how to declare our own exceptions

We will talk about BIG-O notation