Programming

Reviewing CSE 143 data structures and getting familiar with JUnit tests.

Table of contents

1. Array Problems
   1. toString
   2. reverse
   3. rotateRight
2. LinkedIntList problems
   1. reverse3
   2. firstToLast
   3. concatenate
3. IntTree Problems
   1. depthSum
   2. removeLeaves
   3. trim
4. Map Problems
   1. contains3
   2. intersect
5. Running Tests

Reminder

All the graded tests are provided to you in the cse143review.test module; run them to check your progress as you implement parts of the assignment. Review the testing page for more info.

Array Problems

Obey the following restrictions in your solutions:

• Do not add any additional imports.
• Do not create new int[] objects for toString or rotateRight.

toString

Implement a method that returns a String representation of the contents of the input int[]. The String representation of the int[] should begin with “[” and end with “]”. Each pair of integers in the String representation should be separated by a comma and a space.

For example, if a variable named array refers to the array:

{5, 10, 15}

Then toString(array) should return the String:

"[5, 10, 15]"

On the other hand if the input array was:

{1}

Then toString(array) should return the String:

"[1]"

reverse

Implement a method that returns a new int[] containing the input int[]’s elements in reverse order. (The method should not modify the input array.)

For example, if a variable named array refers to an array containing the values:

{1, 2, 3, 4, 5, 6, 7, 8, 9}

The call to reverse(array) should return an array containing the values:

{9, 8, 7, 6, 5, 4, 3, 2, 1}

rotateRight

Implement a method that rotates the values in the input int[] to the right (i.e., forward in position) by one. Each element moves right by one, except the last element, which moves to the front.

For example, if a variable named array refers to an array containing the values:

{3, 8, 19, 7}

The call of rotateRight(array) should modify it to store:

{7, 3, 8, 19}

A subsequent call of rotateRight(array) would leave the array as follows:

{19, 7, 3, 8}

LinkedIntList problems

These problems will involve writing methods that modify a LinkedIntList, taking the list as a parameter and directly modifying its public fields. For these problems, use the ListNode class defined in LinkedIntList.

Obey the following restrictions in your solutions:

• Do not call any methods on the LinkedIntList objects.
• Do not construct new ListNode objects for reverse3 or firstToLast (though you may have as many ListNode variables as you like).
• Do not construct other data structures such as arrays, lists, queues, etc.
• Do not mutate the data of any nodes; instead, change the list only by modifying links between nodes.

reverse3

Implement a method to change the following LinkedIntList (you may assume it has these exact 3 elements):

front → 5 → 4 → 3 → /

Into this sequence of ListNode objects:

front → 3 → 4 → 5 → /

This is intended to be a warm-up to the other LinkedIntList problems, so you don’t need to generalize your solution to work for different lists.

firstToLast

Implement a method that moves the first element of the input LinkedIntList to the back end of the list. Suppose a LinkedIntList variable named list stores the following elements from front (left) to back (right):

front → 18 → 4 → 27 → 9 → 54 → 5 → 63 → /

If you call firstToLast(list), the list would then store the elements in this order:

front → 4 → 27 → 9 → 54 → 5 → 63 → 18 → /

If the list is empty or has just one element, its contents should not be modified.

concatenate

Implement a method which takes two LinkedIntLists as input and returns a new list containing all the items of the first followed by all the items of t he second. Don’t modify the input lists; use the new keyword to create new objects instead.

list1: front → 1 → 2 → 3 → /
list2: front → 4 → 5 → 6 → /

If you made the call concatenate(list1, list2), then it should return a new list:

return: front → 1 → 2 → 3 → 4 → 5 → 6 → /

and list1 and list2 would be unchanged and store their original data:

list1: front → 1 → 2 → 3 → /
list2: front → 4 → 5 → 6 → /

(You should be able to implement this method with linear runtime, i.e., without nested loops iterating through the inputs.)

IntTree Problems

These problems will involve modifying an IntTree, taking the tree as a parameter and directly modifying its public fields. For all these problems, use the IntTreeNode class defined in IntTree.

Obey the following restrictions in your solutions:

• Do not call any methods on the IntTree objects.
• Do not create new IntTreeNode objects (though you may have as many IntTreeNode variables as you like).
• Do not use other data structures such as arrays, lists, queues, etc.
• Do not mutate the data field of any node; instead, change the tree only by modifying links between nodes.

depthSum

Implement a method that returns the sum of the values stored in a binary tree of integers weighted by the depth of each value. You should return the value at the overallRoot, plus 2 times the values stored at the next level of the tree, plus 3 times the values stored at the next level of the tree, and so on. For example, in the tree below:

The sum would be computed as:

1×9 + 2×(7+6) + 3×(3+2+4) + 4×(5+2) = 90

removeLeaves

Implement a method that removes the leaf nodes from an IntTree. (Remember that a leaf node is one that has empty left and right subtrees.) If a variable tree refers to the first tree below, the removeLeaves(tree) should remove the four leaves from the tree (the nodes with data values 1, 4, 6, and 0) leaving the next tree below.

A second call on the method would eliminate the two leaves in this tree (the nodes with data values 3 and 8), shown in the third tree below. A third call would eliminate the one leaf with data value 9, and a fourth call would leave an empty tree because the previous tree was exactly one leaf node. If your method is called on an empty tree, the method does not change the tree because there are no nodes of any kind (leaf or not).

trim

Implement a method that accepts parameters for an IntTree and minimum and maximum integer values, and removes from the tree any elements that are not within that range (inclusive). For this method, you should assume that your tree is a binary search tree (BST), so its elements are in valid BST order. Your method should maintain the BST ordering property of the tree.

For example, suppose a variable of type IntTree called tree stores the following elements:

The table below shows what the state of the tree would be if various trim calls were made. The calls shown are separate; they are not a chain of sequential calls. You may assume that the minimum is less than or equal to the maximum.

Hint

The BST ordering property is important for solving this problem. If a node’s data value is too large or too small to fit within the range, this may also tell you something about whether that node’s left or right subtree elements can be within the range. Taking advantage of such information makes it more feasible to remove the correct nodes.

Map Problems

Each of these methods involves using Java Map objects (even if they don’t show up in the method signature.)

contains3

Implement a method that returns true if any string occurs at least 3 times in the input list, and false otherwise. Use a map as auxiliary storage. For example, consider the following list:

[373", "is", "fun", "HI", "fun", "fun"]

contains3 should return true given this input because “fun” shows up at least 3 times.

intersect

Implement a method that takes as input two maps from Strings to Integers and returns a new map whose contents are the intersection of the two. The intersection of two maps is defined here as the set of keys-value pairs that exist in both maps. If some key K maps to value V in both the first and second map, include it in your result. If K does not exist as a key in both maps, or if K does not map to the same value V in both maps, exclude that pair from your result.

For example, consider the following two maps:

map1: {Janet=87, Logan=62, Whitaker=46, Alyssa=100, Stefanie=80, Jeff=88, Kim=52, Sylvia=95}
map2: {Logan=62, Kim=52, Whitaker=52, Jeff=88, Stefanie=80, Brian=60, Lisa=83, Sylvia=87}

Calling intersect(map1, map2) would return the following new map (the order of the key-value pairs does not matter):

{Logan=62, Stefanie=80, Jeff=88, Kim=52}

Running Tests

Run the provided tests to check your work, as described in the testing page.

For this assignment, the tests on Gradescope are the same tests you can run in IntelliJ. In later assignments, we’ll be emphasizing testing as a skill, so some tests may only be available on Gradescope and you may be limited in the frequency of submissions you can make.

Visit the Commit & Submit page for instructions on saving your work and submitting it for grading.