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

Let's talk about (Let's talk about Recursion)

haha, see what i did there?

  • Simply put, recursion is just another way of writing an algorithim, by breaking it into smaller steps
  • A recursive function will call iteself and will continue to call itself untill reaching a defined stopping point.
    • this stopping point is the smallest step our algorithim takes, what we call a base case

Recursion

Lecture Recap: Steps to making a recursive algorithim

  1. Make the problem smaller. If you don't do this, the problem never gets small enough to solve!
  2. Solve the smallest problem. (base case(s))
  3. Combine the results properly. This is required to arrive at a correct solution.

Problem 1 (easy peasy)

Let's build a pyramid! Say at the top level we have one block, at the second we have two, thrid we have 3 and so on. Your boss wants you to write a function that will tell him how many blocks will be needed to make a pyramid of a given height.

example, a pyramid of height 3 will need 6 blocks

  X
 X X
X X X

Starter code:

public int howManyBlocks(int levels) {
}

Problem 1 (easy peasy)

Answer theese questions when you're done:

  • How many times was that function called?
  • What was/were your base case(s)?
  • How would you make this itterative? Which would be faster?

Trees

"In computer science, a tree is a widely used abstract data type that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes."
https://en.wikipedia.org/wiki/Tree_(data_structure)

  • In this class you'll mainly be working with binary trees
    • binary trees are trees where each node has at most two children
    • Left node, Right node
    • In recursion, we look at those nodes to preform sub-problems

Problem 2 (10 minutes)

The height of a binary tree is the number of edges between the tree's root and its furthest leaf. Write a fucntion to find the height of a binary tree. Remember : Identify the base case, Make the problem at each step, Combine results appropriately.

Starter code:

/*
  class Node 
    int value;
    Node left;
    Node right;
*/

public static int getHeight(Node root) {
  // Write your code here.
}

Problem 3 (10 minutes)

Given binary trees x and y, decide wether or not x,y are identical. Remember : Identify the base case, Make the problem at each step, Combine results appropriately.

Starter code:

/*
  class Node 
    int value;
    Node left;
    Node right;
*/

public static boolean isIdentical(Node x, Node y) {
  // Write your code here.
}

Want more practice?

Solutions

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

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

1)

public int triangle(int rows) {
  if (rows == 0) {
    return 0;  // Base Case
  }
  
  return rows + triangle(rows-1); 
}

2)

This is the type of question to go on a quiz/hw , so I don't want to be the one to leak it

3)

This is the type of question to go on a quiz/hw , so I don't want to be the one to leak it