CSc 150
Answers to Midterm Review Questions

public ListNode findInteger(int key)
{
   ListNode runner;
   runner = firstNode;
   if (length==0)
   {
      return null;
   }
   else    
   {
     //I'll use a running pointer to check each node, starting
     //with the node pointed at by firstNode.  But
     //since it's circular, i'm done not when runner=null, but 
     //when runner gets back to firstNode. But runner
     //starts at firstNode, so I need to take care of the 1st
     //node in the chain separately.
     
     if (runner.data == key)
     {
        return runner;
     }
     else
     {  
        runner = runner.next;

        //so now runner points to either the next node (and
        //we'll be done when runner==firstNode again) or, if
        //the linked list only has 1 node in it, runner points
        //at the same node (which is also firstNode, so we're done).
        //So the loop that checks for when runner==firstNode
        //handles both cases.

        //while (all nodes not checked && current node not the key)

        while (runner!=firstNode && runner.data != key)
        {
            runner = runner.next;
        }
     
        //unlike the search method that you wrote in lab, we're not
        //done yet, since if key isn't there, runner isn't null; it's
        //firstNode.  So we need one last check to see why we exited
        //the loop.  If it was becuase we found it (runner.data == key)
        //then just return runner.  But if not, that means key is not
        //there and we should return null.

        if (runner.data == key)
        {
            return runner;
        }
        else  
        {
            return null;
        }
     }  
   }
}

1. Search for the int in the node pointed to by firstNode
2. Search for the int in the node at the "end" of the circle, i.e. the one in the node that points back at firstNode.
3. Search for the int in any other node (not the two nodes above)
4. Search for a non-existent int
5. Search an empty list
6. Search a 1-node list (for the int it contains)

5 + 10 + 15 + ... + 5n =
5 (1 + 2 + 3 + ... + n) =
5n(n+1)/2

The above is the EXACT number of basic ops that are done. (I *would* expect you to be able to derive this.)

The highest term is the n² term, so the running time is O(n²).

public class Ravioli extends Pasta
{
    protected String filling;
	
    public Ravioli(String fill_type)
    {
        // if you set the flour variable yourself here instead of calling super like
        // I do below, you would lose points for poor design.  Why?
        super();
        filling = fill_type;
    }
}

public class MeatRavioli extends Ravioli
{
    public MeatRavioli(String meat_type)
    {
        // You MUST call super here.  Error will result if you don't.  Why?
        super(meat_type);
    }
	
    public MeatRavioli()
    {
        super("beef");
    }
}

public class CheeseRavioli extends Ravioli
{
    public CheeseRavioli(String cheese_type)
    {
        // You MUST call super here.  Error will result if you don't.  Why?
        super(cheese_type);
    }
	
    public CheeseRavioli()
    {
        super("ricotta");
    }
}