Review Sheet for the Midterm Exam


This review sheet is intended to help you study for the midterm exam. It is not intended to be an exhaustive list of everything we've covered, but it should help you identify the "big ideas". You should also review your lecture notes and the solutions to your homework problems.  The lecture "quizzes" are especially useful in helping you study for the exam.

This take-home exam will be closed-book. However, you may prepare a single 8.5 by 11 sheet handwritten on both sides, and refer to this sheet during the exam.

Study Topics

Foundations of functional programming with Scheme!

Run-time analysis

Logic Programming in Prolog

Object-oriented Programming in Java

Some Practice Problems

  1. Where's Waldo? Write a function (waldo L) that takes in any list, L, at all (arbirarily nested). The function waldo then returns #t if L contains the symbol 'waldo at some level of nesting in L and returns #f otherwise. Here are a couple of examples: 
    2.  > (waldo '(1 (chris (bob waldo)  7) d 10))      
 #t
 > (waldo '(1 2 3 14 (15 16 (17 19)) 20))     
 #f
  2. Writing reduce in Scheme! Recall the the foldr function in Scheme takes as input three arguments: A function f of two variables, a unit (such that (f X unit) => X), and a list L. The foldr function returns the result of repeatedly applying the function f to the elements in L until to reduce them to a single value. For example, 
      Scheme> (foldr (lambda (X, Y) (+ X Y)) 0 '(1, 2, 3, 4))
      10
    You should assume that foldr "associates" (orders operations) like this: 1 + 2 + 3 + 4 = 1 + (2 + (3 + (4 + 0))). (Notice that the 0 at the end is the unit for addition.) Write the foldr function from scratch. That is, your implementation my use Scheme's list notation and recursion, but no built-in functions. Notice that foldr should not be written exclusively to handle addition! It's first argument can be any function of two variables, its second argument is the unit for that function, and its third argument is a list of elements of the type operated on by the given function.

    What is the big-O running time of your code?

  3. Use-it-or-lose-it analysis and Scheme!

    You have been hired by Napquest, a company specializing in finding shortest paths between given cities. (It's called Napquest, because their algorithms tend to be inefficient, causing the users to nap while they wait for the answer!)

    A map is a list of "triplets", where each triplet is a list of the form [City1, City2, Distance]. City1 and City2 are just names of cities (e.g. they might be numbers or strings) and Distance is a positive real number indicating the length of the one-way road from City1 to City2. For example, here is a valid map: [ ["Claremont", "Spamville", 1], ["Spamville", "Claremont", 2], ["Spamville", "Foobarsburg", 2], ["Foobarsburg", "Claremont", 4] ]. Notice that the map may contain cycles and that there may be funny things like a one-way road from Claremont to Spamville which is shorter than the one-way road from Spamville to Claremont.

    Your job is write a program called tour which takes as input two things: The name of the start city, and an entire map. The function returns a boolean that indicates whether there is a path starting in the start city that tours all of the cities (it does not need to return to the start city).  

    The program need not be fast, but it must compute the right answer. For full credit, keep your code very short.  However you may find it easier to write a helper function.

  4. Prolog Write a prolog predicate 
     subseq( L, M )
    that is true when the list L is a subsequence of the list M. The idea is that L is a subsequence of M when M contains all of the elements of L in the same order they appear in L, but perhaps M contains some intervening elements, too. You may assume that L and M are both lists. You will want to use Prolog's nondeterministic programming to your advantage here... . Following are a couple of examples of subseq to clarify its desired behavior: 
    ?- subseq( [1, 2, 3], [0, 1, 5, 3, 2, 4] ).
no.

?- subseq( [1, 2, 3], [0, 1, 5, 3, 2, 4, 3] ).
yes.

  5. The Tree of Java!

    You've been hired by Millisoft, a major software company. Your first job is to write a class called BasicDictionary that supports the dictionary abstract data type operations of insert and find. The insert method takes a reference to an object and inserts it into the dictionary. The dictionary will be implemented as a binary search tree.

    The objects that are being inserted and found are Strings: these can be compared with the compareTo method, which works like "less than" using alphabetical order.

    Your job is to give an implementation of the BasicDictionary class using a binary search tree implementation. Below is the starter code with comments. Just implement the insert method, not the find method. 

    
class BasicDictionary
{
   class TreeNode
   {
     private String data;
     private TreeNode lessChild;
     private TreeNode greaterChild;

     TreeNode(String data)
     {
        this.data = data;
        this.lessChild = null;
        this.greaterChild = null;
     }
   }

   protected TreeNode root;   // Reference to the root of the tree

   BasicDictionary()
   {
     this.root = null;
   }

   public void insert(String data)
   {
        // FILL IN THIS CODE
   }
}
  6. Tree Pruning Now, Millisoft would like you to build a new class called Dictionary that extends the BasicDictionary class and also has a delete method that takes an input an object and deletes it from the tree. You may assume that the object is in the tree. Write the code for Dictionary using inheritance. NOTE: This problem is a tiny bit bigger than what we might ask on an exam, but it's a good practice problem nonetheless!

  7. Objects and References in Java

    Consider the following class definitions.

    class Person
    {
      protected String name;  // data member – protected

      public Person( String name )  { this.name = name; }
      public boolean isAsleep( int hr )  { return 22 < hr || 7 > hr; }
      public String toString()      { return name; }

      public getName()
      {
        return name;
      }
     
      public setName(String newname)
      {
        name = newname;
      }
     
      public void status( int hr )
      {
        if ( this.isAsleep( hr ) )
          System.out.println( "Now offline: " + this );
        else
          System.out.println( "Now online: " + this );
      }

     
    }

    class Student extends Person
    {
      protected int units; // additional data member

      public Student( String name, int units )  {
        super(name);
        this.units = units;
      }

      public boolean isAsleep( int hr ) // override
      { return 2 < hr && 8 > hr; }

      public String toString()
      {
        String result = super.toString();
        return result + " units: " + units;
      }
     
    }

    class Mudder extends Student
    {
      protected String dorm;

      public boolean isAsleep( int hr ) { return false; }

      public Mudder( String name, int units, String dorm )
      {
        super(name, units);
        this.dorm = dorm;


      }

      public String toString()
      {
        String result = super.toString();
        return result + " dorm: " + dorm;
       

      }

     
    } 

    What will the following code print?  Will it produce any errors at compile time or run time?

    public static Person doStuff(Person p)
    {
        Student s = new Student( "Sally", 17 );
        p.setName( s.getName() );
        p = s;
        return p;
    }

    public static void main(String[] args)
    {

        Mudder M = new Mudder( "Chris", 42, "Olin" );
       
        Person P = doStuff( M );

        System.out.println( P );

        System.out.println( M );   

    }