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.

Please remember that you may use at the exam a 8.5 by 11 sheet of self-made notes.

Study Topics

Now with Prolog!

Functional programming with Racket...

Parsing and Evaluating a Language

Object-oriented Programming in Java

Information structures and data structures

Run-time analysis

Some Practice Problems

These don't hope to span all of the topics we've covered, but they are meant to give a sense of the size and scope of possible exam problems.

  1. Writing foldr in Racket! Recall the the foldr function in Racket 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, 
      Racket> (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 Racket'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.

  2. Use-it-or-lose-it in Racket

    Write a function (closest-sum target L) that takes in a numeric target and a list of numbers L. Then, closest-sum should return the subset of the elements of L whose sum is as close as possible to target.

    For example, 

    (closest-sum 19 '(3 4 7 7 22))
'(4 7 7)
    Ties may be handled arbitrarily... any best answer is OK.


  3. 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
   }
}



  4. Tree Pruning Now, Millisoft would like you to build a new class called Dictionary that extends the BasicDictionary class but 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 bit bigger than what we might ask on an exam, but it's a good practice problem nonetheless!


  5. 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( "Zach", 42, "Olin" );
        Person P = doStuff( M );
        System.out.println( P );
        System.out.println( M );   
    }