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

Contents [0/52]

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

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

Course: CSC301 (Data Structures II)

Instructor: James Riely

Overview of Today's Class [2/52]

Admin: Course Overview [3/52]

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/52]

Plus

Admin: Prerequisites [5/52]

CSC300/402 C- or better.

Admin: Policies [6/52]

You must attend class!

Admin: Discussion Forum [7/52]

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

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

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/52]

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/52]

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

Admin: Textbooks [10/52]

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, AddAll]

by Cay Horstmann (Addison-Wesley, 2017)

Available as Ebook

Available online via Safari

Companion site.

Older edition is fine.

Algorithms 4e [Amazon, AddAll]

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, AddAll]

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, AddAll]

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, AddAll]

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/52]

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 Java, Eclipse and Graphviz [12/52]

Note that Eclipse

Start Menu -> Programming -> Eclipse        

There is a video walking through these steps on windows: Java/Eclipse/Graphviz installation

Quick links:

Step-by-step:

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

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

Quick links:

Step-by-step:

Admin: Downloading homework [14/52]

Follow these instructions:

hw-file-get1
hw-file-get2
hw-file-get3

Admin: Uploading homework [15/52]

After you have completed the assignment, save your work in eclipse and then follow these instructions:

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

Admin: Installation problems? [16/52]

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 you have lots of red marks in Eclipse [17/52]

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

install-eclipse-red

Try this:

Admin: What to do if warnings/errors won't go away in Eclipse [18/52]

Try

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

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

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

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

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? [20/52]

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: Useful stuff in eclipse [21/52]

To stop copy paste from inserting bogus imports

  "Preferences" > "Java" > "Editor" > "Typing" > (Under "When Pasting") 
  uncheck "Update Imports"

To get autocompletion when typing characters other than .

  "Preferences" > "Java" > "Editor" > "Content Assist" > (Under "Auto Activation")   
  paste the following in the textfield for "Auto activation triggers for Java"

  ._abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789

  Use uparrow/downarrow to go through the suggestions
  Use enter/return to accept a suggestion
  Use escape to dismiss the suggestions

To change fonts

  "Preferences" > "General" > "Appearance" > "Colors and Fonts" > "Basic" > "Text Font" > "Edit..."

Admin: How to talk about code via email [22/52]

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: Running programs [23/52]

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 [24/52]

Review Homework [25/52]

Trees: Terminology [26/52]

tree-height-depth

Trees: Traversals [27/52]

tree-simple

Note: Parentheses are included only for clarity.

Tree code: While loop going left [28/52]

    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 [29/52]

    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 [30/52]

    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 [31/52]

    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 [32/52]

    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) [33/52]

    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? [34/52]

    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? [35/52]

    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? [36/52]

    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? [37/52]

    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! [38/52]

    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 [39/52]

    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! [40/52]

    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 [41/52]

    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 [42/52]

    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 [43/52]

    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 [44/52]

    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... [45/52]

    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... [46/52]

    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! [47/52]

    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! [48/52]

    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! [49/52]

    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 [50/52]

    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 [51/52]

    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 [52/52]

    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