University of Minnesota
Structure of Computer Programming II
index.php

CSCI 1902
Spring Semester 2011
Lab 1
Due: Tuesday, February 22, 2011 at 11:59 PM.
(30 points)

As described in the syllabus, late labs will not be accepted except in cases of documentable and unforseeable emergencies.


This lab is designed to help you gain experience and confidence with basic object-oriented programming in Java. In part one, you will combine your knowledge in recursive programming from CSCI 1901 with Java classes and methods. In part two, you will practice using Java's conditionals and iteratives. In parts three and four, you will explore the roles of methods and static methods in Java classes.

Before you begin to write code, spend significant time in thought as to how you will organize your solutions. Good program structure, abstractions, readability, and re-usability of code are significant components to the grading. The questions are not necessarily in order of difficulty.

As with all work you do during the semester be sure to test your code thoroughly. You should ensure that your code satisfies all requirements. Be sure to implement your code using all class names and method signatures given in the writeup.

You should hardcode your test cases into your programs. Your programs must not ask the user for input.


  1. (6 points) Implement a Java class which uses recursion to efficiently solve the Towers of Hanoi.

    You should not use arrays or for loops to solve this problem.

    The Towers of Hanoi problem consists of three towers (or posts) and a number of discs. Each disc has a hole in its center so that it may be stacked on a tower. In the initial configuration, all discs are stacked on the first tower. The discs are all of different diameters - in the initial configuration, the largest disc is stacked at the bottom of the first tower, with progressively smaller discs stacked on top of it.

    The problem is to move the entire stack of discs from one tower to another tower.

    The following restrictions apply:

    • Only one disc may be moved at a time.

    • Only the top disc of any tower may be moved.

    • No disc may be placed on top of a smaller disc.

    You will need to turn in a Java class called Towers.java. The class should have the following public constructor and method:

    • A constructor which takes an int as an parameter. The int specifies the number of discs to be used.

    • public void solve(int startingTower, int destinationTower)

      Valid values for startingTower and destinationTower are 1, 2, and 3. When solve() is called, your program should print out the moves required to move the specified number of discs from the startingTower to the endingTower.

      Moves should be printed to standard out exactly in the following format:

      Moving disc 1 from tower 1 to tower 2
      Moving disc 2 from tower 1 to tower 3
      Moving disc 1 from tower 2 to tower 3

    Inside your Towers class, also write a main() method that will test the methods of your Towers class.

    As you think about the implementation of Towers, consider that the number of discs in the problem is passed to the Towers constructor, so it is set at the construction of a Towers object. solve() has access to the number of discs as a class instance attribute. But, solve() does not have a parameter corresponding to the number of discs. The general recursive approach to solving this puzzle for an n-disk problem, is to first move n-1 disks from the start to an intermediate tower (the one that is not the start or destination), then move the nth disk from start to destination, and finally move the n-1 disks from the intermediate tower to the destination. A suggestion is to create a new instance of Towers for each value of n. So, in a three disk puzzle, Towers will have three instances--one corresponding to the main puzzle (n=3) and one for each of the recursive cases (n=2 and n=1).

    Also, note that solve() has start and destination parameters, but it does NOT have a parameter to indicate the tower to be used for the intermediate (or temporary) tower. This is different from many common solutions. The lack of an explicit intermediate tower parameter on the solve() procedure requires you to write code to determine which tower (1, 2, 3) should be used as the intermediate by examining the start and destination tower numbers and choosing the only unused tower number for the intermediate.

    Simple test cases are available:

    TowersTester.java and expected results


    NOTE: For fun and as a helpful tool, a Java application to help you visualize the results of your Towers of Hanoi class is available to you. To use it:

    • Save the results of your Towers problem as a text file (ex moves.txt). The file must be in the format:

      Moving disc 1 from tower 1 to tower 2
      Moving disc 2 from tower 1 to tower 3
      Moving disc 1 from tower 2 to tower 3

    • Download TowerViewer.class

    • Run: java TowerViewer moves.txt

    • NOTE: You have likely included more than one test case in the main() method in your Towers.java. However, TowerViewer expects that the text file you supply (ex moves.txt) includes only one test case. This means that if you (for example) test your Towers class with 3 discs, and then again with 7 discs, you should save the results of each test case in a separate text file (ex moves3.txt and moves7.txt). Those text file can then be separately viewed using TowerViewer (java TowerViewer moves3.txt) (java TowerViewer moves7.txt)




  2. (9 points) Implement a Java class which represents Roman numerals.

    The class must be able to convert integer values in the range of 1 to 2500 (inclusive) to their equivalent Roman numeral representation. (There is no 0 in Roman numerals.) You will need to handle 0, negative numbers, and numbers over 2500 as error cases.

    You will need to turn in a Java class called RomanNumeral.java. The class should have the following public static class variables and public methods:

    • public static int MAX_VALUE
      Maximum value which the RomanNumeral class can represent.

    • public static int MIN_VALUE
      Minimum value which the RomanNumeral class can represent.

    • public static String UNDEFINED
      An error message that you will define. This message will be returned by the toString() method if the Roman numeral representation is not defined.

    • public RomanNumeral(int integerValue)

    • public String toString()
      Return the Roman numeral representation of the integerValue which was passed to the constructor.
      If the Roman numeral representation is not defined, return the value of the static variable UNDEFINED

    • public int toInt()
      Return the integer representation of this Roman numeral.

    • public int compareTo(RomanNumeral r)
      Return -1 if this object is less than RomanNumeral r.
      Return 0 if this object and RomanNumeral r have the same value.
      Return 1 if this object is greater than RomanNumeral r.

    Then, inside your RomanNumeral class, write a main() method that will test the methods of your RomanNumeral class. You will probably want the most test cases for this of any of the programs in this assignment.

    Some basic Roman numeral equivalents appear in the tables below (note that certain numbers use a "subtractor value" in front of another symbol as shown in the second table.) There is a general rule that no more then three of the same symbols can appear in sequence in a Roman numeral. So, that forces numbers such as 9 to be represented as IX rather than VIIII. There may be some other possible ambiguities, so state any assumptions you make.

    Number Roman Number Roman
    1 I 4 IV
    5 V 9 IX
    10 X 40 XL
    50 L 90 XC
    100 C 400 CD
    500 D 900 CM
    1000 M    

    Please use the following convention when forming large Roman numerals.

    A subtractor (such as IV, IX, XC, XL, CM) is restricted to the designator that represents the even power of ten just under the designator that it subtracts from.

    So, while CM is fine because C (100) is one power of 10 under M (1000), neither XM nor IM can be used because they are respectively 2 and 3 powers of ten under the M designator. LM and VL are also eliminated because L and V are not powers of 10.

    Similarly, using D (500), CD is used to represent 400, but neither XD nor ID can be used because X and I are more than one even power of 10 under the D designator.

    Some further legal examples:

    Number Roman
    94 XCIV
    277 CCLXXVII
    496 CDXCVI
    899 DCCCXCIX
    999 CMXCIX


    Simple test cases are available:

    RomanTester.java and expected results




  3. a. (3 points) Write a boolean static method called isPrime(int), which returns true when the integer argument supplied is a prime number, and false otherwise. Note that prime numbers are all >1, so 1 is not considered prime, nor is 0 or any negative number considered prime. Test your code with a main method, and show your testing.

    Turn in a file called PrimeTester.java that implements the requirements in part a.

    b. (4 points) Write an instantiable class called "Prime" that contains the following methods:

    • int getPrime() - returns the prime number following the previously returned prime; 2 is returned upon first call.
    • void reset() - resets Prime to return 2 the next time getPrime() is called.
    • void reset(int) - resets Prime to return the smallest prime number >= the int supplied, upon the next call to getPrime().

    Implementation Questions - Should the method isPrime() from part (a) above be included in the Prime class? If yes, public or private, static or non-static? If no, why not, and where should it be included? Rather than answer these questions directly here, have your code and comments show your answers.

    You will need to turn in a file called Prime.java that implements the code requirements in part b including the answers to the implementation questions.

    c. (2 points) Write an application that prints the *sum* of the first n prime numbers for several interesting values of n. (Choose the value of "several" wisely.) Utilize class Prime from part (b) above. For example, if you pass it 10, then you expect the sum to be 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 = 129.

    Turn in a file called PrimeApp.java that implements the requirements in part c.

    d. (1 point) Create a PrimeDemo.java file that contains a main() method that shows the use of two co-existing, yet independent, instances of the Prime.java class, each producing separate streams of prime numbers.





  4. (5 points) The design on this one (what methods, constructors) is up to you. Write an INSTANTIABLE MostDivisors class that will find the integer between 1 and some number n that has the largest number of divisors.  Your class should be able to output the number it finds and all of the divisors it was found to have.

    Then, inside your MostDivisors class, write a main() method that will test the methods of your MostDivisors class.

    You will also need to turn in a file called MostDivisors.java that implements these requirements.


What to turn in

Create a new directory called lab1.

Put all of your .java files from the above questions into the lab1 directory. (If you are using eclipse, you will need to first export your Java files. You can do this by going to the File menu and selecting Export... and then following the dialog to export all of your relevant Java files.)

Also, put a file called README.txt file into the lab1 directory. Please name your file README.txt exactly, with the same case and spelling. The README.txt file should list the name(s), full email address(es), section number(s), and student ID number(s) of the student or students who did this assignment.

Create an archive file of your lab1 directory. The archive file must be called either lab1.zip or lab1.tar.gz

You may make your archive on a home computer or on an ITLabs computer. To make the archive on an ITLabs computer, put your files in a directory called lab1, go out of that folder and type:

tar cvzf lab1.tar.gz lab1

Using the Submit tool, turn in a single archive called either lab1.zip or lab1.tar.gz. You may use the online ITLabs submit tool or the command-line ITLabs submit tool

If you have questions about the assignment, the submission format, or the due date, please contact one of the TAs as soon as possible. The TAs are available via email and at office hours. If you need help and none of the office hours work for you, contact a TA or Professor Dovolis to arrange an appointment outside office hours.