EBoard 25: Pairs and Lists and Stuff

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

• I hope to catch up on tokenizing this weekend. (I’m also writing 28-or-so LAs, so that may not be possible.)
• Mentor sessions Monday at 5pm and 9pm (I think).
• Congratulations!!!!! to those of you who are getting US Visas. Fingers crossed for the rest of you.
• Apologies for issues with the vector reading. We were using a form of helper recursion that we’ve cut from the class (and I thought last semester’s teacher had cut it from the readings, but they didn’t use the vectors reading).
• If your file uploads on Gradescope look weird, you need to re-save your file as text.
  • File -> Save Other -> Save Definitions As Text…

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 tonight.
• Individual tutors are temporarily unavailable. We’re recruiting more.
  • Don’t let this stop you from requesting one.
  • If you’re willing to share your individual tutor (as in, to do pair tutoring), let me know.

Upcoming activities

Attend (or watch recording within a day or so) and send a one-paragraph reflection asap afterwards.

Only those activities I list count.

• Some time, Monday, Art Museum Thingy
• Noon, Wednesday, 9 December 2020: Community Convesation
• 5:00 p.m. Thursday, 10 December 2020: MIST: The Mathematical Image Synthesis Toolkit. Sam’s research students.

Upcoming work

• Redo of Mini-project 3 (due Sunday the 6th at 10:30 p.m. CST)
• Mini-project 5 (due next Wednesday, December 9 at 10:30 p.m. CST)
  • Please call it language.rkt.
• Readings for Monday
  • Dictionaries and such
  • Give me a day to update
• Quiz Today: Randomness
• Quiz Monday: Pairs and/or Vectors
• SoLA 3 Tuesday (no quiz)

Q&A

Mini-Project 3 Redo

None yet.

Mini-Project 5

None yet.

Randomness

None yet.

SoLA 3

Will you release a set of sample problems?

Yes.

Will the mentors hold sessions?

Yes.

For the tail-recursion problem on SoLA 3, will we be transforming functions we are given?

Yes.

But I won’t give you a template.

Do you really believe that we’ll know enough about dictionaries to do a problem on them?

I hope that after the lab, you will be able to do a problem on dictionaries.

Thank you for the hint about keeping the problem reasonable.

Pairs and Pair Structures

Could you go over the weirdo variants?

(cadr x) is (car (cdr x)) (element 1 of the list)

(caddr x) is (car (cdr (cdr x))) (element 2 of the list)

(cadar x) is (car (cdr (car x))) (element 1 of the element 0 of the list) [we’re dealing with a list of lists]

(caddddddr x) might be (car (cdr (cdr (cdr (cdr (cdr (cdr x))))))) (element 6?)

(caaaar x) might be element 0 of element 0 of element 0 of element 0 of an incredibly nested list.

Vectors

What about vectors makes them different than lists?

In the reading on pairs, you saw that lists are structured like this in memory (e.g., ‘(a b c))

+-+-+   +-+-+  +-+-+
| |*--> | |*-> | |/|
+|+-+   +|+-+  +|+-+
 |       |      |
 v       v      v
 a       b      c

Morals: We have to follow all of the arrows which (a) might make our head hurt and (b) takes some time.

Here’s what the same vector looks like

+-+-+-+
|*|*|*|
+|+|+|+
 | | |
 v v v
 a b c

Important: Just one chunk of memory.

Important: It’s easy to calculate where the reference to the element i is: Start of the vector in memory + i*width-of-a-cell.

Only takes a short calculation to find the ith element, rather than a long one.

Why aren’t lists arranged like vectors?

Adding an element to the front of the list is fast.

Adding an element to a vector requires copying the whole vector.

As an algorithm designer or programmer, you think about which is best for the current situation.

Why doesn’t vector-set! work with vectors defined with '#(x1 x2).

The designers of Racket decided that those would be “constant vectors”, vectors that are immutable. It avoids accidental changes.

Lists are also immutable. You can make new lists from old, but you can’t change an existing list. map and filter make new lists.

How do you get Racket to display a vector you’ve changed with vector-set!?

We type the vector’s name again.

> (define vec (vector "a" "b" "c"))
> vec
'#("a" "b" "c")
> (vector-set! vec 2 "x")
> vec
'#("a" "b" "x")

Miscellaneous

If we are not happy with our MP redo grade, can we redo again?

Sure. Our graders love grading.

I’ll figure out how to manage that.

Quiz

• You know the drill.

Lab

• Don’t forget to review the included procedures!