Homework 0B: Data Structures

Assignment Setup

Please follow the Assignment Workflow Guide to get started with this assignment. This assignment is hw0b.

Language Constructs

Types

Java is a statically typed language, which means that every variable has a type that is known at compile time, meaning you must specify it in your code. In contrast, Python is a dynamically typed language, which means that the type of variables are generally only known at runtime, meaning you do not need to specify them in your code.

In Java, there are two kinds of types: primitive types and reference types. Primitive types are lowercase, and we named the ones that we care about in Part A: boolean, int, char, double. Pretty much every other type is a reference type, such as String. If a type starts with a capital letter, it is likely a reference type.

You will learn more about the distinction between primitive and reference types in Lecture 4, but for this homework, you will need to know that each primitive has a corresponding reference type (Boolean, Integer, Character, Double). If you are using “generics” to declare a data structure, you must use the reference type. You can (usually) seamlessly convert between a primitive type and its reference type.

null

Java also has null, which is the approximate equivalent of None in Python. Any reference type can be assigned a value of null. If we try to access an instance member or call an instance method from a value of null, we will see an error called a NullPointerException.

Arrays (fixed-size)

Java arrays are a lot like Python lists. However, Java arrays are fixed-size, so we can’t add or remove elements (that is, no append, remove, etc.).

zeroedLst = [0, 0, 0]
lst = [4, 7, 10]
lst[0] = 5
print(lst[0])
print(lst)
print(len(lst))

int[] zeroedArray = new int[3];
int[] array = {4, 7, 10};
array[0] = 5;
System.out.println(array[0]);
System.out.println(Arrays.toString(array));
System.out.println(array.length);

• In new int[3], the int is the type in the array; and 3 is the length. With this syntax, all elements take on their “default value”. For int, this is 0.
• Arrays do not print nicely, for reasons beyond the scope of HW 0. To print an array, you can call Arrays.toString(array).
• Arrays do not have a length method. It is an instance variable, so it does not have parentheses.
• Java does not support negative indexing or slicing.

Foreach Loop / Enhanced For Loop

lst = [1, 2, 3]
for i in lst:
    print(i)

int[] array = {1, 2, 3};
for (int i : array) {
    System.out.println(i);
}

• Notice the type declaration of the iterating variable, as well as the usage of : instead of in.
• We can also use this syntax on certain other types, such as Lists and Sets.

Lists (resizable)

lst = []
lst.append("zero")
lst.append("one")
lst[0] = "zed"
print(l[0])
print(len(l))
if "one" in lst:
    print("one in lst")

for elem in lst:
    print(elem)

List<String> lst = new ArrayList<>();
lst.add("zero");
lst.add("one");
lst.set(0, "zed");
System.out.println(lst.get(0));
System.out.println(lst.size());
if (lst.contains("one")) {
    System.out.println("one in lst");
}
for (String elem : lst) {
    System.out.println(elem);
}

• Java has the List interface. We largely use the ArrayList implementation.
• The List interface is parameterized by the type it holds, using the angle brackets < and >.
• Lists, again, do not support slicing or negative indexing.

Sets

s = set()
s.add(1)
s.add(1)
s.add(2)
s.remove(2)
print(len(s))
if 1 in s:
    print("1 in s")

for elem in s:
    print(elem)

Set<Integer> set = new HashSet<>();
set.add(1);
set.add(1);
set.add(2);
set.remove(2);
System.out.println(set.size());
if (set.contains(1)) {
    System.out.println("1 in set");
}
for (int elem : set) {
    System.out.println(elem);
}

• Java has the Set interface. There are two main implementations: TreeSet, and HashSet. TreeSet keeps its elements in “sorted” order, and is fast. In contrast, HashSet does not have a defined “order”, but is (usually) really fast.
  • We will formalize these notions of “fast” later on in the course when we learn about asymptotic analysis.
• A Set cannot contain duplicate items. If we try to add an item already in the set, nothing happens.

Dictionaries / Maps

d = {}
d["hello"] = "hi"
d["hello"] = "goodbye"
print(d["hello"])
print(len(d))
if "hello" in d:
    print("\"hello\" in d")

for key in d.keys():
    print(key)

Map<String, String> map = new HashMap<>();
map.put("hello", "hi");
map.put("hello", "goodbye");
System.out.println(map.get("hello"));
System.out.println(map.size());
if (map.containsKey("hello")) {
    System.out.println("\"hello\" in map");
}
for (String key : map.keySet()) {
    System.out.println(key);
}

• Java has the Map interface. There are two main implementations: TreeMap, and HashMap. Similarly to sets, TreeMap keeps its keys sorted and is fast; HashMap has no defined order and is (usually) really fast.
• A Map cannot contain duplicate keys. If we try to add a key already in the map, the value is overwritten.
• In the angle brackets, we have the “key type” first, followed by the “value type”.
• Maps cannot directly be used with the : for loop. Typically, we call keySet to iterate over a set of the keys, and use those to retrieve the values. One may also iterate over the entrySet to get both the keys and values.

