Assignment 4 Best Path

CIS 313, Intermediate Data Structures Programming Assignment 4

0 Instructions
Submit your work through Canvas. You should submit a tar file containing all source files and a README
for running your project. Don’t submit any other files (e.g., test case or pyc files).
More precisely, submit on Canvas a tar file named lastname.tar (where lastname is your last name) that
contains:
• All source files. You can choose any language that builds and runs on ix-dev.
• A file named README that contains your name and the exact commands for building and running
your project on ix-dev. If the commands you provide don’t work on ix-dev, then your project can’t be
graded and there will be a significant penalty.
Here is an example of what to submit:
hampton.tar
README
my class1.py
my class2.py
my class3.py
problem.py
another problem.py
...
README
Andrew Hampton
Problem 1: python problem1.py <input_filename
Problem 1: python problem1.py <input_filename
...
Note that Canvas might change the name of the file that you submit to something like lastname-N.tar. This
is totally fine!
1
The grading for the project will be roughly as follows:
Task Points
Problem 1 10
pass given sample test case 3
pass small grading test case 3
pass large grading test case 4
Problem 2 10
pass given sample test case 3
pass small grading test case 3
pass large grading test case 4
Problem 3 30
pass given sample test case 10
pass small grading test case 10
pass large grading test case 10
TOTAL 50
2
1 Applications
Problem 1. Best Path
Add a method to your BST class that calculates the value of the best path from the root to a leaf node. We
define the best path to be the path with the highest occurrence of the digit 5. Consider the tree:
40
5 55
25
15 33
4
-5
This tree has a total of four paths from root to leaf:
40 – 5 – 4 – -5: this path has 2 occurrences of the digit 5
40 – 5 – 25 – 15: this path has 3 occurrences of the digit 5
40 – 5 – 25 – 33: this path has 2 occurrences of the digit 5
40 – 55: this path has 2 occurrences of the digit 5
Therefore, the path 40 – 5 – 25 – 15 is the best path and its value is 3. Your new method must calculate the
value of the best path in the tree:
best path value(): Returns the value of the best path. O(n)
Write a driver program that takes a single command-line argument, which will be a filename. The input file
will contain instructions for tree operations. The first line of the input file will be an integer 0 ≤ N ≤ 106
giving the number of instructions. Following will be N lines, each containing an instruction. The possible
instructions are:
insert K, where −105 ≤ K ≤ 105
is an integer: insert a node with key K into the tree. There is no output.
remove K, where −105 ≤ K ≤ 105
is an integer: remove a node with key K from the tree. If such a node
exists, there is no output. If no such node exists, output TreeError.
bpv: output the best path value. If the tree is empty, output TreeError.
Hint: in Python, to count the number of occurences of the digit 5 in an integer x, try str(x).count(‘5’).
Example input file:
11
insert 40
insert 5
insert 4
insert -5
insert 25
insert 15
insert 33
insert 55
bpv
3
remove 15
bpv
Example output:
3
2
4
Problem 2. Syntax Tree
Extracting meaning from a sequence of symbols is a challenging task! Think about how difficult it is to
learn a new language. Fortunately, formal languages like those found in programming and mathematics are
designed with more structure than natural language. In this problem, we will build and analyze a syntax
tree for basic arithmetic expressions.
Consider the arithmetic expression 2 + 3. We can represent it as a syntax tree like this:
+
2 3
For simple expressions like this, the syntax tree doesn’t help much. But consider the more complicated
expression 4 ∗ 2 + 3. The correct order of operations is clear from the syntax tree:
+
* 3
4 2
To evaluate an arithmetic expression, we find the equivalent value using the usual mathematical order of
operations. The expression 2 + 3 evaluates to 5. The expression 4 ∗ 2 + 3 evaluates to 11.
We say that the expression is fully parenthesized if parentheses are used to make the order of operations
unambiguous. The fully parenthesized version of 2 + 3 is (2 + 3). The fully parenthesized version of 4 ∗ 2 + 3
is ((4 ∗ 2) + 3).
For this problem, you will evaluate a syntax tree representing an arithmetic expression. Your program should
take a single command-line argument, which will be a filename. The input file will contain exactly two lines.
The first line of the input file will be an integer 0 ≤ N ≤ 105 giving the number of nodes in the syntax
tree. The second line will be a space-separated array representation of the syntax tree (using the standard
representation from the textbook, where the array is one-indexed and the element at position i represents
the node with children at positions 2i and 2i + 1).
The syntax tree can contain integers −103 ≤ X ≤ 103
, as well as the symbols +, −, and ∗.
You need to output two things. First, a fully parenthesized mathematical expression. Second, a single
integer, the result of evaluating the syntax tree. This output should be separated by a newline. See sample
output below.
The input tree will always represent valid mathematical syntax.
The runtime should be linear in the number of nodes.
Hint: read the input and construct a binary tree. To evaluate the expression, perform a post-order traversal.
To create the fully parenthesized expression, consider an in-order traversal.
Getting started: code (problem2 starter.py) is provided for building a syntax tree from the input list. Read
this code to understand what it’s doing (a preorder traversal) and incorporate it into your solution if you
want. This is a common use case for the preorder traversal.
5
Example input 1:
5
+ * 3 4 2
Example output 1:
((4*2)+3)
11
This input file represents the syntax tree shown above.
Example input 2:
7
* + - 1 2 3 4
Example output 2:
((1+2)*(3-4))
-3
This input file represents the following syntax tree:
*
-
3 4
+
1 2
6
2 Implementation
Problem 3. Red-Black Tree
For this problem, you will implement a red-black tree with integer keys. Do not use any builtin tree structures
that your language might have. Since you have already implemented a binary search tree, you should augment that structure such that it satisfies the red-black properties as described in Chapter 13 of the textbook.
Your data structure should implement the same methods as the BST from Project 3. The only difference
(but it is a big difference!) is that any method in the BST that had runtime complexity O(h) must in the
red-black tree be O(log n), where n is the number of nodes in the tree.
Write a driver program that takes a single command-line argument, which will be a filename. The input file
will contain instructions for tree operations. The first line of the input file will be an integer 0 ≤ N ≤ 106
giving the number of instructions. Following will be N lines, each containing an instruction. The possible
instructions are:
insert K, where −105 ≤ K ≤ 105
is an integer: insert a node with key K into the tree. There is no output.
remove K, where −105 ≤ K ≤ 105
is an integer: remove a node with key K from the tree. If such a node
exists, there is no output. If no such node exists, output TreeError.
search K, where −105 ≤ K ≤ 105
is an integer: output Found if a node exists with key K. If no such node
exists, output NotFound.
max: output the maximum key in the tree. If the tree is empty, output Empty.
min: output the minimum key in the tree. If the tree is empty, output Empty.
inprint: print the keys of the tree according to an in-order traversal, separated by a single space. If the
tree is empty, output Empty.
Example input file:
18
inprint
remove 2
max
search 5
insert 1
insert 2
search 1
search 2
insert 3
inprint
insert 10
insert 5
inprint
search 5
remove 2
inprint
max
min
7
Example output:
Empty
TreeError
Empty
NotFound
Found
Found
1 2 3
1 2 3 5 10
Found
1 3 5 10
10
1
8