Learning Objectives

This assignment is designed to help you learn about recursive thinking, programming using recursion, and working with different kinds of Collections and other abstract data types.

Overview

As you may have heard, James Madison University has been working hard to give extraterrestrials (including Arcturans, Arquillians, Ballchinians, Boov, Colossi, Daleks, Druidians, Ewoks, Flora, Gorg, Hutts, Krylorians, Kylothians, Mawgs, Oods, Raxacoricofallapatorians, Remoolians, Sontarans, and Wookies) the opportunity to study on campus. However, for a variety of reasons related mostly to their psychologies, many extraterrestrials have a habit of getting lost on campus. So, JMU has created a super-secret group, named People in Purple, that monitors them (with their permission, of course).

Since their physiologies tend to interfere with the operation of both wearable devices and mobile telephones, PIP has purchased a remote sensor from the (fictitious) company Sciontific, that can determine if a particular extraterrestrial is in a given square area (of any size). They have asked you to create an algorithm that can use this sensor to determine a particular extraterrestrial’s location within a small tolerance, and to incorporate it into an application named the Extraterrestrial Locator.

The relationship between all of the components that comprise the Extraterrestrial Locator are illustrated in the following detailed UML class diagram.

Components in purple are part of the Java libraries, components in green were written by the GUI development team, components in orange were written by other developers, and components in black are to be written by you for this assignment. The Point class is in the package java.awt. All of the other classes are in the default package.

Background Information

Before you can start working on the components, you need to learn a little bit about the system.

Acronyms

EL

Extraterrestrial Locator

JMU

James Madison University

PIP

People in Purple

About the JMU Campus

People in Purple wants the system to work with the following area around and including the JMU campus.

JMU Campus

About the Sensor

The sensor that People in Purple has purchased from Sciontific is very sophisticated, but has limitations.

First, though the sensor can determine if a particular extraterrestrial is in any square area, it can’t determine exactly where the extraterrestrial is. Hence, you must design and implement an algorithm that can identify the 1x1 cell that contains the extraterrestrial if it is, in fact, in the campus area. (Note: A particular extraterrestrial can be in at most one 1x1 cell.)

Second, it can only perform 50 scans on a single charge. Hence, since there are 262,144 cells on campus, the algorithm they originally thought they would use to locate an extraterrestrial (i.e., using a nested loop that scans all 262,144 of the 1x1 cells) does not work.

Provided Files

1. pa5.jar
   • this jar includes the Sensor and SensorDisplay classes, but you will not see their source code. You don’t need to interact with the SensorDisplay class yourself. You can find the documentation for the Sensor class below.
   • Remember, you’ll need to add the .jar to the build path: How to import .jar files
2. ExtraterrestrialLocator.java
3. jmu.png
   • you should put this one in the eclipse project folder for your PA5, but unlike the Extraterrestrial.java file, this image should not be in the src folder.

The Existing Class: Sensor

Other programmers at People In Purple have created the Sensor and SensorDisplay classes that interact with the physical sensor and can be used to visualize the results. They are in the provided jar file.

You need only use the Sensor class (the Sensor class uses the SensorDisplay class). The scan() method in this class is passed the square to scan (where x and y are the upper-left corner of the square and width is the width and height of the square). It returns -width if the extraterrestrial is not in the square and width if the extraterrestrial is in the square. The checkSystem() method returns a two-line String that describes the result of the scan. The first line will be "Power constraint satisfied" if 50 or fewer scans were used and will be "Power constraint violated" otherwise. The second line will be "Strongest signal at location" if your ELgorithm found the extraterrestrial at the correct location and will be "No signal" if your ELgorithm does not find the extraterrestrial at the correct location. They have also written the main class.

The main method is passed one required and one optional argument. Argument 0, which is required, is a String containing the name of the extraterrestrial to search for. Argument 1, which is optional, is an integer that controls the amount of time between scans (in milliseconds), which is useful when visualizing the search process. If you want to visualize the results on the aerial photograph of the campus area, you will also need the aerial photo of the JMU campus (see provided files above), which must be in your project directory/folder. When searching for Stitch with a non-zero scan time, the application will look something like the following while it is in the process of searching.

In this visualization, the gray areas are those that did not contain the extraterrestrial of interest, the purple lines are used to delineate the area that is currently being scanned, and the purple square (which flashes briefly), indicates the area that is currently being scanned.

Part 1

The Class to be Written

You must write the ELgorithm class.

The search() method in this class is called by the main() method in the (provided) ExtraterrestrialLocator to initiate a search in the area defined by the parameters 0, 0, 512. Hence, the search() method is responsible for doing the work of locating the extraterrestrial (thought it can, of course, call other methods). This method must return null if the extraterrestrial is not in the area of interest and must return a Point object with the coordinates of the 1x1 cell containing the extraterrestrial if it is in the area of interest.

Submission

You must submit (using Gradescope):

1. Your implementation of the ELgorithm class.
2. You must not submit any other classes; the Sensor class will be available on Gradescope.
3. There is no limit on the number of submissions and no penalty for excessive submissions.

Part 2

1. Write the Area class. In addition to the specs implied by the UML diagram,
   1. override toString to return a String representation of this Area. If this Area had a starting x of 160, a starting y of 192, and a width (and height) of 32, then the String representation would be (note the leading newline):

      
      +-------------------+
      |(160, 192) +  32   |
      |         (192, 224)|
      +-------------------+
      

      • all 5 of the numbers displayed here are inserted into the String with a field width of 3 (padded with spaces when necessary)
      • the commas always have at least 1 space after them regardless of the numbers that follow
      • 3 spaces follow the width before the |
      • 9 spaces precede the opening parenthesis of the ending coordinates
      • See below for examples where some of the numbers do not have 3 digits.

        
        +-------------------+
        |(  0,   0) + 512   |
        |         (512, 512)|
        +-------------------+
        

        
        +-------------------+
        |(256, 320) +  64   |
        |         (320, 384)|
        +-------------------+
        