Classes

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def distanceTo(self, other):
        return math.sqrt(
            (self.x - other.x) ** 2 +
            (self.y - other.y) ** 2
        )

    def translate(self, dx, dy):
        self.x += dx
        self.y += dy

public class Point {
    public int x;
    public int y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public Point() {
        this(0, 0);
    }
    public double distanceTo(Point other) {
        return Math.sqrt(
            Math.pow(this.x - other.x, 2) +
            Math.pow(this.y - other.y, 2)
        )
    }
    public void translate(int dx, int dy) {
        this.x += dx;
        this.y += dy;
    }
}

We can use these classes as follows:

p1 = Point(5, 9)
p2 = Point(-3, 3)
print(f"Point 1: ({p1.x}, {p1.y})")
print("Distance:", p1.distanceTo(p2))
p1.translate(2, 2)
print(f"Point 1: ({p1.x}, {p1.y})")

Point p1 = new Point(5, 9);
Point p2 = new Point(-3, 3);
System.out.println("Point 1: ( " + p1.x
    + ", " + p1.y + ")");
System.out.println("Distance: "
    + p1.distanceTo(p2));
p1.translate(2, 2);
System.out.println("Point 1: ( " + p1.x
    + ", " + p1.y + ")");

Main

Java programs may also have a special method called main. When you execute a program, the main method is called. The main method runs whatever code is inside, which may call other methods defined within the program.

We define the main method with the signature public static void main(String[] args). You will learn the meaning of each part of this signature later in the class. For now, you can treat main as a “play button” for the code you have written.

To run the code in the previous example, we may create a main method in the Point class like this:

class Point:

    # other methods...
    # end of Point class

if __name__ == '__main__':
    p1 = Point(5, 9)
    p2 = Point(-3, 3)
    print(f"Point 1: ({p1.x}, {p1.y})")
    print("Distance:", p1.distanceTo(p2))
    p1.translate(2, 2)
    print(f"Point 1: ({p1.x}, {p1.y})")

public class Point {

    // other methods...

    public static void main(String[] args) {
        Point p1 = new Point(5, 9);
        Point p2 = new Point(-3, 3);
        System.out.println("Point 1: ( " + p1.x
            + ", " + p1.y + ")");
        System.out.println("Distance: "
            + p1.distanceTo(p2));
        p1.translate(2, 2);
        System.out.println("Point 1: ( " + p1.x
            + ", " + p1.y + ")");
    }

    // end of Point class
}

Notice that in Java, the main method is defined within a class.

If you are coding in IntelliJ, you can actually “play” the main method! IntelliJ will display a green play button to the left of the main method’s signature. Click it to run the code inside.

Programs

Let’s look at some Java programs that use data structures and classes. Here are some simple ones that you might find yourself referring to if you forget how to do something.

Index of Minimum of a List of Numbers

def min_index(numbers):
    # Assume len(numbers) >= 1
    m = numbers[0]
    idx = 0
    for i in range(len(numbers)):
        if numbers[i] < m:
            m = numbers[i]
            idx = i
    return idx

public static int minIndex(int[] numbers) {
    // Assume numbers.length >= 1
    int m = numbers[0];
    int idx = 0;
    for (int i = 0; i < numbers.length; i++) {
        if (numbers[i] < m) {
            m = numbers[i];
            idx = i;
        }
    }
    return idx;
}

Exceptions

Lastly, let’s look at how we can throw exceptions in Java compared to Python with previous example.

def minIndex(numbers):
    if len(numbers) == 0:
        raise Exception("There are no elements in the list!")
    m = numbers[0]
    idx = 0

    ...

    return m

public static int minIndex(int[] numbers) {
    if (numbers.length == 0) {
        throw new Exception("There are no elements in the array!");
    }
    int m = numbers[0];
    int idx = 0;

    ...

    return m;
}

Programming Exercises

In order to get you more familiar with Java syntax and testing, there are a few exercises for you to solve! After you complete the functions, we have provided a handful of tests for you. Although we have provided tests, you are welcome to write your own too! Writing tests is not only crucial for this class but it is one of the most important skills to have in general. It reinforces our understanding of what specific methods are supposed to do and allows us to catch edge cases! You will have more exercises for testing later on in the course but we want you to be exposed early on.

Please complete Lab 01 prior and refer here how to start with the assignment.

While completing the assignment, you may need to use different data structures like ArrayList and TreeMap. In order to import these classes, if you hover over wherever you are using the data structures, IntelliJ will give you option to import it or you can do it manually by adding:

import java.util.ArrayList;
import java.util.TreeMap;

Task 1: JavaExercises

JavaExercises.java has 4 different methods for you to complete:

