EBoard 37: Tree recursion and binary search trees

Warning! You are being recorded (and transcribed).

Approximate overview

  • Administrative stuff
  • Questions
  • Lab

Administrative stuff

Why is it so hard to show up to the first class of the day on time?

  • My glasses broke over the weekend. I’ll likely have even more difficulty than normal identifying you.
  • I will be working from home tomorrow. I’ll do my best to respond to questions on email and Teams. All office hours will be on Teams.
  • The CS picnic is coming up. Make sure to sign up.
  • MP8 has now been returned. The redo is due at the end of week 14. (If you turn it in earlier, the graders might be able to get to it.)
  • Congrats to Men’s Tennis on a successful weekend.

The wonders of English

We considered my favorite “stupid valid English sentence” in my other class on Friday. I thought I’d share it with you.

Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo Buffalo buffalo buffalo.

Wasn’t that amazing? You can read about it on my ‘blog.

Token opportunities

Academic/Scholarly

  • Tuesday, 2024-04-30, noon, some PDR. CS Table (topic TBD).
  • Tuesday, 2024-04-30, 7pm, Science 3819. Mentor Session.
  • Thursday, 2024-05-02, 11am, JRC 101. PBK Scholars’ Convocation: Cathleen Kaveny on “Can We Be Civil? Prophetic Indictment and Call-Out Culture in American Public Life”.
  • Thursday, 2024-04-25, 7pm, Science 3819. Mentor Session. Review for the fourth SoLA.

Cultural

  • Most days, 2024-04-xx and 2024-05-xx, 11am-6pm, Grinnell College Museum of Art. BAX 2024. Shouldn’t it be BAE?
  • Friday, 2024-05-03, 4:00–5:00pm, HSSC N1170. Middle of Everywhere.

Peer

  • Saturday, 2024-05-04 (aka “Star Wars Day”), noon–3:00pm, Pioneer Park. Baseball vs. Illinois.
  • Saturday, 2024-05-04 (aka “Star Wars Day”), 2:30–5:30pm, Pioneer Park. Baseball vs. Illinois.
  • Saturday, 2024-05-05, 11:00am–2:00pm, Pioneer Park. Baseball vs. Illinois. (It takes a lot of games to play a whole state.)

Wellness

  • Monday, 2024-04-29, 4:00–5:00pm, HSSC Atrium. Therapy Dogs.
  • Sunday, 2024-05-05, 10:00am–6:00pm, Mac Field. Bubble Soccer. (It takes almost as long as cricket!)
  • Friday, 2024-05-10, 5:00pm–??:??pm, Merrill Park West. CS Picnic! Survey forthcoming.

Misc

  • Monday, 2024-04-29, 4:00–5:00pm, HSSC A1231 (Kernel). Quality Initiative Update: What We’ve Learned By Mapping the Advising Ecosystem.
  • Thursday, 2024-05-02, 4:15–5:30pm, Burling 1st. Conversation with Kathryn Mohrman ‘67.
  • Saturday, 2024-05-04 (aka “Star Wars Day”), 10:00am–11:00pm, Central Campus. The Grinnellian.

Other good things (no tokens)

Note: Softball seems to have moved their games. Or I was very confused when I put this together. Please check the calendar.

  • Saturday, 2024-05-04 (aka “Star Wars Day”), 1:00–3:00pm, Softball Complex. Softball vs. Lawrence.
  • Saturday, 2024-05-04 (aka “Star Wars Day”), 3:00–5:00pm, Softball Complex. Softball vs. Lawrence.
  • Sunday, 2024-05-05, 1:00–3:00pm, Softball Complex. Softball vs. Illinois. (Because three games against the same team in one weekend is absurd.)

Other questionable things (no tokens)

  • Saturday, 2024-05-04 (aka “Star Wars Day”), noon–5:00pm, Cleveland Beach. Alice in Wonderland.

Upcoming work

Questions

Administrative

Will you ever tell us our tokens?

Probably not. You can assume you have enough.

MP9

Could you teach us how to do blends?

I’ll send out something tomorrow.

BSTs

Can you go over the examples from the reading?

Sure.

Misc

Can we start lab now?

Sure.

Lab

Random tree shapes

Sam’s analysis for how many random trees of size 5 there are.

  • Size 0: We can only have one tree of size 0.
  • Size 1: We can only have one tree of size 1.
  • Size 2: We can have two trees of size 2: The one in which the left subtree is nonempty and the one in which the right subtree is nonempty.
  • Size 3: Things start to get complicated here. We could have two values on the left (2 versions), we could have two values on the right (2 versions), or we could have one value on each side (1 version). That gives us five trees of size 3.
  • Size 4: Things get even more complicated here. We could have three values on the left (5 versions) and zero on the right (1 version). We could have two values on the left (2 versions) and one on the right (1 version). We could have one value on the left (1 version) and two on the right (2 versions). And we could have zero values on the left (1 version) and three values on the right (5 versions). 5 + 2 + 2 + 5 = fourteen different trees of size 4.
  • Size 5: Things are complicated enough that I’m switching to a bulleted list.
    • Four on the left (14 versions), zero on the right (1 version): 14 versions.
    • Three on the left (5 versions), one on the right (1 version): 5 versions
    • Two on the left (2 versions), two on the right (2 versions): 4 versions
    • One on the left (1 version), three on the right (5 versions): 5 versions
    • Zero on the left (1 version), four on the right (14 versions): 14 versions
    • If I count right, that gives us forty-two different trees of size 5.
    • Life, the universe, and everything!

Searching trees

What procedures did we see to search trees?

bst-find

binary-tree-contains?

Copyright © Eric Autry, Charlie Curtsinger, Sarah Dahlby Albright, Janet Davis, Nicole Eikmeier, Fahmida Hamid, Priscilla Jiménez, Barbara Johnson, Titus Klinge, Peter-Michael Osera, Leah Perlmutter, Samuel A. Rebelsky, John David Stone, Anya Vostinar, Henry Walker, and Jerod Weinman.

Unless specified otherwise elsewhere on this page, this work is licensed under a Creative Commons Attribution 3.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc/3.0/ or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.

This website was built using Jekyll, Twitter Bootstrap, and the Bootswatch Cosmo Theme.