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.
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.
intersect
Author: Marty Stepp (on 2016/09/08)
Write a method intersect
that takes two Map
s 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}
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
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:
LinkedIntList
object such as size
or toString
.ListNode
objects (though you may have as many ListNode
variables as you like).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:
LinkedIntList
object such as size
or toString
.ListNode
objects (though you may have as many ListNode
variables as you like).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:
LinkedIntList
object such as size
or toString
.ListNode
objects (though you may have as many ListNode
variables as you like).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
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:
IntTree
objectIntTreeNode
objects (though you may have as many IntTreeNode
variables as you like).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:
IntTree
objectIntTreeNode
objects (though you may have as many IntTreeNode
variables as you like).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:
IntTree
objectIntTreeNode
objects (though you may have as many IntTreeNode
variables as you like)..left
and .right
and .overallRoot
links between nodes.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:
IntTree
objectIntTreeNode
objects (though you may have as many IntTreeNode
variables as you like)..left
and .right
and .overallRoot
links between nodes.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:
IntTree
objectIntTreeNode
objects (though you may have as many IntTreeNode
variables as you like)..left
and .right
and .overallRoot
links between nodes.