Recursion and Sorting
> Click or hit ControlEnter to run the code above
Recursive Tree Search

Base case: We’ve reached a node with no descendants. Return true if its value matches, zero otherwise.

Recursive step: Consider our right tree and left tree separately.

Combine results: Return true if either we or our right or left subtree contain the search value.
> Click or hit ControlEnter to run Example.main above
How Could We Make This Search More Efficient?
> Click or hit ControlEnter to run Example.main above
Recursive Tree Traversal
Let’s find all nodes in the tree and add them to a list.
What’s Our (Recursive) Algorithm?
Recursive Tree Traversal

Base case: We’ve reached a
null
node, at which point we can stop. 
Recursive step: Consider our right tree and left tree separately.

Combine results: Add ourselves to the list of nodes.
Java ArrayList
s
Lists are one of the two data structures you meet in heaven.
We’ve studied them in class together. But you’ll usually use Java`s builtin implementations.
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
List list = new ArrayList();
List anotherList = new LinkedList();
> Click or hit ControlEnter to run the code above
> Click or hit ControlEnter to run Example.main above
Other Recursive Data Structures
Every sub(blank) of a (blank) is, itself, a (blank).

Tree

(Contiguous) List

(Contiguous) Array
List Recursion
public class Item {
public int value;
public Item next;
Item(int setValue, Item setNext) {
value = setValue;
next = setNext;
}
}
List Recursion
public class Item {
public int value;
public Item next;
Item(int setValue, Item setNext) {
value = setValue;
next = setNext;
}
}
List Recursion
public class Item {
public int value;
public Item next;
Item(int setValue, Item setNext) {
value = setValue;
next = setNext;
}
}
List Recursion
public class Item {
public int value;
public Item next;
Item(int setValue, Item setNext) {
value = setValue;
next = setNext;
}
}
List Recursion
public class Item {
public int value;
public Item next;
Item(int setValue, Item setNext) {
value = setValue;
next = setNext;
}
}
List Recursion
Just like with trees, we need a way to both make the problem smaller and identify the smallest subproblem.

How do we make the problem smaller? Break the list into the current item and the rest of the list.

What’s the smallest subproblem? A list with a single element.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
Just like with trees and lists, we need a way to both make the problem smaller and identify the smallest subproblem.

How do we make the problem smaller? Break the list into two smaller subarrays.

What’s the smallest subproblem? An array with a single item.
Questions About Recursion?
Sorting Algorithms
Sorting algorithms bring together several of the things that we have discussed recently:

Imperative programming

BigO algorithm runtime analysis

Recursion
Sorting Matters
Sorting is often a building block for many other algorithms.

Searching is more efficient if the data is sorted first

Sorting can be used to detect duplicates

Sorting is often used to produce a canonical representation of data or for presentation to human users
In Memory of Jim Gray, Turing Award Winner
Jim Gray was a pioneer in the fields of databases and data processing.
He vanished at seat in 2007 and, despite a worldwide crowdsourced effort to locate his boat, was never found.
There Are Many Sorting Algorithms
And we won’t discuss them all…

Insertion sort (Friday)

Selection sort (lab)

Merge sort (lecture)

Quicksort (lecture)

Bubble sort (lab)

And even new ones, like Timsort (circa 2002)
Sorting Basics

We’ll discuss sorting on arrays which allow random access, although many algorithms will also work on lists.

We’ll be sorting in ascending order, although obviously descending order sorts are also possible.

We can sort anything that we can compare—but we’ll mostly be sorting integers.
Analyzing Sorting Algorithms
Since sorting algorithms handle data, we care about both time and space complexity.

Time complexity: how long does it take?

Space complexity: how much space is required?
CS 125 Project Fair
Fair Overview
This will be our third CS 125 Final Project Fair: bigger and better than ever.

Date: Thursday 5/2/2019 from 1–3PM, with awards Friday 5/3/2019 at 1:30PM (our official final exam slot).

Participation: Optional but worth 1% extra credit

Location: TBD
How to Not Get a Great CS Job
All of you will get a job. Not all of you will get a great 1 job.
Here’s a good strategy for not getting a good job:

Take CS classes.

Do the projects.

Get good grades.

Don’t do any side projects: focus on grades instead.
How to Get a Great CS Job
Show your passion for technology.

The CS 125 Project Fair is intended to get you started doing that.
Example Fall 2018 Fair Projects
Announcements

MP4 is out. Please get started!

I have office hours today from 1–3PM in Siebel 2227. Please come by and say hi!