Scientific Programming II

ModSim

Midterm

It's dangerous to go alone, take this!

I have provided a NetBeans project for you to start with, containing all of the files needed to get started. When importing into NetBeans, there is a distinct possibility that the IDE will complain about the Java Platform being unable to be found. In that case, right click the project in the Navigator window and choose Properties > Libraries, and ensure that the Java Platform is set to Java 8 (sometimes depicted as Java 1.8).

Documentation

Problem 1 (25 Points)

A set (in mathematics) is defined on Wikipedia as:

A set is a well defined collection of distinct objects. The objects that make up a set (also known as the elements or members of a set) can be anything: numbers, people, letters of the alphabet, other sets, and so on. Georg Cantor, the founder of set theory, gave the following definition of a set at the beginning of his Beiträge zur Begründung der transfiniten Mengenlehre:

A set is a gathering together into a whole of definite, distinct objects of our perception [Anschauung] or of our thought—which are called elements of the set.

Quite simply, a set for our purposes can be considered a list of distinct objects or values. Therefore, {1, 2, 3} is a set while {1, 2, 1} is not. There are several symbols used with sets, which you need to recognize for this problem.

∅ - the empty set, or {}
⊆ - subset operator
∪ - union operator
∩ - intersection operator

Set Operations

Subsets

A set A is a subset of set B if and only if all elements in A are in B, or if:

A = {1, 2, 3}
B = {1, 2, 3, 4, 5}

then:

∅ ⊆ A ⊆ B

Union

The union operation is the 'addition' of sets. Two sets unioned together will produce a third set containing every element contained in either set.

A = {1, 2, 3}
B = {3, 4, 5}
A ∪ B = {1, 2, 3, 4, 5}

Intersection

The intersection operator determines common elements between sets. Two sets intersected together will produce a third set containing every element contained in both sets.

A = {1, 2, 3}
B = {2, 3, 4, 5}
A ∩ B = {2, 3}

You will edit a class Set to include methods that represent the subset, union, and intersection operators. The method signatures should be as follows:

public boolean isSubset(Set that);
public Set union(Set that);
public Set intersect(Set that);

Rubric

• Note: Your documentation should be javadoc. Normal comments will receive half credit.
• Note: Code style means your code should be consistent and readable.

Test Data

Set A = {1, 2, 3}
Set B = {1, 2, 3, 4, 5}
Set C = {3, 4, 5, 6}
Set D = {2, 3, 4}

A ⊆ B == true
A ∪ C == {1, 2, 3, 4, 5, 6}
A ∩ D == {2, 3}

Problem 2 (25 Points)

A strictly binary node in a binary search tree is a node which has both a left child node and a right child node. Write a method public void checkStrictlyBinary() which checks if all the non-leaf nodes of a binary search tree are strictly binary or not. If all the non-leaf nodes are strictly binary, your method should print a line stating, “"All non-leaf nodes are strictly binary". If all non-leaf nodes are not strictly binary, your method should print a count of the number of non-leaf nodes that are strictly binary.

Rubric

• Note: Your documentation should be javadoc. Normal comments will receive half credit.
• Note: Code style means your code should be consistent and readable.

Test Data

          67
     45
23
          13
     11
               9
          1

---

          67
     45
          33
23
          13
     11
               9
          1
               0

Helpful Hints

Helpful Hint 1

You may want a method public boolean isStrictlyBinary() in Node.java that tests if the Node is strictly binary or not.

Helpful Hint 2

You may want a method public boolean isLeaf() in Node.java that tests if the Node is a leaf or not.

Helpful Hint 3

Look at how you solved printing each leaf in a Tree, and expand upon that logic if you're stuck.