CSE 247 Module 10: Ordered Sets

• Module Home
• Studio
• Lab

Studio

Part A

• Perform Team…Pull to make sure you have the latest copies of the software for htis assignment.
• The Java files you need for this assignment are in the studio10 package of the studios source folder.
• Find and open the BST class

  This code is an implementation of the binary search tree shown in class, with slides beginning here.

• Run the BST class as a Java Appliation and look at the resulting output in the console window.
• As a group, go over the output and the code and answer the following questions:

  Write your answers into the studio10.txt file in the studiowriteups folder.

  A1. Why do sad and happy appear as they do? Why is happy indented? What are the parent, left-child, and right-child relationships between happy and sad?

  Modify the code in the main method so that some string appears above sad, indented as much as happy.

  A2. What string did you use?

  In the numbers that follow, find the first (smallest) and last (largest) entries in the tree that is shown (on its side, as discussed in lecture).

  A3. Is the first number always the first line to be shown in such a display?

  A4. Is the last number always the last line to be shown?

• Take a look at the add and addHelper methods.

  A5. Why do we need insertHelper?

  A6. Why is it private instead of public?

• The console output shows the result of two remove operations. Look through the code and discuss how the code accomplishes remove. Both of the examples involve a node with two children, and you can see the results both before and after each remove.

  A7. Does the code actually remove the node containing the value to be removed? If not, what is actually happening?

• Toward the bottom of the main method, you see the following code:

  // Why does this code fail?
  //		
  //		BST<Color> col = new BST<Color>(new Ticker());
  //		col.add(Color.RED);
  //		col.add(Color.BLUE);
  

  Uncomment that code, and then run the code.

  A8. Why does the code fail to execute properly?

  A9. Why does eclipse not report a problem when you try to create a BST of type Color?

Part B

• Run the SortedSetUsingBST class, which will produce ticks and timing output in the outputs folder. The integers provided to this sorted set are random.

  Remember to refresh the outputs folder so you can see the new files generated.

  B1. What behavior do you see in the output? You will likely have to rely on ticks rather than time, because the times are so fast.

  B2. What behavior did you expect to see, and why?

• Let's change the input to the binary search tree run so that it runs on a sorted input sequence. To make this change, look near the end of SortedSetUsingBST, and change these two lines:

  				new IntArrayGenerator(), 
  /*				new IntSequenceArrayGenerator(),   */
  

  to

  /*				new IntArrayGenerator(), 	*/
    				new IntSequenceArrayGenerator(),   
  

  which will provide an integer sequence as input.

  Rerun the SortedSetUsingBST program, refresh outputs and look at the newest time and ticks files.

  B3. What behavior do you see in the output given the sorted input?

  B4. What behavior did you expect to see, and why?

• Now let's look at SortedSetUsingUnorderedList. Run it, refresh outputs, and look at the generated times. We can't look at ticks, because the LinkedList implementation is already written, but the times should provide interesting output.

  B5. What behavior do you see in the output when a sorted set is implemented by an unordered list? Adding to the list should be quick, so why are we seeing these times?

  B6. What behavior did you expect to see, and why?

Submitting your work (read carefully)

• If there is a file for you to complete in studiowriteups, please respond to the questions and supply any requested information.
• You must commit and push all of your work to your repository. It's best to do this from the top-most level of your repository, which bears your name and student ID.
• Follow the instructions in the green box below to receive credit for your work.

When you done with this studio, you must be cleared by the TA to receive credit.

• Commit all your work to your repository
• Fill in the form below with the relevant information
• Have a TA check your work
• The TA should check your work and then fill in his or her name
• Click OK while the TA watches
• If you request propagation, it does not happen immediately, but should be posted in the next day or so

This demo box is for studio 10

	Last name	WUSTL Key	Propagate?
		(NOT your numeric ID)		Do not propagate
e.g.	Smith	j.smith
1				Copy from 1 to all others
2				Copy from 2 to all others
3				Copy from 3 to all others
4				Copy from 4 to all others

---

TA: Password: