Study Guide for the Demi-Exam.


The demi-exam will be technically oriented and will require you to write short
segments of code as well as analyze code that I provide.  There will also be
a few questions on concepts.

Topics to be covered:

Data structures:
   2D arrays, Priority Heaps, and Hash tables.

Informal complexity analysis of the algorithms.  

Polymorphism and inheritance


What to study:  lecture notes, previous labs, sample programs, handouts, 
	        web links.


---------------------- Sample Questions -----------------------



1.  In an open-hash table, why is it necessary to distinguish between a
    slot that's never been occupied and a cell that's just not currently
    occupied.  Describe a scenario were this distinction would be needed.

2  sketch the priority-heap data structure after inserting in order the
    elements 2 5 1 8 7 3 9.  Sketch a TREE, not an array!

3  sketch the priority-heap after 9 is deleted.


4  What is the time-complexity of inserting n numbers into a heap
    in terms of n?  The heap is initially empty.

5. Write a function to print the ith column of a 2D array, given 
   as an argument:

   public static void printcol(int[][] A, int i)


5  Explain the difference between an abstract class and an interface.


6  What are the types Integer and Double?  How are they different
    from int and double?

7. In the following program, for each line in main, determine
   if the line is valid, causes compiler error, or runtime error.  For
   the valid lines that involves output, determine the output.  Explain
   your answers.

abstract class AA<GT>
{
   public abstract GT f();  // function to return some value of type GT
   public void g()
   {
      System.out.println("AA.g");
   }
}

class B extends AA<Double>
{
   public Double f() 
   { return 3.1415927; }  // conversion of double to Double is implicit
   public void g()   // override superclass method
   { System.out.println("B.g"); } 
   public void h()   // new method
   { System.out.println("B.h"); } 
}

public class aaa
{
    public static void main(String[] argv)
    {
	AA<Double> b = new B();
	b.h();
	((B)b).h();
	b.g();
	((AA<Double>)b).g();  // tricky one
    }
}


7b.  Write a class C that extends AA<String>.  The class can contain
anything as long as it statisfies the requirements of extending AA<String>.

If the following were additional lines in main:

AA<String> c = new C();
Double x = c.f();  

Will this cause a compiler error or a runtime error or no error at all?


... more sample problems may be added later.  Solutions will be posted or
discussed in class.