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
Lecture Recap: Steps to making a recursive algorithim
Make the problem smaller. If you don't do this, the problem never gets small enough to solve!
Solve the smallest problem. (base case(s))
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:
publicinthowManyBlocks(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;
*/publicstaticintgetHeight(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;
*/publicstaticbooleanisIdentical(Node x, Node y){
// Write your code here.
}