CSE 131 Module 8: ADTs

Exercises

These exercises are part of the asynchronous component of this course. Material is taught and demonstrated, but at times you are asked to complete one of the exercises to help you master the new concepts.

In the repository you are using for this course, look inside the exercises source folder, and you will see assignments organized by name. Before continuing on to the next portion of the asynchronous material, spend some time on the exercise. When you are finished, commit your code so that credit for the exercise can be given.

It is not so important that you get the exercise exactly right. It is important to work through it as best you can before you look at the solution or continue with other work in this module.

Before starting this exercise:
Be sure to update your repository before beginning this assignment, so that you receive any code you need.

Thinking about how to use lists

You do not write code in this exercise. Instead, consider each numbered question below and write down some responses that come to mind. You are at this point quite new to lists, so take your time and try to think of the best responses you can.
To record your work here, create and edit a new Java class ThinkingAboutLists in the exercises8 package of your exercises folder. You can enter the text in comments there.
  1. What are some examples of lists? In the introductory video, I spoke about a list of books that I read this summer and a list of temperature readings. Those might be declared ast List<String> and List<Double>, respectively. The String could repesent the title of each book I read, and the Double could represent each temperature reading.

    Think of possible applications of the other two types of lists covered in the video:

    For each of the above, try to find an example where at least one of the following is true:
  2. Suppose we spin a Roulette wheel some number of times, and we must report the numbers that show on the wheel when it stops. Note that: Thus, we need a List<?>, but what type of element should be in this list?
  3. Can you think of a problem where having List<Boolean> would be useful?
  4. Suppose we have some kind of a List. What kinds of operations might we want to perform on that List?
After completing this exercise:
Commit any files you have changed so that you receive credit for your work!
Before starting this exercise:
Be sure to update your repository before beginning this assignment, so that you receive any code you need.

Use a List<String>

Let's try using the code from the end of the video. If you get stuck, look at the solution video, but only as far as it takes you to get unstuck, then try going forward on your own again.

To get started, open the UsingLists class in the exercises8 package of the exercises folder.

Some important points:

Once you are done, change the implementation from LinkedList to ArrayList, and verify that you see no difference in the program's behavior (this part is not on the video).
After completing this exercise:
Commit any files you have changed so that you receive credit for your work!
Before starting this exercise:
Be sure to update your repository before beginning this assignment, so that you receive any code you need.

Investigating the Set interface

Often in designing or writing software, it helps to use code that others have written. We have done exactly that with the List interface and its LinkedList implementation.

In this exercise you will investigate the Set interface using Javadoc documentation. You will then write code to use the Set interface via its HashSet implementation, and observe what happens with the eating example from the previous exercise.

You will no doubt find some of the documentation confusing, as it refers to concepts we have not studied. Nonetheless, browsing such documentation is commonplace at all levels when searching for code that may be of use as you develop software.

Try to skim over the confusing parts to pick up the essential parts of the documentation:

The methods are listed alphabetically, which does not necessarily cover the most important methods first. Skim to get what you need.
  1. Browse this documentation for the Set interface.
  2. In the documentation, find the list of All Known Implementing Classes. All of these implement the Set interface, but:
  3. Browse the documentation for HashSet, an implementation of the Set interface.
  4. Open the UsingSet class of the exercises8 package in the exercises folder.
After completing this exercise:
Commit any files you have changed so that you receive credit for your work!
Before starting this exercise:
Be sure to update your repository before beginning this assignment, so that you receive any code you need.

Generating hashCode and equals for an object you design

In this exercise, you use eclipse to auto-generate useful parts of a class. Try this on your own, but as you need help, run the solution video only as far as necessary for you to move forward again on your own.
  1. Find and open the Point class in the exercises8 package of the exercises folder.
  2. Based on the comment you see there concerning has-a, declare the instance variables for this class, calling them x and y.
  3. Auto-generate the constructor by choosing Source and then Generate Constructor using Fields….
  4. Choose the fields x and y, and finish to generate the constructor.
    Admire the work eclipse just did for you.
  5. These fields will be immutable, so edit the declarations for x and y and add the final attribute.
    This ensures that the values of x and y can be set only by the constructor.
  6. Now use eclipse to generate the getters for x and y.
    Usually the menu you are presented would also offer to generate setters but eclipse knows the relevant variables are final and cannot be set after construction.
  7. In the main() method, construct and print a Point or two and verify that things look good.
    They should not look so good. When you print a Point, you get an ugly and uninformative String. To get something better, we must override the toString() method.
  8. Use eclipse similarly to generate a simple toString() method.
    This, and the subsequent work below, is accomplished also via the Source menu.
  9. OK we are ready to make a Set of some points. Put the following code in the main method: 
    Set<Point> set = new HashSet<Point>();
set.add(new Point(131, 132));
set.add(new Point(131,132));
System.out.println("Set has " + set);
    • Recalling that sets should have no duplicates, you the output from the above code should show the set having the same point twice.
    • This is because Java is using its built-in notion of equality: are two objects exactly the same object (as in, the same reference in memory)?
    • We need to change this behavior, so read on.
  10. Now let's use eclipse to generate hashCode() and equals(Object other) methods.
    You must pick the attributes (instance variable names) upon which you wish equality to be based.
  11. Rerun your code and make sure that two Point objects with the same coordinates cannot both be contained in the same set.

Further exploration

  1. What happens if hashCode() returns a random integer? Try: 
    public int hashCode() {
   return (int)(Math.random()*100000);
}
    • What behavior do you see in the set?
    • Why do you see that behavior?
    The above code makes hashCode() inconsistent, breaking a portion of the contract concerning object equality.
  2. What happens if hashCode() always returns the same result? Try: 
    public int hashCode() {
   return 0;
}
    • Does this work?
    • What impact does the above hashCode() have on performance?

Now try lists

Go back and change the Set and HashSet of your code to use List and LinkedList, respectively.

  1. You should see duplicates. But that's OK for lists.
  2. Intentionally break KBD>.equals(Object other) by returning false always.
    What aspect of the contract does this break for .equals(Object other)?
  3. What behavior do you see?
    Adding to a list does not consult .equals(Other object), so you should see no difference.
  4. Now ask whether the list .contains(new Point(131,132)).
    Nothing should be found in the list with the broken .equals(Object other).
  5. Revert the code back to its proper hashCode and .equals(Object other).
After completing this exercise:
Commit any files you have changed so that you receive credit for your work!
Before starting this exercise:
Be sure to update your repository before beginning this assignment, so that you receive any code you need.

Implementing a StockHolding object

OK now you are pretty much on your own: As usual, if stuck, consult portions of the solutions video.

The story

A StockHolding object:
has-a
and it needs:
You should generate the above automatically, not by hand!
After completing this exercise:
Commit any files you have changed so that you receive credit for your work!
Before starting this exercise:
Be sure to update your repository before beginning this assignment, so that you receive any code you need.

Applying an interface

Do your work in the exercises8 package of the exercises folder.

The story

Define a PersonalProperty object:
has-a
and it needs:

Your task

After defining the above class, adapt it to implement the Valuable interface: 
public interface Valuable {
   public int getLiquidValue();
}
After completing this exercise:
Commit any files you have changed so that you receive credit for your work!