CS 199 EMP

Hosted by Jackie Chan and Akhila Ashokan

Topics: MORE Recursion, MORE Trees, and MORE Sorting

Resources

As stated in the title, we'll checkout a recursion problem, a trees problem, and a sorting problem.

Write code on the homepage or any playground on the site!
https://cs125.cs.illinois.edu/

Slides are on the course site!
https://cs199emp.netlify.app/

Remember Recursion?

Don't forget about it. Recusion is just when an algorithm calls itself over and over again until it reaches a stopping point or base case. We'll practice it in just a second but let's recall the three laws of recursion.

  1. A recursive algorithm must have a base case.

  2. A recursive algorithm must change its state and move toward the base case.

  3. A recursive algorithm must call itself, recursively.

Palindrome Practice (10 minutes)

This is a classic recursion problem. Write a method that returns true if a given String is a palindrome.

What's a palindrome? A palindrome is a word that reads the same backwards as forwards. For example, 'madam' is a palindrome.

There are several ways to approach this problem. The iterative solution is the often the simplest, but see if you can come up with the recursive solution.

  • Iterative Solution (5 minutes)

  • Recursive Solution (5 minutes)

Palindrome Starter Code


boolean isPalindromeIterative(String str) {
  // write your iterative solution here 
}

boolean isPalindromeRecursive(String str, int low, int high) {
 // write your recursive solution here 
}

String str = "XYBYBYX";
 
if (isPalindromeIterative(str)) {
  System.out.println("Palindrome");
} else {
  System.out.println("Not Palindrome");
}

if (isPalindromeRecursive(str, 0, str.length() - 1)) {
  System.out.println("Palindrome");
} else {
  System.out.println("Not Palindrome");
}

Trees

This semester we learned about arrays, array ists, hash maps, and TREES!

Trees are the special hierarchical data structure with root values, nodes, parent nodes, and child nodes.

We did some practice with binary trees before. Do you remember what makes a binary tree different from an ordinary tree?

Trees and recursion are two peas in a pod so you'll often use one with the other.

Identical Binary Tree Practice (10 minutes)

You are developing search engine software X. Your software uses binary search trees to store data. Your next task as a developer is to write a method that will return whether two binary trees are identical. Two trees are identical if their nodes have the same values and they are structurally identical.

Identical Binary Tree Start Code

public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode() { }
  TreeNode(int setVal) { 
    this.val = setVal; 
  }
  TreeNode(int setVal, TreeNode setLeft, TreeNode setRight) {
    this.val = setVal;
    this.left = setLeft;
    this.right = setRight;
  }
  
}

public boolean identicalTree(TreeNode p, TreeNode q) {
  // write your code here 
}

TreeNode b = new TreeNode(2, null, null);
TreeNode c = new TreeNode(3, null, null);
TreeNode a = new TreeNode(1, b, c);

TreeNode e = new TreeNode(2, null, null);
TreeNode f = new TreeNode(3, null, null);
TreeNode d = new TreeNode(1, e, f);

System.out.println(identicalTree(a, d));

Sorting...A Short Overview...Again...

  • Bubble Sort: Think about values bubbling up to the top. Average Case Runtime: O(n2)O(n^2)

  • Insertion Sort: Think about having an already sorted list and inserting new values into it. Average Case Runtime: O(n2)O(n^2)

  • Merge Sort: Recursive algorithm (technically all could be recursive, but I think this one is well suit), takes advantage of the fact that merging two already sorted list is easy. Average Case Runtime: O(nlog(n))O(nlog(n))

  • Quicksort: Uses pivots and partitions to split the array apart into smaller pieces. Average Case Runtime: O(nlog(n))O(nlog(n))

  • Selection Sort: Repeatedly finds the minimum or maximum value and moves it to the right position in the array. Average Case Runtime: O(n2)O(n^2)

Sorting Video

Still struggling to visualize how these algorithms work? Check out this video!

Find Pair Practice (10 minutes)

Given an array of integers and a value, find a pair within the array that sum to the given value.

int[] arr = {8, 7, 2, 5, 3, 1 };
int sum = 10; 
findPair(arr, sum); // should print 'Pair found (8,2)'

The naive solution does not using sorting and considers every pair in the array. However, this approach has a time complexity of O(n2)O(n^2). How could you use sorting to improve this run time?

Hint on the next slide

Find Pair Hint

Sort the array into ascending order. Keep track of a high and low index where the indices point to two endpoints in the array. Find the total created by low and high at every iteration. If the result is less than the desired sum, then increment low. If the results is more than the desired sum, then decrement high. Continue this process the desired sum is found or low > high.

And... we are done!

You made it! Another EMP under your belt. We covered some recursion, some trees, and some sorting today.

As always, thanks for stopping by. Good luck on the quiz today.

See y'all on Friday!

Solution Section

Palindrome Iterative Solution

boolean isPalindromeIterative(String str) {
  if (str == null || str.length() == 0) {
    return false;
  }
  
  for (int i = 0, j = str.length() - 1; i < j; i++, j--) {
    if (str.charAt(i) != str.charAt(j)) {
      return false;
    }
  }
  
  return true;
}

Palindrome Recursive Solution

boolean isPalindromeRecursive(String str, int low, int high) {
  // base case
  if (low >= high) {
    return true;
  }
  
  // return false if mismatch happens
  if (str.charAt(low) != str.charAt(high)) {
    return false;
  }
  
  // move to the next pair
  return isPalindromeRecursive(str, low + 1, high - 1);
}

Identical Binary Tree Solution

public boolean identicalTree(TreeNode p, TreeNode q) {
  // p and q are both null
  if (p == null && q == null) {
    return true;
  }
  
  // one of p and q is null
  if (q == null || p == null) {
    return false;
  }
  
  if (p.val != q.val) {
    return false;
  }
  
  return identicalTree(p.right, q.right) && identicalTree(p.left, q.left);
}

Find Pair Solution

// Function to find a pair in an array with a given sum using sorting
public static void findPair(int[] a, int sum) {
  // sort the array in ascending order
  Arrays.sort(a);
  
  // maintain two indices pointing to endpoints of the array
  int low = 0;
  int high = a.length - 1;
  
  // reduce the search space `A[low…high]` at each iteration of the loop
  
  // loop till the search space is exhausted
  while (low < high) {
    // sum found
    if (a[low] + a[high] == sum) {
      System.out.println("Pair found (" + a[low] + ", " + a[high] + ")");
      return;
    }
  
    // increment `low` index if the total is less than the desired sum;
    // decrement `high` index if the total is more than the desired sum
    if (a[low] + a[high] < sum) {
      low++;
    } else {
      high--;
    }
  }
  
  // we reach here if the pair is not found
  System.out.println("Pair not found");
}