CSC301: Week 1: Trees, iteration and recursion (3.2)

Contents [0/56]

Are You In The Right Room? [1/56]
Overview of Today's Class [2/56]
Admin: Course Overview [3/56]
Admin: Course Objectives [4/56]
Admin: Prerequisites [5/56]
Admin: Policies [6/56]
Admin: Discussion Forum [7/56]
Admin: Assessment [8/56]
Admin: Course Homepage [9/56]
Admin: Textbooks [10/56]
Admin: Expectations [11/56]
Admin: Install Graphviz [12/56]
Admin: Install code for this class [13/56]
Admin: Install Java 11 [14/56]
Admin: Install Eclipse [15/56]
Admin: Start eclipse in the eclipse-workspace you downloaded before [16/56]
Admin: Disable some warnings [17/56]
Admin: Downloading homework [18/56]
Admin: Uploading homework [19/56]
Admin: Installation problems? [20/56]
Admin: What to do if you get errors on the format function [21/56]
Admin: What to do you have lots of red marks in Eclipse [22/56]
Admin: How to add a JRE [23/56]
Admin: What to do if you cannot see package explorer in Eclipse [24/56]
Admin: Run problems? [25/56]
Admin: How to talk about code via email [26/56]
Admin: About the code from the textbook [27/56]
Homework [28/56]
Review Homework [29/56]
Trees: Terminology [30/56]
Trees: Traversals [31/56]
Tree code: While loop going left [32/56]
Tree code: Recursion going left [33/56]
Tree code: Recursion going left and right [34/56]
Tree code: Recursion going left and right [35/56]
Tree code: Recursion going left and right [36/56]
Tree code: Base case first (negating the conditional) [37/56]
Tree code: Is this correct? [38/56]
Tree code: Is this correct? [39/56]
Tree code: Is this correct? [40/56]
Tree code: Is this correct? [41/56]
Tree code: Back to sanity! [42/56]
Tree code: Make right call independent of the left [43/56]
Tree code: Don't need the sz parameter! [44/56]
Tree code: Local variables don't matter [45/56]
Tree code: Local variables don't matter [46/56]
Tree code: Nullable [47/56]
Tree code: Non-nullable [48/56]
Tree code: The winner is... [49/56]
Tree code: The winner is... [50/56]
Tree code: Negligent! [51/56]
Tree code: Paranoid! [52/56]
Tree code: Returns too quickly! [53/56]
Tree code: Threaded parameter with non-nullable pointer 0 [54/56]
Tree code: Threaded parameter with non-nullable pointer 1 [55/56]
Tree code: Deriving non-nullable code from a loop [56/56]

(Click here for one slide per page)


Are You In The Right Room? [1/56]

Course: CSC301 (Data Structures II)

Instructor: James Riely

Overview of Today's Class [2/56]

Admin: Course Overview [3/56]

This is the second course in a two-course sequence on data structures using Java. The course focuses mainly on the following data structures, their analysis, and their applications: trees (search trees, balanced search trees), heaps, associative arrays, hash tables, and data structures for representing graphs. The implementation of the basic operations on each data structure are discussed and analyzed in terms of their efficiency. The applications discussed highlight and exploit the unique characteristics of the different data structures, and emphasize problem solving and recursive thinking.

From Wired Magazine: Code is far from a utilitarian means to an end. Like painting or sculpting, it's a medium with which you can create something. And as such, code can take many forms: beautiful or ugly, elegant or clunky.

Admin: Course Objectives [4/56]

Plus

Admin: Prerequisites [5/56]

CSC300/402 C- or better.

Admin: Policies [6/56]

You must attend class!

Admin: Discussion Forum [7/56]

You must subscribe to the course discussion forum on google groups. Do it as soon as possible.

http://groups.google.com/group/csc301winter2018

The discussion forum is an extension our time in class. This is particularly great for students that miss the live lecture. If you are watching the class online, you should write down any questions that arise, including the time from the recording for reference. Then send the list of questions to me, and I will post a reply to the group.

I will also use Teamviewer for communication. With teamviewer, you can show me your computer screen while we talk over the phone.