• makeDice: This method takes returns a new array of integers [1, 2, 3, 4, 5, 6].
• takeOrder: This method takes in a String and returns a new array containing the orders of the customer. If the customer is Ergun, you should return an array of Strings ["beyti", "pizza", "hamburger", "tea"] in that order. If the customer is Erik, you should return an array of Strings ["sushi", "pasta", "avocado", "coffee"]. In any other case, return an empty String array of size 3.

  NOTE: == behaves strangely with Strings for reasons we’ll see later in the course. You should check strings s1 and s2 for equality using s1.equals(s2) in Java.

• findMinMax: This method takes an int[] array and returns the the positive difference between the maximum element and minimum element of the given array. You may assume the input array is nonempty.
• hailstone: This method takes an int n as input and returns its hailstone sequence as a list of integers. The hailstone sequence is defined by the following procedure: pick a positive integer n as the start. If n is even, divide n by 2. If n is odd, multiply n by 3 and add 1. Continue this process until n is 1.
  • You should compute this using recursion with the provided helper method hailstoneHelper.

For this part, you can import List and ArrayList.

Task 2: ListExercises

ListExercises.java has 4 different methods for you to complete:

• sum: This method takes a list List<Integer> L and returns the total sum of the elements in that list. If the list is empty, the method should return 0.
• evens: This method takes a list List<Integer> L and returns a new list containing the even numbers of the given list. If there are no even elements, it should return an empty list.
• common: This method takes two lists List<Integer> L1, List<Integer> L2 and returns a new list containing the items present in both of the two given lists. If there are no common items, it should return an empty list.
• countOccurrencesOfC: This method takes a list and a character List<String> words, char c and returns the number of occurrences of the given character in a list of strings. If the character does not occur in any of the words, it should return 0.

For this part, you can import ArrayList.

Task 3: MapExercises

MapExercises.java has 3 different methods for you to complete:

• letterToNum: This method returns a map from every lower case letter to the number corresponding to its ordering in the alphabet, where ‘a’ corresponds to 1 and ‘z’ corresponds to 26.
• squares: This method takes a list List<Integer> nums and returns a map from the integers in the list to their squares. If the given list is empty, it should return an empty map.
• countWords: This method takes a list List<String> words and returns a map from words in the list to the number of times they appear. If the given list is empty, it should return an empty map.

For this part, you can import TreeMap.

Task 4: Dessert.java

Compared to your previous classes, 61B may leave a lot of wiggle room for you on assignments. For example, there’s no skeleton code for this exercise - don’t be alarmed!

Create a class called Dessert (you’ll need to create a new file and add it to Git) inside of the src/ folder. This class should have the following characteristics:

• Two instance variables: int flavor and int price.
• A constructor that takes two parameters int flavor and int price and sets the instance variables accordingly.
• One static variable int numDesserts that keeps track of the number of desserts created so far.
• A method public void printDessert() that prints the flavor and price of the dessert, along with the total number of desserts created so far, separated by a space.
  • For example, if we create a dessert with flavor 1 and price 2, and then call its printDessert() method, it should print 1 2 1.
  • If we then create a dessert with flavor 3 and price 4, and then call its printDessert() method, it should print 3 4 2.
• Lastly, a method public static void main(String[] args) that only prints the line I love dessert! when executed.

Be sure to implement the above behavior exactly, otherwise you may not pass the tests!

When you have completed Dessert.java, uncomment the appropriate lines in tests/DessertTest and run the test.

class Dessert:
    numDesserts = 0

    def __init__(self, flavor, price):
        self.flavor = flavor
        self.price = price
        Dessert.numDesserts += 1

    def printDessert(self):
        print(self.flavor, self.price, Dessert.numDesserts)

if __name__ == "__main__":
    print("I love dessert!")

Testing and Debugging

If you’re having trouble running your code, please read through the common errors in this section before asking course staff!

Syntax Errors

IntelliJ will not run your code (the green play button will not appear) if your code contains syntax errors.

If your code has syntax errors, you will see a red exclamation point in the top-right corner, and there will be red squiggles in your code. To see where the syntax errors are, you can click on the red exclamation point.

If you are seeing syntax errors in parts of the code that you haven’t modified yet, you may have a syntax error earlier in the code (e.g. mismatched brackets), which is causing later parts of the code to not compile.

For example, in the image above, the takeOrder method is missing its closing bracket on Line 19. This causes a syntax error on Line 23.

Deliverables

• JavaExercises.java
• ListExercises.java
• MapExercises.java
• Dessert.java

For this assignment, you need to complete the methods in JavaExercises, ListExercises, and MapExercises. You also need to create a new file Dessert.java and implement it according to the desired specifications. Make sure you test your code before submitting to Gradescope. Although we do not have a submission limit for this specific assignment, in the future it is encouraged to use existing tests and write your own tests to see if your methods work before submitting your code to the autograder, as there may be limited submissions.

This assignment is 10 points and due 1/22, 11:59 PM.