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

Review: How to approach recursive problems

  • 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

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)

Given a Tree, return a list of all the node values that are single leaves. (single meaning they are the only leaf corresponding to a parent node, Right or Left, but not both)

import java.util.ArrayList;
import java.util.List;
public class Tree {
  int value;
  Tree left;
  Tree right;
}

public static List<Integer> findSingleLeaves(Tree t) {
  List singleLeaves = new ArrayList();
  return singleLeaves
}

Sorting

Why do we sort?

Sorting algorithims make it easier for us to index through all sorts of data

  • dewey decimal system: sorts non-fiction books in order
    • Fiction books are sorted by author's last name.
  • Students in a gradebook, sorted by netid
  • The People page on the 125 website, sorted by first name (in each category)

Common sorting algorihims and their runtimes

(As told by geoff's old slides)

merge
https://en.wikipedia.org/wiki/Merge_sort

insert
https://en.wikipedia.org/wiki/Insertion_sort

quick
https://en.wikipedia.org/wiki/Quicksort

Anagram (10 minutes)

Given two strings s and t , write a function to determine if t is an anagram of s.
Hint: Try to see how using Arrays.sort() could help you solve this faster

public boolean isAnagram(String s, String t) {

}

see: https://www.geeksforgeeks.org/arrays-sort-in-java-with-examples/

Pet Shop, but for chuchu (10 minutes)

Geoff has given Chuchu an allowance for being a good boi. Chuchu now wants to use the money he has saved up to buy as many chew toys as he can. as he chew-chews through a lot of them. You are given Chuchu's allowance and an array of the toys and their prices (you can assume that every item in the store's inventory has its own price int in the array, so duplicates exist). Return the max number of toys chuchu could buy.
Solve this with sorting!

3 bones ($5 each), 1 rope ($2 each), 2 plushies($3 each) would look like
[5, 5, 5, 2, 3, 3]

If chuchu had 9 dollars, the most he could get in this example would be 1 rope, and two plushies, return 3

int maxToys(int allowance, int[] toyInventory) {
  int toyCount = 0;
  return toyCount;
}
int[] toys = {5, 5, 5, 2, 3, 3};
assert maxToys(9, toys) == 3;

Solutions

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

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

1)

import java.util.ArrayList;
import java.util.List;

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

public static List<Integer> findSingleLeaves(Tree t) {
  List singleLeaves = new ArrayList();
  singleHelper(t, singleLeaves);
  return singleLeaves;
}

public static void singleHelper(Tree t, List list) {
  if (t == null) {
    return;
  }
  if (t.left == null ^ t.right == null) {
    list.add(t);
  }
  singleHelper(t.left, list);
  singleHelper(t.right, list);
}

2)

import java.util.Arrays;

public boolean isAnagram(String s, String t) {
  if (s.length() != t.length()) {
    return false;
  }
  var arrS = s.toCharArray();
  var arrT = s.toCharArray();
  Arrays.sort(arrS);
  Arrays.sort(arrT);
  
  return Arrays.equals(arrS, arrT);
}

System.out.println(isAnagram("harsh", "hrsah"));

3)

import java.util.Arrays;
// O(n) loop with O(nlogn) sort over naive O(n^2)
int maxToys(int allowance, int[] toyInventory) {
  Arrays.sort(toyInventory);
  int toyCount = 0;
  while (allowance > 0) {
    allowance -= toyInventory[toyCount];
    toyCount++;
  }
  return toyCount - 1; 
  // toyCount is the number of toys till we run out of money
  // so -1 is the number of toys we can get with some money left
}
int[] toys = {5, 5, 5, 2, 3, 3};
assert maxToys(9, toys) == 3;