CS 199 EMP

Even More Practice

Attendance Link:

https://forms.gle/8yto1LvJ4hntiKNu7

2 meetings every week Tuesday and Thursday

  • Early CST - Early risers and Eastern timezones

  • Evening CST - Western timezones (and really late Eastern folks)

  • Calendar contains zoom links

  • Attend 7 sessions for credit, attendence via google form.

Format

  • 3 practice problems every session

  • focused on practical understanding of concepts covered recently in class

  • slides and material available after both sessions

How to follow along

  • Small breakout rooms of working together

  • Work for 10-15 minutes together, feel free to use paper, whiteboards, online share tools.

  • Use the code playground on the 125 homepage for the interactive running

Recursion

Divide and conquer :)

How to approach recursive problems

  1. Base Case

  2. Recursive step

  3. Combine it back

Base case

  • This is a simplest version of the problem that you can solve.

  • This you can setup with a few simple conditions at the start of your function

  • generally you have at least one but sometimes there might be many base cases

  • For example a factorial has base case 0!=10! = 1

Recursive step

  • How to make a big problem slightly smaller

  • You don't have to solve the big problem right away, the focus is to get it as a slightly simpler problem.

  • Since the function calls itself a lot of times, so eventually the slight reduction everytime leads to the base case.

  • For example to break down the factorial problem you can consider 5!=5∗4!5! = 5 * 4! so here we broke it down to solve 4!4! instead.

Combining it together

  • Eventually everything will eventually hit the base case, so after that you have to do the right step to put it back.

  • Sometimes this is adding, sometimes multiplying, sometimes taking the min/max.

  • In the case of factorial recursive, it's the multiplying of all the results together that works.

  • 5!=5∗4!=5∗4∗3!=5∗4∗3∗2!=5∗4∗3∗2∗1!=5∗4∗3∗2∗1∗0!=5∗4∗3∗2∗1∗15! = 5 * 4! = 5 * 4 * 3! = 5 * 4 * 3 * 2! = 5 * 4 * 3 * 2 * 1! = 5 * 4 * 3 * 2 * 1 * 0! = 5 * 4 * 3 * 2 * 1 * 1

  • Once everything hit the base case now all the results just multiply to give us our result of 120120

Recursive fibonacci Problem (10 minutes)

A classic problem used everywhere when teaching recursion.

For the first two,

f0=1f_0 = 1

f1=1f_1 = 1

Otherwise

fn=fn−1+fn−2f_n = f_{n-1} + f_{n-2}

Recursively generate fibonacci numbers using recursion.

long fib(int n) {
  return 0; 
}
assert (fib(0) == 1);
assert (fib(1) == 1);
assert (fib(6) == 13);

Binary Trees

Binary tree data structure

  • This class we work with the simplest type of trees called binary trees.

  • Each node has a left node and a right node, they both don't have to be filled out but there never can be more of these.

  • A tree is a type of recursive data structure, that means that even the nodes are trees themselves, so it's right to think about each tree being made up of a left subtree and right subtree.

  • Since it is a recursive data structure, trees are great for recursive algorithms and trying to do these problems iteratively will be far more complex. This means your code for doing stuff like this will often be short, but tricky to figure out.

  • It gets better with practice :)

Full binary tree (10 minutes)

  • Check for full binary tree

  • That means that each node has either zero children, or two.

  • Return true for null cases.

  • full binary tree

  • From wikipedia images Full_binary (CC License)

public class Tree {
  int value;
  Tree left;
  Tree right;
}

public static boolean isFull(Tree t) {
  return false;
}

Problem (10 minutes)

  • Given a binary tree, check if it follows the heap property.

  • There are many types of heaps, here we pick max-heap nodes higher up are greater than the ones below.

  • Return true if all the childen below a node are less than the given node.

  • Return true for null

  • max heap

  • From wikipedia images Max-Heap (CC License)

public class Tree {
  int value;
  Tree left;
  Tree right;
}

public static boolean isHeap(Tree t) {
  return false;
}

Solutions

(no peeking, it's for your own good!)

(no seriously, attempt the problems with your groupmates first!)

1)

long fib(int n) {
  if (n < 2) {
    return 1;
  }
  return fib(n - 1) + fib(n - 2);
}
assert (fib(0) == 1);
assert (fib(1) == 1);
assert (fib(6) == 13);

2)

public static boolean isFull(Tree t) {
  // base cases
  if (t == null) {
    return true;
  }
  if (t.left == null && t.right == null) {
    return true;
  }
  if (t.left == null || t.right == null) {
    return false;
  }
  // recurse
  return isFull(t.left) && isFull(t.right);
}

3)

public class Tree {
  int value;
  Tree left;
  Tree right;
}

public static boolean isHeap(Tree t) {
  if (t == null) {
    return true;
  }
  // check if each branch exists, then first check the immediate value 
  // and after that check the whole subtree
  if (t.left != null  && t.value < t.left.value  && !(isHeap(t.left)))  {
    return false;
  }
  if (t.right != null && t.value < t.right.value && !(isHeap(t.right))) {
    return false;
  }
  
  return true;
}