CSE 373, Spring 2019: HW1 Problems

Summary

Due Wednesday, April 10 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/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/TestLinkedIntListProblems.java
• src/test/java/datastructures/TestIntTreeProblems.java

Note: The following parts are divided up by the file you will edit to complete the homework. The parts don't rely on each other, so you can do the parts in any order. Know that the problems within each section are ordered from probably-easier to probably-more-difficult.

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}

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

Part b.iii: 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] → /

Obey the following restrictions in your solution:

• 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.

Part b.iv: 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.

Obey the following restrictions in your solution:

• 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.
• Your solution should run in linear time with respect to the number of elements of the linked list.

Part b.v: shift

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

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.

Obey the following restrictions in your solution:

• 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.
• Your solution should run in linear time with respect to the number of elements of the linked list.

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

Part b.vi: 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

Obey the following restrictions in your solution:

• 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 use other data structures such as arrays, lists, queues, etc.

Part b.vii: numberNodes

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

Write a method numberNodes that changes the data stored in a binary tree, assigning sequential integers starting with 1 to each node so that a pre-order traversal will produce the numbers in order (1, 2, 3, etc.). For example, given the tree referenced by tree below at left, the call of numberNodes(tree); would overwrite the existing data assigning the nodes values from 1 to 6 so that a pre-order traversal of the tree would produce 1, 2, 3, 4, 5, 6.

You are not to change the structure of the tree. You are simply changing the values stored in the data fields. Your method should return a count of how many nodes were in the tree.

Obey the following restrictions in your solution:

• 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 use other data structures such as arrays, lists, queues, etc.

Part b.viii: 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).

Obey the following restrictions in your solution:

• 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.

Part xi: tighten

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

Write a method tighten that eliminates branch nodes that have only one child. For example, if a variable called tree stores the tree below at left, the call of tighten(tree); should leave tree storing the tree at right:

The nodes that stored the values 8, 9, 6, and 1 have been eliminated because each had one child. When a node is removed, it is replaced by its child. This can lead to multiple replacements because the child might itself be replaced (as in the case of 9 which is replaced by 6 which is replaced by 0).

Obey the following restrictions in your solution:

• 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.

Part x: 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.

Obey the following restrictions in your solution:

• 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.