Admin: Assessment [8/56]

Grades will be determined as follows.

You must pass the final exam in order to pass the course.

DePaul's academic integrity policy

For in class students: Participation will consist of me calling on students in class. If you are not here or don't hear, then you will lose participation credit.

Admin: Course Homepage [9/56]

Course homepage: http://fpl.cs.depaul.edu/jriely/ds2/

Admin: Textbooks [10/56]

If you are delayed in getting the texts, you can view them online via Safari.

Required Books

Core Java SE 9 for the Impatient, 2nd Edition [Amazon, Indiebound]

by Cay Horstmann (Addison-Wesley, 2017)

Available as Ebook

Available online via Safari

Companion site.

Older edition is fine.

Algorithms 4e [Amazon, Indiebound]

by Robert Sedgewick and Kevin Wayne (Addison-Wesley, 2011)

Available as Ebook

Available online via Safari

Companion site.

Do not get an older edition. They are completely different books.

Recommended Books

Schaum's Outline of Data Structures with Java 2e [Amazon, Indiebound]

by John Hubbard (Schuams, 2009)

This book is a good source of example problems with solutions.

Available as Ebook

More books

Algorithms 4e (with videos) [Amazon, Indiebound]

by Robert Sedgewick and Kevin Wayne (Addison-Wesley, 2011)

Available as Ebook

How to Think Like a Computer Scientist

by Allen B. Downey.

Free!

An good introduction to Java.

Skip the GridWorld chapters, which are intended to help with the AP exam in CS.

See also these lecture notes from MIT. The first three lectures are particularly useful.

Java for Python Programmers

by Brad Miller.

Free!

See also here.

Introduction to Programming in Java (Chapter 1)

by Robert Sedgewick and Kevin Wayne

Free!

This is the first chapter of the introductory text written by the authors of our primary textbook.

It presents the same material as section 1.1 of the primary text, but at a slower pace.

Effective Java 2e [Amazon, Indiebound]

by Joshua Bloch (Addison-Wesley, 2008)

Available as Ebook

Available online via Safari

The algorithms text describes all of the Java that is required for the class. The discussion is terse, making it an excellent reference. If you would like a longer discussion of Java, you might want a supplementary text. In this case, you might consider one of the following.

Admin: Expectations [11/56]

We will discuss concepts in class.

You will have weekly programming assignments.

Getting the homework correct is not enough. The first time you solve something it could take days, and may require help. Once you get a solution, you are not done.

From the Chronicle of Higher Education: People often mistake familiarity for understanding. They open the textbook after getting home from a lecture, and they recognize the material. They think: I get this. Then they take a test -- and bomb it.

I do not give out solutions to homework problems.

How to succeed:

Admin: Install Graphviz [12/56]

This step is only necessary to draw the pictures that I show in class.

On windows, download and install Graphviz from here: Graphviz
install-graphviz-windows

On the mac, you need to install Homebrew
install-graphviz-mac

Once you have homebrew, just enter the following commands on the Terminal:

brew update
brew install graphviz

Admin: Install code for this class [13/56]

Quick links:

Step-by-step:

Admin: Install Java 11 [14/56]

We will use Java 11. It is easiest to use eclipse if you remove any other versions of Java from your machine.

You can download Java 11 from Amazon or adoptOpenJDK

JDK stands for Java Development Kit.

Admin: Install Eclipse [15/56]

Install the Eclipse IDE for Java Developers from here: Eclipse Downloads

Get the most recent version.

You should get Eclipse IDE for Java Developers. The main difference between versions is the number of packages that come pre-installed. This is the smallest version that has everything we need.

install-eclipse-download1
install-eclipse-download2
install-eclipse-download3
install-eclipse-download4
install-eclipse-download5
install-eclipse-download6

Admin: Start eclipse in the eclipse-workspace you downloaded before [16/56]

There is a video walking through these steps on windows: Algs4 workspace movie

Admin: Disable some warnings [17/56]

Disable warnings for unnecessary code. LEAVE ALL OTHER WARNINGS AT THEIR DEFAULT VALUES.

install-eclipse-warnings1