2. Create a new specialization of the Sensor class, called it LoggingSensor
   1. Its constructor (summarized in the UML diagram) should rely on its base class constructor to initialize most things, but it should also initialize the new instance variable scanLog to a new HashMap.
   2. It should override the scan method to call the base class scan method, and then add the result to the scanLog.
   3. It should override toString to return (only) a String representation of the scanLog.
3. Modify the ExtraterrestrialLocator class to:
   1. use the LoggingSensor class (rather than the regular Sensor)
   2. print the toString of the LoggingSensor after the search is complete.

Submission

You must submit (using Gradescope):

1. Your implementation of these classes:
   1. Area
   2. LoggingSensor
2. You must not submit any other classes; the Sensor class will be available on Gradescope.
3. There is no limit on the number of submissions and no penalty for excessive submissions.

Grading

Your code will first be graded by Gradescope and then by the Professor. The grade you receive from Gradescope is the maximum grade that you can receive on the assignment

Your code must compile, all class names and method signatures must comply with the specifications, and your code must have no style defects for you to receive any points on this assignment. Gradescope will then grade your submission as follows:

Part 1

Correctness (OfficialTests): 75 points (Limited Partial Credit Possible) Given the nature of this assignment, your grade from Gradescope will be either a 0, 37, or 75, and a 37 is fairly unlikely. In other words, your code must be correct for you to receive any points from Gradescope on this part of the assignment.

Part 2

Correctness (OfficialTests): 25 points (Partial Credit Possible)

Manual Grading

After the due date, the Professor may manually review your code. At this time, points may be deducted for inelegant code, inappropriate variable names, bad comments, etc.

Suggestions

You may find the following suggestions helpful.

Allocating Time

Almost all of your time on this assignment should be spent thinking; very little time should be spent typing/compiling/etc. It is very unlikely that you will discover an algorithm that works through trial and error (i.e., try something, compile, test, make a change, repeat).

Getting Started

Before you start thinking about building a full-fledged ELgorithm, you might want to play around a little bit. For example, here’s a ELgorithm that scans the whole area and then scans some cells around I81. (Note: As it turns out, this algorithm will find Omastar.)

import java.awt.Point;
public class ELgorithm {
  private Sensor sensor;
  public ELgorithm(Sensor sensor) {
    this.sensor = sensor;
  }
  public Point search(int x, int y, int width) {
    int resultOfScan;
    Point resultOfSearch;
    resultOfSearch = null;
    // Check the whole area
    resultOfScan = sensor.scan(x, y, width);
    if (resultOfScan < 0) // The extraterrestrial isn't in the area
    {
      resultOfSearch = null;
    }
    else // The extraterrestrial is in the area so let's search some more
    {
      // Try some cells around I81
      for (int xx=300; xx<340; xx++)
      {
        resultOfScan = sensor.scan(xx, 323, 1);
        if (resultOfScan == 1)
        {
          resultOfSearch = new Point(xx, 323);
          break;
        }
      }
    }
    return resultOfSearch;
  }
}

Approach

This assignment will be much easier to complete if your algorithm is recursive. Indeed, it is possible to write a recursive algorithm that contains surprisingly few lines (though your algorithm, like mine, may have more than that). Remember that there are two parts of a recursive algorithm:

1. The part of the algorithm that handles the “easy” (or “base”) case.
2. The part of the algorithm that moves “difficult” cases toward the “easy” case (i.e., the refinement part of the algorithm).

The first thing to think about is how to define the “easy”/“base” case. To do so, suppose your ELgorithm calls the scan() method in the Sensor class. When is its job really easy? (Note: There may be more than one easy case.) The second thing to think about is what you need to do to refine other cases (i.e., take hard cases and move them closer to the easy case).

Testing and Debugging

The visualization of the scanning process can both help and hinder testing and debugging. For your convenience:

• The scan time controls the speed of the visualization. Longer scan times will make it easier for you to see what your ELgorithm is doing, shorter scan times will make the program run faster.
• You can disable the GUI window completely with a scan time of 0.

The following extraterrestrials are known to frequent the JMU campus: Beeblebrox, Chewbacca, Fourarms, Groot, Kang, Neelix, Omastar, and Stitch. In other words, your ELgorithm must find all of these extraterrestrials. You can also test the system using UL, LL, UR and LR (fake extraterrestrials that are at the upper-left, lower-left, upper-right, and lower-right corners). Alf, on the other hand, is never on campus.

Questions to Think About

You don’t have to submit your answers to these questions, but you should try to answer them because they will help you determine whether or not you understand some of the important concepts covered in this assignment.

1. Why weren’t your required to find the exact location of the extraterrestrials (rather than the 1x1 cell containing them)?
2. Could the search() method in the ELgorithm class return an int[] rather than a Point? What is the advantage of returning a Point?
3. Why were square areas used rather than rectangular areas?

Looking Back - The Big Picture

By the time you complete this assignment you should have learned many things, including but not limited to the following “big picture” issues.

• Some problems are much easier to solve using recursion.
• Solving problems using recursion requires a different way of thinking.

Acknowledgements

Thanks to the CS 159 F'22 team (esp. Dr. Bernstein!) for their work in an earlier version of this assignment.

Change Log

Many software projects undergo changes over time. This section documents the changes made to this assignment over time. The most recent changes are listed first (this is called “reverse chronological order”).

1. Added to spec for Area.toString() - 🗓️ 4/26@10:45
2. Corrected spec (and UML) for Area to use ints rather than Point - 🗓️ 4/19@10:00