The ACM's Code of Ethics states in section 1.5: Honor property rights including copyrights and patent
- Skim the Code of Ethics, but read 1.5 more closely.
- Write an essay (single-spaced, 12 pt, at most one page) in which you:
- State and explain this ethical obligation.
- Explain how the obligation applies to professional action.
- Use a systematic argument to support your explanation.
- Give several specific examples of professional activities where the ethical obligation applies.
If you prefer, you may select another section of the ACM Code of Ethics as the basis for your essay. If you do this, be sure to indicate which section you chose to elaborate.
- Submit your essay to the Code of Ethics drop box on ANGEL.
You will submit problems 2-5 to the WA5 dropbox as usual:
Use mathematical induction to prove that this formula is true for all integers n≥1.
java.util.Map
to complete this problem.
Assume in each case that you are inserting the items into a Binary Search tree that is initially empty. There are of course 4! permutations, but in many cases multiple permutations lead to the same tree. For example, 2134 and 2314 lead to the same tree (2 is the root, 1 is 2’s left child, 3 is 2’s right child, 4 is 3’s right child. That's why different trees have different probabilities (each permutation has probability 1/24, but some trees come form multiple permutations; the total of all of the probabilities should be 1). As another example, the permutation 2413 leads to the tree (expressed in "displayable" notation) chars="2143", children="20L0".
(12 points) Fill in the following table. Be very careful to get the exact values. Most of the credit will be for the last column.
Feel free to include explanations of your answers. correct_answer → full_credit. wrong_answer + no_explanation → no_credit.
1/2 point for each entry in the first two columns, and 2 points each for each entry in the last column.
| n | Height of shortest binary tree with n nodes | Height of tallest binary tree with n nodes | Height of tallest AVL tree with n nodes |
|---|---|---|---|
| 7 | 2 | 6 | 3 |
| 8 | |||
| 370 | |||
| 17000 | |||
| 50000 |
(40 points) This problem, though part of the written assignment, involves actually getting your code working on your computer. But, since it requires you to write a very small amount of code, and because the thought process involved is more along the lines of written problems in this course, I am including it in a written assignment.
When it comes to implementing ordered sets, Binary Search Trees are generally better than array lists or linked lists, because many O(n) operations on lists or vectors become (on average) O(log
n) on BSTs. But there is at least one operation that is less efficient in most cases on a BST than on a list: given an element of the structure, find the next or previous in-order element of the structure. This is especially true for nodes in the BST that have no children. Weiss’s
InOrder
iterator class (page 594) has to maintain an auxiliary stack in order to be able to do the next
advance(). It would also be nice to be able to have a
retreat()
method in the
InOrder
class as well. A call to
advance()
moves the current position to the in-order successor of the current node, while a call to
retreat()
would move to the in-order predecessor of the current node. The obvious approaches to efficiently supporting both
advance()
and
retreat()
require a lot of extra space and time. So let’s try an un-obvious approach.
There is a well-known way to make these operations more efficient. We can take advantage of the fact (we will prove it later) that more than half of the references in a binary tree are
null. We replace each
null
left reference in the tree by a reference to that node’s in-order predecessor, and replace each
null
right reference by a reference to the node’s in-order successor. Traditionally, these in-order references have been called threads (same word but no relation to “threads of execution”). If we use threads, we need to be able to distinguish a thread from a regular left or right pointer. Doing so only requires two additional bits in each node , although it’s easier to write the code (and thus we do it here) with two
boolean
instance variables,
isLeftThread
and
isRightThread. When one of these fields contains true, it indicates that the corresponding reference in the node is a thread, rather than a “normal” tree pointer.
You can do the problem without reading this note; it is here
for
enlightenment of those who may be concerned about
the extra space needed for these new boolean fields. This
explanation uses some terminology that is outside the
background required of this course, so don't worry about it
if you don't understand all of it. I would be happy to talk
with you about "masking" if it is a new concept for you; it
is not a required concept for this course.
Generally there would be some field of the node that does not really use all of the bits allotted to it, and some masking would allow us to grab two of the bits of that field to use for the “is it a thread?” information without taking up any extra space. In a language (like C or C++) that allows typecasting between integers and pointers, we can
definitely do this: The value of a pointer will probably always end in two 0 bits (because things “pointed to” will be aligned on longword boundaries); we
can use those bits “for free” (use masking to
zero out the last two bits when using the value as a
pointer. Zero out the first 30 bits when testing for
thread existence) That is, the extra space would come at no cost. But this approach obviously requires
(a constant multiple) more time.
In the diagram below, normal pointers are shown as solid lines, while threads are dotted lines. The threads from the left- and right-most nodes represent
null
references. These two
null
references could be treated either as threads or regular pointers, but since the former makes the code that you will write easier, the diagram shows them as threads.
I am providing a complete
ThreadedBinaryNode
class and JUnit tests in
ThreadedBinarySearchTreeTest. To help you with debugging, I’m also providing a
TestThreadedTree
class that prints results rather than doing unit tests. The file
expected_output_of_TestThreadedTree.txt
gives the results of a correct run of
TestThreadedTree. While these printed results should be useful for debugging, the JUnit tests are what we will use to judge the correctness of your code.
Your job is to complete the
ThreadedBinarySearchTree
class. I provided part of the class to help you get oriented, so you only have to write three methods (insert,
toStringInOrder, and
toStringInReverseOrder). In fact, we have provided the driver for
insert; you only need to write the recursive helper method that does the real work.
In order to get full credit, you must meet the following constraints:
-
insertmust have running time that is O(height of the tree). -
toStringInOrderandtoStringInReverseOrdermust not use a stack (nor any other additional collection, including an array) or recursion. -
The code that you write for
toStringInOrderandtoStringInReverseOrdermay not referencerootat all. (To be specific, you can use the two given references torootbut you must not add any others).
Ideally,
ThreadedBinarySearchTree
would implement the entire
SortedSet
interface. But that would have made this problem too long and complicated for a small exercise. So I am only having you implement two methods that are similar to methods from that interface.
Also, it would be desirable to implement
ThreadedInOrder, an in-order iterator class for
ThreadedBinarySearchTree. But I did not want to add the complication of having you write yet another class, so I chose to settle for the
toStringInOrder
and
toStringInReverseOrder
methods, which bring out the same threading issues.
Getting the code: The starting code is available in your SVN repository in the
Threaded
project. Treat the comments in that code as part of the requirements for this problem.
I suggest that you begin by studying the
ThreadedBinaryNode
code. Notice that this class and its fields default (package
friendly) visibility. In order to facilitate debugging, I have written an unusual
toString()
method for the
ThreadedBinaryNode
class. It shows the node’s contents, the contents of its left and right “children”, and the value of its boolean
isLeftThread
and
isRightThread
fields. This
toString()
method should be called whenever you need a text representation of a node’s contents.
You should also study the
ThreadedBinarySearchTree
code. This class has a single instance variable,
root,
of type
ThreadedBinaryNode. No explicit constructor is needed; the default constructor does what we need. Study the provided
find()
method and its recursive helper method as an example of how to work with the threads.
Testing: TestThreadedTree is just provided for your convenience. The JUnit tests in
ThreadedBinarySearchTreeTest
are how we will evaluate the correctness of your program.
Turnin: Commit to your repository.
When we run your program for grading purposes, we may alter the test cases to use some different input strings, but we will not change the test code in any other way.