On windows, the "Preferences" option is under "Window" instead of "Eclipse"

  Go to "Eclipse/Window" > "Preferences" > "Java" > "Compiler" > "Errors/Warnings" > "Unnecessary code"
  Set the following to "Ignore"
    "Value of local variable is not used"
    "Unused private member"

install-eclipse-warnings2
install-eclipse-warnings0

Admin: Downloading homework [18/56]

Download the appropriate file from the Submission tab of D2L. Use control-click on mac, right-click on windows to download the file.

hw-file-get1a
hw-file-get1b

Use drag-and-drop to add the file to eclipse into the correct package.

hw-file-get2
hw-file-get3

If drag and drop are not working, try the following:

Admin: Uploading homework [19/56]

After you have completed the assignment, save your work in eclipse and use drag-and-drop to upload the file to D2L.

hw-file-put1
hw-file-put2
hw-file-put3
hw-file-put4

If drag-and-drop does not work, you can use an alternative method, shown below.

Be very careful to upload a .java file from the src directory.

Do not upload a .class file from the bin directory.

hw-file-put5
hw-file-put6

Admin: Installation problems? [20/56]

If you have errors after installing eclipse and the code from class, please watch this: Eclipse problems

Uninstall everything and try again.

If that does not work, email me ASAP. Don't waste time trying to fix a broken eclipse install.

Admin: What to do if you get errors on the format function [21/56]

You may get a compiler error message like this:

The method format(String, Object[]) in the type StdOut is not applicable for the arguments (String, String)
The method format(String, Object[]) in the type StdOut is not applicable for the arguments (String, String, int, int)

Make sure that you are using Java 11

install-eclipse-jre2
install-eclipse-jre1

Admin: What to do you have lots of red marks in Eclipse [22/56]

Suppose you had eclipse working and then one day, eclipse looks like this:

install-eclipse-red

Try

  "Project" > "Clean..." > "Clean all projects"

If that does not work, try creating a fresh eclipse-workspace.

The above works by copying the good files to a new eclipse-workspace. You can also try the following approach, which removes the problemantic files from the exiting eclipse-workspace instead.

If that does not work ensure that you have the correct version of Java installed.

Admin: How to add a JRE [23/56]

Eclipse will only include JREs that were present before it started in a given eclipse-workspace. If you add a JRE later, the easiest thing to do is to recreate the eclipse-workspace from scratch. See the instructions on the previous slide.

You can also add a JRE after the fact, following these instructions:

add-jre1

add-jre2

add-jre3

add-jre4

Admin: What to do if you cannot see package explorer in Eclipse [24/56]

To show the package explorer, do this:

package-explorer1

Once it is showing, you can adjust the view using the buttons:

package-explorer2

Admin: Run problems? [25/56]

You may get this Run As box in eclipse, like this:

install-run1

Or this:

install-run2

First, make sure that you are running the code from the correct package in the src folder. Go back to the installation instructions for the code from class and make sure that the package explorer looks correct. If not, re-do the installation of the code from class, and start over.

If the package explorer looks okay, then try selecting the program you want to run in the package explorer and using a right click to bring up a context menu. You can select run from there:

install-run3

The run button is context sensitive in eclipse. It's behavior varies depending upon where the mouse was last clicked and what the last command to be run was. This problem usually sorts itself out. So try the run button again later.

Admin: How to talk about code via email [26/56]

If you want advice about an error, send me email, doing one of the following.

If you have a problem getting a program to work and you want me to look at some of your code in more detail, send me email with the following three things.

  1. Your java file as an attachment.

  2. A description of how the output of the program is different from what you expected.

  3. The output of your program, if it runs.

Admin: About the code from the textbook [27/56]

The textbook code is written to run from the command line. We will not do this. Instead, we will edit the code in eclipse to provide the following, when necessary:

  1. command line arguments
  2. standard input
  3. standard output

If the text runs the program:

  java Program arg1 arg2 < input.txt > /tmp/output.txt

