CS 112 Fall 2011 -- Homework One

Due Monday, September 19th at 12 Midnight (i.e., 1 minute after 11:59pm on 9/19/11)

Introduction

This homework consists of several programming problems.These will get you up to speed on the course infrastructure and remind you how to write Java code! I suggest you read each problem carefully and think about your solution for a bit before launching Dr. Java and beginning to type. In addition to the requirements for each problem, you must observe the following requirements (for all homework submitted in this course):

Consult the textbook and the Java online documentation as needed.

Problem One: MysterySearch, a.k.a. The 20 Questions Game [20 pts]

We provide you on the class web site with a class MysteryInt that contains a single integer value; you have the ability to test if that value is greater than whatever integer you supply, and no other mechanism to find out what the value is. We also provide you with a class MysterySearchDriver, which contains a single method main that repeatedly reads in an input value, puts it into a MysteryInt, and invokes Guesser.guess method to guess what value that is. If the guess is incorrect, it complains; else it prints ``Ok.'' Your task is to write a class Guesser, containing a single public static method guess (and other, private, static methods if you want), that will use binary search to figure out and return the value of its input MysteryInt. If you do it correctly and run ourMysterySearchDriver, it should never complain. Do not modify the classes we give you. Submit only Guesser.java.

Problem Two: Square Roots using 20 Questions[20 pts]

Write a program that uses binary search to compute a square root (rounded down to the nearest integer) of an input non-negative integer. Your program should read integers from a console and print out their square roots, one per line. It should quit when given a negative input. A sample session of your program should look like this (user input underlined): 

  10
  3
  25
  5
  0
  0
  1025
  32
  -1
Hint: think of the square root that you are looking for as the mystery value from the previous problem. Caution: make sure your search ends up rounding down in case the input is not a square, and gives the correct answer in case the input is a square. Submit a single file Sqrt.java.

Problem Three (A & B): Integer Multiset Abstract Data Type (two parts, 20 pts each)

For this problem you are going to provide implementations for a simple collection, which can be thought of as a Bag (p.121) that supports deletion, or a Set (p.489) that allows duplicate elements; this material will be covered class the week of 9/12. The interface that specifies this ADT is as follows (and may be found in the file IntMultiset.java on the class web site):

public interface IntMultiset {
   void add(int k);            // insert k into multiset--may produce duplicate versions of k
   void delete(int k);         // delete one instance of k--other instances of k may remain
   boolean contains(int k);    // does k occur in the multiset?
   boolean isEmpty();          // is the multiset empty?
   int size();                 // total number of elements in the multiset (including duplicates)
}

You must provide TWO different implementations of this interface:

(A) The first implementation will use an unordered array of 100 integers. Here are some hints for implementing the various methods:

int add(int k): Initialize your array with a "pointer" variable next set to 0; this will be the next location to put a new integer, when adding, simply insert at this location and update next; do not worry about checking for array overflow;

int delete(int k): Scan through the array and find an occurrence of k (if it exists) and then move all elements with higher indices down one; update next;

boolean contains(int k): Scan through the array and return true if you find k and false if you do not;

boolean isEmpty() and int size(): These are simple to implement by examining next.

Submit your code in a file UnorderedIntMultiset.java.

(B) The second implementation will use an ordered array of 100 integers. Here, again, are some hints:

int add(int k): You may implement this using a similar array and next pointer as in (A), but now you must either scan through, or use binary search, to find the location where the new element should be, then move all elements with higher indices over to make room for the new element; again, do not worry about overflow; note that next only serves to mark the end of this, and not the insertion point;

int delete(int k): Similar to in (A), but you may use binary search to find the element if you wish;

boolean contains(int k): Use binary search to find the element (if it exists);

boolean isEmpty() and int size(): Unchanged from (A).

Submit your code in a file OrderedIntMultiset.java.

Follow all the suggestions in the discussion on Java program structure, in particular, making all class members as private as possible. Each of your implementations should work with the client program IntMultisetClient.java (on the class web site), which will access both of your classes and tell you what output is expected.

Problem Four: Analysis (10 pts)

For each of the methods in each of your implementations, give the worst case running time for an array containing N integers. Count the number of times you have to "touch" an integer (e.g., access it or compare or move it -- just count once for each element, i.e., if you compare and then move it, then that counts as one "touch"). Then answer the question "Why do you think we are unconcerned about whether you use binary search or a linear scan in add and delete?" Submit this as a file HW01.Prob04.txt or HW01.Prob04.pdf.

Problem Five: Lab (10 pts)

You will be doing an activity in lab this week which you must hand in as part of this homework; instructions will be given in the lab. Hand this in as a file HW01.Prob05.txt or HW01.Prob05.pdf.