IC 312 Fall 2022 / HWs

This is the archived website of IC 312 from the Fall 2022 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Homework 07: Partial AVL implementation

Name: _____________________________________________ Alpha: ___________________

Describe help received: ________________________________________________________

  • Due by 0800 on Monday, October 17
  • This homework contains code to be submitted electronically. The assignment name on the submit system is hw07.
  • This is an electronic homework and you do not need to print out anything to turn in during class.

1 Overview

For this homework, you will implement insertion and a restricted form of removal for a balanced search tree, e.g., an AVL tree, that holds only keys of type double and no values.

There are only 2 public methods you need to implement, but getting the tree rotations and rebalancing right is notoriously tricky business. We have made the task simpler for you by not making the class generic, only having keys (no values), only asking for a restricted form of removal, and making the autotest code visible. But this will still be a challenging task — be sure to take your time, think CAREFULLY about every line of code you write, and draw lots of pictures to help you check your work along the way.

2 Files

You can get all these files at once by downloading the file hw07.tar.gz and running tar xzvf hw07.tar.gz

3 The AddMax interface

Your task is to complete the DoubleTree class so that it implements the AddMax interface. Fortunately, this interface has just two methods:

  • void add(double x): Inserts a new key into the tree. You can assume that there will not be any duplicate insertions, so x will not be exactly equal to any key already in the tree.
  • double removeMax(): Removes and returns the largest key in the tree.

Of course, you will probably want to add your own methods so that you can test your code and see what your tree looks like as you debug!

4 Testing and submission

You will be limited to just 10 submissions on the submit server. The reason for this is to encourage you to test your own code locally and make sure it’s perfect before you submit.

But this is not as dire as it may seem: the full testing code that will be used when you submit is available in the AddMaxTest.java file above. To compile and run this test, you have to install JUnit4. This is already installed on the lab machines in Hopper, or on your VM or WSL you can run

sudo apt install junit4

After that, you can compile and run the tests with the following two commands:

javac -Xlint:all -cp .:/usr/share/java/junit4.jar *.java
java -ea -cp .:/usr/share/java/junit4.jar org.junit.runner.JUnitCore AddMaxTest

Because it’s annoying to type those long commands, we kindly give you a Makefile that has them pre-loaded. So then you can just type make test to compile and test your code.

See this page for more help about writing JUnit test cases.