Sample questions and things to think about for the impending mid-term:

1) What is a stack?

2) If you implement a stack as an array, how do test to see if
it is full? empty?

3) List three things a stack might be used for.

4) If you implement a stack as a linked-list, how do you test to see
if the stack is empty?

5) Answer questions 1-4 for queues.

6) In Java, what is the difference between runtime 
exceptions and other exceptions?

8) Given the following Java code:

public interface intSummable
{
  public int addEmUp();
}

public class IntCollection
{
  public static final int maxSize = 100;
  protected int data[];
  protected int number;
  
  public IntCollection()
  {
    //constructor
  }

  public void insert(int val)
  {
    //put val into the data if it is not already there,
    //else throw an exception
  }

  public boolean isThere(int val)
  {
    //return true if val is in the data, false otherwise
  }

  public void delete(int val)
  {
    //remove val from the collection
  }

  public int getNum()
  {
    //return the number of items in the collection
  }
}

a) Write the bodies of the member functions
b) Using inheritance, create a subclass called SummableIntCollection
which implements the intSummable interface.

11) Write a recursive and an interative function which accepts as
its parameter a pointer to a linked list and prints the
contents of every element in the list.

12) What is a free tree? What is a rooted tree? What is an ordered tree?
What is a binary tree?

13) In the following fragment of code...

public int findMax(int data[], int size)
{
  int retval = data[0];

  for (int i = 0; i < size; i++)
  {
    if (data[i] > retval)
      retval data[i];
    return retval;
  }
}

What is the invariant of the for loop?

14) Write a recursive function that accepts as a parameter a pointer
to the root node of a tree and traverses the tree in pre-order.
How would you change it to give in-order or post-order.

15) What additional requirement(s) make a binary tree into a binary search
tree?


20) Describe the mergesort algorithm.

21) What possible problems are there with using quicksort
in a time-critical application?


23) Given a binary tree with N nodes, what is the deepest it could
be? The shallowest?

24) A certain O(lgN) process requires 10 seconds to process 1024 items.
How long would it take for it to process 2048 items?
How long would it take for it to process 2048 items?
Answer similar questions of O(N lgN) O(N) O(N*N).

**** New for the second mid-term *****
25) What is the difference between a depth first and a breadth first search?
What do they correspond to if the graph in question is a binary tree?
They can be implemented almost identically by changing one data structure
in the implementation. What data structure?

26) What properties are desirable in a hashing function?
What alternative is there to linear probing to avoid collissions?

27) What is a cirumstance in which an unbalanced tree is a good thing?

28) How can a variable length code for encoding characters produce smaller file sizes?

29) What quantity do we try to minimize when creating a Huffman encoding tree?

30) Give an example of a divide-and-conquer algorithm

31) Give an example of a greedy algorithm.