EBoard 30: Analysis and Searching

This class will be recorded! Its use is limited to members of the class. Please do not share with others.

Approximate overview

• General administrative stuff [~10 min]
• Q&A [~10 min]
• Quiz [~10 min]
• Lab [~60 min]

Administrative stuff

Notes and news

A Facebook posting from an alum I love (and I love them even when they are critical of me).

Five years ago I finished my first computer science course. I got a D or an F (see? you won’t remember one day) on my first test and came back with an A. Before that, I was told that I couldn’t be an engineer because I was poor, not a boy, didn’t have a computer, etc. I’ve failed countless interviews, and had lots of blunders. Now I’m working at Spotify as a software engineer and doing well. I didn’t do well my first round of evaluations, but I got promoted the next.

I’m mostly here thinking out loud that for every success there’re 1000s of mistakes. I’m striving to learn to be ok with doing things 70% perfectly, instead of obsessing over what I didn’t do right.

And some followup notes.

and i mean still struggling! every day!

but better than to not try at all

and seriously i was so confused…

recursion didn’t really make sensee to me for a long time

and i hate the kybord on my mac

Normal notes

• Additional office hours (email or DM to reserve times)
  • Today, 1-2
  • Monday, 2:30-4:30
  • Tuesday, 2:30-4:30 (4:00-4:30 claimed)
  • Wednesday, 2:30-4:30
  • Thursday, 2:30-4:30
• I’ll also continue to hang out on Teams and email when I can.
• Reminder: Labs always begin with this term. If you don’t see “Fall 2020, Term Two” or something similar at the top, you probably have the wrong lab.
  • Today’s lab should be called “Searching and Analysis”
• CONGRATULATIONS to the Singers in our class on the wonderful performance yesterday.

Tutoring reminders

• Please use our tutors! They like to work.
• Evening tutoring will be available
  • 8-10 p.m. Sundays through Thursdays
  • 3-5 p.m. Sundays
  • In the “Drop in tutoring” channel on the CS team.
  • Sam will generally not be available during these times.
  • We should have two evening tutors on Wednesdays.
  • Don’t forget to cite the evening tutors (and the individual tutors).
• We will have one evening tutor available tonight from 8-10 p.m. Also feel free to support each other; just don’t give away answers.

Upcoming activities

Info:

• Attend (or watch recording within a day or so) and send a one-paragraph reflection asap afterwards.
• Only those activities I list count.
• But you can suggest others.
• Links are in the Announcements channel.
• Unless otherwise specified, these each earn one token.

Activities

• 2:00 p.m. TODAY, 11 December 2020: Newberry Library Talk
• 12:00 m. Monday, 14 December 2020: CS Table (Google vs. Wikipedia)
• 5:00 p.m. Monday, 14 December 2020: Mentor Session
• 9:00 p.m. Monday, 14 December 2020: Mentor Session

Upcoming work

Mini Projects

• Mini-project 5 (due TODAY, December 11 at 10:30 p.m. CST)
• Redo of Mini-project 4 (due Sunday, December 13 at 10:30 p.m. CST)
• Redo of Mini-project 5 (due Sunday, December 20 at 10:30 p.m. CST)

Readings

• No reading for Monday! (That’s a discussion today.)

Quizzes

• Quiz Today: Tree recursion
• Quiz Monday: Binary Search, Analysis, etc.

Other

• SoLA 4 next Wednesday (note different day of week)

Q&A

Mini-Project 5

Any order for experiments?

Fun ones on top.

Administrative stuff

Reading

Yesterday’s lab

Could we go over the traversals?

; Sam predicts: a b d c f h g e for postorder

(define flatten-preorder
  (lambda (t)
    (if (empty-tree? t)
        null
        (append (list (btt t))
                (flatten-preorder (btl t))
                (flatten-preorder (btr t))))))

(define flatten-inorder
  (lambda (t)
    (if (empty-tree? t)
        null
        (append (flatten-inorder (btl t))
                (list (btt t))
                (flatten-inorder (btr t))))))

(define flatten-postorder
  (lambda (t)
    (if (empty-tree? t)
        null
        (append (flatten-postorder (btl t))
                (flatten-postorder (btr t))
                (list (btt t))))))

> (define sample-tree (vector->tree (vector "a" "b" "c" "d" "e" "f" "g" "h")))
> sample-tree
'("e" ("c" ("b" ("a" ◬ ◬) ◬) ("d" ◬ ◬)) ("g" ("f" ◬ ◬) ("h" ◬ ◬)))
> (display-binary-tree sample-tree)
⦿ e
  ● c
    ▶ b
      ▪ a
    ▶ d
  ● g
    ▶ f
    ▶ h
> (flatten-postorder sample-tree)
'("a" "b" "d" "c" "f" "h" "g" "e")
> (flatten-inorder sample-tree)
'("a" "b" "c" "d" "e" "f" "g" "h")
> (flatten-preorder sample-tree)
'("e" "c" "b" "a" "d" "g" "f" "h")

Is there a general pattern for tree recursion?

(define tree-proc
  (lambda (t)
    (if (empty-tree? t)
        *BASE-CASE*
        (*COMBINE* (*PROCESS* (btt t))
                   (tree-proc (btl t))
                   (tree-proc (btr t))))))

Other Questions

Will we get SoLA 3 back before we take SoLA 4?

Yes. As soon as I can?

What is that number in the lower-right-hand corner?

I have no idea.

When am I getting redo grades?

Um. Soon.

Quiz

You know the drill.

Lab

Agh! So many problems.