We will add the following lines to the "main" method of our java program:

  public static void main(String[] args) {
    args = new String[] { "arg1", "agrg2" };
    StdIn.fromFile ("data/input.txt") 
    StdOut.toFile ("/tmp/output.txt")
    ...

Homework [28/56]

Review Homework [29/56]

Trees: Terminology [30/56]

tree-height-depth

Trees: Traversals [31/56]

tree-simple

Note: Parentheses are included only for clarity.

Tree code: While loop going left [32/56]

    public int sizeLeft () {
        Node x = root;
        int sz = 0;
        while (x != null) {
            x = x.left;
            sz = sz + 1;
        }
        return sz;
    }

While loop going left.

Here is a trace of an execution.

Back to the size problem. Here is starter code which computes the size of the leftmost branch in the tree.

Tree code: Recursion going left [33/56]

    public int sizeLeft () {
        return sizeLeft (root, 0);
    }
    private static int sizeLeft (Node x, int sz) {
        if (x != null) {
            sz = sizeLeft (x.left, sz + 1);
        }
        return sz;
    }

Recursion going left

Here is a trace of an execution.

Tree code: Recursion going left and right [34/56]

    public int size () {
        return size (root, 0);
    }
    private static int size (Node x, int sz) {
        if (x != null) {
            sz = size (x.left, sz + 1);
            sz = size (x.right, sz + 1);
        }
        return sz;
    }

Recursion going left and right. Now computing the size of the tree.

Is this correct?

Here is a trace of an execution.

Tree code: Recursion going left and right [35/56]

    public int size () {
        return size (root, 0);
    }
    private static int size (Node x, int sz) {
        if (x != null) {
            sz = sz + 1;
            sz = size (x.left, sz);
            sz = size (x.right, sz);
        }
        return sz;
    }

Add in only once.

Here is a trace of an execution.

What is the initial value of sz at each node as we go around the tree?

Tree code: Recursion going left and right [36/56]

    public int size () {
        return size (root, 0);
    }
    private static int size (Node x, int sz) {
        if (x != null) {
            sz = sz + 1;
            sz = size (x.left, sz);
            sz = size (x.right, sz);
        }
        return sz;
    }

Computation of the size happens as we go forward, in a preorder traversal.

Initial value of sz at each node is the number of nodes that precede this one in a preorder traversal.

The initial value of sz does not include the node x.

Final value of sz is the initial value plus the size of the tree rooted at x: size (x, sz) returns size (x) + sz

Tree code: Base case first (negating the conditional) [37/56]

    public int size () {
        return size (root, 0);
    }
    private static int size (Node x, int sz) {
        if (x == null) return sz;
        sz = sz + 1;
        sz = size (x.left, sz);
        sz = size (x.right, sz);
        return sz;
    }

Base case first (negating the conditional)

This is more idiomatic for recursive functions.

Tree code: Is this correct? [38/56]

    public int size () {
        return size (root, 0);
    }
    private static int size (Node x, int sz) {
        if (x == null) return sz;
        sz += 1;
        sz += size (x.left, sz);
        sz += size (x.right, sz);
        return sz;
    }

Is this correct?

Tree code: Is this correct? [39/56]

    public int size () {
        return size (root, 0);
    }
    private static int size (Node x, int sz) {
        if (x == null) return sz;
        sz += 1;
        sz += size (x.left, sz);
        sz += size (x.right, sz);
        return sz;
    }

Is this correct?

No. size (x, sz) returns size (x) + sz, so this is adding it twice.

Here is a trace of an execution.

Tree code: Is this correct? [40/56]

    public int size () {
        return size (root, 0);
    }
    private static int size (Node x, int sz) {
        if (x == null) return sz;
        sz = sz + 1;
        size (x.left, sz);
        size (x.right, sz);
        return sz;
    }

Is this correct?

Tree code: Is this correct? [41/56]

    public int size () {
        return size (root, 0);
    }
    private static int size (Node x, int sz) {
        if (x == null) return sz;
        sz = sz + 1;
        size (x.left, sz);
        size (x.right, sz);
        return sz;
    }

Is this correct?

No. Mistake here is to think of sz as shared among the function calls.

Here is a trace of an execution.

Tree code: Back to sanity! [42/56]

    public int size () {
        return size (root, 0);
    }
    private static int size (Node x, int sz) {
        if (x == null) return sz;
        sz = size (x.left, sz);
        sz = size (x.right, sz);
        sz += 1;
        return sz;
    }

Threaded parameter: correct version, doing the addition postorder.

What are the initial values of sz as you go around the tree?

Tree code: Make right call independent of the left [43/56]

    public int size () {
        return size (root, 0);
    }
    private static int size (Node x, int sz) {
        if (x == null) return sz;
        sz = size (x.left, 0);
        sz += size (x.right, 0);
        sz += 1;
        return sz;
    }

Make it so that the right does not know about the left!

Change so that size returns just the size of x, rather than size of x plus sz

Intial value of sz is always 0

Tree code: Don't need the sz parameter! [44/56]

    public int size () {
        return size (root);
    }
    private static int size (Node x) {
        if (x == null) return 0;
        int sz = 0;
        sz += 1;
        sz += size (x.left);
        sz += size (x.right);
        return sz;
    }

Don't need the sz parameter!

Node x is counted postorder, as we return.

This is true regardless of where we put sz += 1, since the intermediate values are not passed around.

Tree code: Local variables don't matter [45/56]

    public int size () {
        return size (root);
    }
    private static int size (Node x) {
        if (x == null) return 0;
        int szl = size (x.left);
        int szr = size (x.right);
        return szl + szr + 1;
    }

Local variables don't matter.

Here is a trace of an execution.

This is static single assignment (SSA) form: each variable is assigned on exactly one line of code.

Most compilers translate your code into SSA as part of the compilation process.

In SSA, the right-hand-side of the assignment may be restricted to be either a single function call or a single operator. In this case, the last line would be translated to:

        int tmp1 = szl + szr;
        int tmp2 = tmp1 + 1;
        return tmp2;

Tree code: Local variables don't matter [46/56]

    public int size () {
        return size (root);
    }
    private static int size (Node x) {
        if (x == null) return 0;
        return size (x.left) + size (x.right) + 1;
    }

From a compiler point of view, this code is identical to the previous version, since this will be translated into SSA.

Tree code: Nullable [47/56]

    public int size () {
        return size (root);
    }
    private static int size (Node x) {
        if (x == null) return 0;
        int sz = 1;
        sz += size (x.left);
        sz += size (x.right);
        return sz;
    }

Back to the version with one variable.

Note that it does not matter when we add 1 to sz, since we don't carry the intermediate values around as parameters.

In this code, we make the call, then check for null.

The variable x is nullable (may be assigned null)

Lets call this the nullable version.

We might also call it optimistic, or Just do it!

Tree code: Non-nullable [48/56]

    public int size () {
        if (root == null) return 0;
        return size (root);
    }
    private static int size (Node x) {
        int sz = 1;
        if (x.left != null) sz += size (x.left);
        if (x.right != null) sz += size (x.right);
        return sz;
    }

In this code, we check for null, then make the call.

The variable x is non-nullable (must not be assigned null)

Lets call this the non-nullable version.

We might also call this cautious, or Look before you leap!

Tree code: The winner is... [49/56]

    public int size () {
        return size (root);
    }
    private int size (Node x) {
        if (x == null) return 0;
        int sz = 1;
        sz += size (x.left);
        sz += size (x.right);
        return sz;
    }
    public int size () {
       if (root == null) return 0;
       return size (root);
    }
    private int size (Node x) {
        int sz = 1;
        if (x.left != null) sz += size (x.left);
        if (x.right != null) sz += size (x.right);
        return sz;
    }

What are the advantages of each approach?

In general, which should you prefer?

Nullable has one static conditional (if statement). Non-nullable has three!

However, we have exactly the same number of dynamic conditionals (executions of the if statement).

Nullable has about twice as many dynamic function calls! Count them!

Tree code: The winner is... [50/56]

    public int size () {
        return size (root);
    }
    private int size (Node x) {
        if (x == null) return 0;
        int sz = 1;
        sz += size (x.left);
        sz += size (x.right);
        return sz;
    }
    public int size () {
       if (root == null) return 0;
       return size (root);
    }
    private int size (Node x) {
        int sz = 1;
        if (x.left != null) sz += size (x.left);
        if (x.right != null) sz += size (x.right);
        return sz;
    }

nullable version has less redundancy. Easier to maintain. Full of win.

non-nullable version is also known as Too many base cases!.

Only prefer performance over maintainability if you have determined that the performance is an actual problem and you have done profiling to determine the actual location of the problem.

One of the trickiest things for Java programmers is to keep track of when a variable is nullable.

Recent languages such as swift and kotlin distinguish nullable and non-nullable types. In these languages, a variable that may be null must be given a type that ends in a question mark. (In swift, null is written nil, or equivalently as Optional.none.)

In these languages, we would give different types to the argument in the helper function above. For the nullable version, x would be given type Node? whereas for the non-nullable version, it would be given type Node.

Tree code: Negligent! [51/56]

    public int size () {
        return size (root);
    }
    private static int size (Node x) {
        int sz = 1;
        if (x.left != null) sz += size (x.left);
        if (x.right != null) sz += size (x.right);
        return sz;
    }

What's wrong with this code?

Tree code: Paranoid! [52/56]

    public int size () {
        if (root == null) return 0;
        return size (root);
    }
    private static int size (Node x) {
        if (x == null) return 0;
        int sz = 1;
        if (x.left != null) sz += size (x.left);
        if (x.right != null) sz += size (x.right);
        return sz;
    }

What's wrong with this code?

Tree code: Returns too quickly! [53/56]

    public int size () {
        if (root == null) return 0;
        return size (root);
    }
    private static int size (Node x) {
        if (x.left != null) return 1 + size (x.left);
        if (x.right != null) return 1 + size (x.right);
        return 1;
    }

What's wrong with this code?

Tree code: Threaded parameter with non-nullable pointer 0 [54/56]

    public int size () {
        if (root == null) return 0;
        return size (root, 0);
    }
    private static int size (Node x, int sz) {
        sz = sz + 1;
        if (x.left != null) sz = size (x.left, sz);
        if (x.right != null) sz = size (x.right, sz);
        return sz;
    }

Threaded parameter with non-nullable pointer.

Tree code: Threaded parameter with non-nullable pointer 1 [55/56]

    public int size () {
        if (root == null) return 0;
        return size (root, 1);
    }
    private static int size (Node x, int sz) {
        if (x.left != null) sz = size (x.left, sz + 1);
        if (x.right != null) sz = size (x.right, sz + 1);
        return sz;
    }

Describe the difference from the previous version.

Is it correct?

What's the invariant as we go through the tree?

Tree code: Deriving non-nullable code from a loop [56/56]

    public int size () {
        if (root == null) return 0;
        return size (root, 1);
    }
    private static int size (Node x, int sz) {
        if (x.left != null) sz = size (x.left, sz + 1);
        if (x.right != null) sz = size (x.right, sz + 1);
        return sz;
    }

This is what you get if you start with a variant of the loop sizeLeft.

Recall the original code. Here, you count the node referenced by x.

    public int sizeLeft () {
        Node x = root;
        int sz = 0;
        while (x != null) {
            x = x.left;
            sz = sz + 1;
        }
        return sz;
    }

In the following variant, we assume that x is already taken care of, and you work on x.left instead.

    public int sizeLeft () {
        if (root == null) return 0;
        Node x = root;
        int sz = 1;
        while (x.left != null) {
            x = x.left;
            sz = sz + 1;
        }
        return sz;
    }

Note that x is non-nullable. It hangs back one place.

Going recursive.

    public int sizeLeft () {
        if (root == null) return 0;
        return sizeLeft (root, 1);
    }
    private static int sizeLeft (Node x, int sz) {
        if (x.left != null) {
            sz = sizeLeft (x.left, sz + 1);
        }
        return sz;
    }

Left and right.

    public int size () {
        if (root == null) return 0;
        return size (root, 1);
    }
    private static int size (Node x, int sz) {
        if (x.left != null) sz = size (x.left, sz + 1);
        if (x.right != null) sz = size (x.right, sz + 1);
        return sz;
    }


Revised: 2008/03/17 13:01