CSE 373, Summer 2019: Project 0 - CSE 143 review problems

Summary

Due Wednesday, July 3 at 11:59pm.

Submit by pushing your code to GitLab, as described in the final part of the project. If you intend to submit late, fill out this late submission form when you submit.

You will be modifying the following files:

• src/main/java/problems/MapProblems.java
• src/main/java/problems/ArrayProblems.java
• src/main/java/problems/LinkedIntListProblems.java
• src/main/java/problems/IntTreeProblems.java

Additionally, here are a few more files that you might want to review while completing the assignment (note that this is just a starting point, not necessarily an exhaustive list):

Data structures

• src/main/java/datastructures/LinkedIntList.java
• src/main/java/datastructures/IntTree.java

Tests

• src/test/java/datastructures/TestMapProblems.java
• src/test/java/datastructures/TestArrayProblems.java
• src/test/java/datastructures/TestLinkedIntListProblems.java
• src/test/java/datastructures/TestIntTreeProblems.java

Map Problems

Part b.i: contains3

Author: Marty Stepp (on 2016/09/08)

Write a method contains3 that accepts a List of strings as a parameter and returns true if any single string occurs at least 3 times in the 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.

Part b.ii: intersect

Author: Marty Stepp (on 2016/09/08)

Write a method intersect that takes two Maps of strings to integers as parameters and that 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 and values that exist in both maps. So 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:

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

Calling your method on the preceding maps would return the following new map (the order of the key/value pairs does not matter):

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

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.

Part b.iii: toString

Write a method named toString that accepts an int[] as a parameter and returns a String representation of its contents. The String representation of the int[] should begin with "[" and end with "]". Each pair of integers in the String representation should be seperated by a comma and a space.

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

{5, 10, 15}

Then a call of toString should return the String:

"[5, 10, 15]"

On the other hand if the input list was:

{1}

Then a call of toString should return the String:

"[1]"

Part b.iv: reverse

Write a method named reverse that accepts an int[] as a a parameter and returns a new int[] in reverse order.

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

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

The call of reverse(list) should return an array containing the values

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

Part b.v: rotateRight

Author: Marty Stepp (on 2016/09/08)

Write a method named rotateRight that accepts an int[] as a parameter and rotates the values in the array 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 list refers to an array containing the values:

{3, 8, 19, 7}

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

{7, 3, 8, 19}

A subsequent call of rotateRight(list) 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 src/main/java/datastructures/LinkedIntList.java

Obey the following restrictions in your solutions:

• Do not call any other methods on the LinkedIntList object such as size or toString.
• Do not create new ListNode objects (though you may have as many ListNode variables as you like).
• Do not use other data structures such as arrays, lists, queues, etc.
• Do not mutate the data of any existing node; change the list only by modifying links between nodes.
• For firstLast and shift, your solution should run in linear time (O(n)) with respect to the number of elements in the list.

Part b.vi: reverse3

Author: Marty Stepp (on 2016/09/08)

Write the code necessary to change the following LinkedIntList:

front → [5] → [4] → [3] → /

Into this sequence of ListNode objects:

front → [3] → [4] → [5] → /

Part b.vii: firstLast

Author: Marty Stepp (on 2016/09/08)

Write a method firstLast that moves the first element of the list 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 made the call of firstLast(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.

Part b.viii: shift

Author: Whitaker Brand (on 2016/09/08)

import

Write a method shift that rearranges the elements of a LinkedIntList by moving to the end of the list all values that are in odd-numbered positions and otherwise preserving list order. For example, suppose a variable list stores the following values:

front → 0 → 1 → 2 → 3 → 4 → 5 → 6 → 7 → /

The call of shift(list); should rearrange the list to be:

front → 0 → 2 → 4 → 6 → 1 → 3 → 5 → 7 → /

In this example the values in the original list were equal to their positions and there were an even number of elements, but that won't necessarily be the case. For example, if list had instead stored the following:

front → 4 → 17 → 29 → 3 → 8 → 2 → 28 → 5 → 7 → /

Then after the call shift(list); the list would store:

front → 4 → 29 → 8 → 28 → 7 → 17 → 3 → 2 → 5 → /

Notice that it doesn't matter whether the value itself is odd or even. What matters is whether the value appears in an odd index (index 1, 3, 5, etc). Also notice that the original order of the list is otherwise preserved.

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 src/main/java/datastructures/IntTree.java

Obey the following restrictions in your solutions:

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

Update (6/27): the course staff accidentally left in two method stubs from an earlier version of this project. Please just delete the method stubs for the numberNodes and tighten methods.

Part b.ix: depthSum

Author: Robert Baxter (on 2016/09/08)

Write a method depthSum 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 plus 4 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

Part b.x: removeLeaves

Author: Robert Baxter (on 2016/09/08)

Write a method removeLeaves that removes the leaves from a tree. A leaf node that has empty left and right subtrees. If a variable tree refers to the first tree below, the call of removeLeaves(tree); should remove the four leaves from the tree (the nodes with data values 1, 4, 6, and 0) leaving the next tree shown 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).

Part xi: trim

Author: Marty Stepp (on 2016/09/08)

Write a method trim that accepts minimum and maximum integers as parameters 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) and that 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; it's not a chain of calls in a row. 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.