Held: Tuesday, 12 April 2016

Back to Outline 37 - Pairs and Pair Structures. On to Outline 39 - Pause for Breath.

Summary

We consider vectors, an alternative to lists for storing collections of data.

Related Pages

• Reading: Vectors
• Lab: Vectors
• EBoard 38 (Source 38)

Overview

• Problems with lists.
• A solution: Vectors.
• Behind the scenes: How Scheme implements vectors.
• Important vector procedures.

Administrivia

• New partners!
• I will continue to bring you food (or food-like substances) until I am caught up on grading.
• I have not had the opportunity to read much email today. I'm also watching my son play soccer in Pella. If you sent a question, I probably won't get to until 9:00 p.m.

Reminders

• Office hours this week
  • See http://rebelsky.youcanbook.me.
  • Ask me about other available times.
• Tutor hours
  • Sunday, 3-5 p.m.
  • Sunday-Thursday, 7-10 p.m.
• Review Sessions
  • Wednesday at 8pm in CS commons with Sarah (?)
  • Thursday at 8pm in CS commons with Kumar.
  • None with Sam this week

Upcoming Work:

• No reading for tomorrow.
• Lab Writeup:
  • Send email titled CSC 151 Lab Writeup 38 (Your Names)
  • Do not include the underscores.
  • Send to CSC151-02-grader@grinnell.edu
  • Due before class on Tuesday.

Extra Credit

• Send your reports to rebelsky@grinnell.edu with subject "CSC 151 Extra Credit". (Do not include the quotation marks.)
• Send opportunities to me before class with subject "CSC 151 EXTRA CREDIT OPPORTUNITY!"

Academic / Artistic

• Talk Wednesday, 4pm, ARH 302
• Talk Thursday, 4:15 pm, ARH 102, The Stability of Value-added Measures of Teacher Effectiveness Derived under Different Growth Models
• Student Research Symposium this week
• Symphony Orchestra with Dave Stamey, Herrick. April 16, 7:30-9:00 p.m.
• Any of the fora on the report from the Residential Learning Task Force. (Formal announcement forthcoming.)
  • April 15: Open task force meeting, 1:00-2:30pm in JRC 209
  • April 18: Listening session, 8:00-9:00pm TBD
  • April 22: Open task force meeting, 1:00-2:30pm in JRC 209
  • April 26: Listening session, 6:00-7:00pm TBD

Peer

• Lords of the Flies, 7:30 pm April 22nd, 2:00 pm April 23rd, 2:00 9pm April 24th. (Only 50-60 tickets per show)
• ISO, Saturday, April 16, 7-9 p.m. Various classmates performing in the first half. Second Annual Contra into Spring Dance, April 22nd, Main Quad, 7:30 p.m.

Miscellaneous

• Host a prospective student this coming weekend.

Regular Peer

• Social Dance Workshop Tuesdays 7:00-8:00 in Bucksbaum Dance Studio
• Post-break ExCo on British Politics Wednesdays at 8:00 in JRC 203.
  Just show up; you don't need to sign up.
• Pun club Saturdays at 4pm in Younker
• Electronic Potpourri on KDIC Fridays at Five
• Space Odyssey KDIC Fridays at Six
• Bollywood, Fridays, 7:30-8:30, Younker
• Effective Altruism club, 2:30-3:30 Sundays in JRC 226.

Misc

Far in the Future

• Adaptation of Rushdie's East West. Early May.

Questions

What was yesterday's writeup?

Exercise 3.

What should rac and rcd return when given null as input?

What do car and cdr return when given null as input?

What's wrong with my stencil procedure?

Most common answer: You don't have to fit everything into one let or letrec. You can nest forms of let.

Second most common answer: You need to recompute the random column and row at each repetition. Think about your ordering of operations.

Can you demo image-set-pixel!?

Sure.

Can you explain the formula for problem 6?

The area of a circle is pirr. If the radius is 1, the area of a circle is pi. If it's a quarter circle, the area is pi/4. We're approximating the area of the quarter circle. We can then run the formula backwards to get pi.

_I've written irgb-closest using that "doubly recursive method" which we've seen is horribly inefficient. Will you penalize us for that?

Yes. Lots! (If I'm in a good mood when grading, and you have nothing else wrong with your solution, you'll be lucky to get a 6/10 on that problem.)

Data Types

• At the start of the semester, we decided that "basic values and operations on those values" are key to writing algorithms.
  • We tend to use the word "type" to express these two concepts.
• We've seen a variety of characteristics of types in 151.
  • Some types are defined in terms of a list of possible values or a simple construction method: Character, Boolean, RGB color, etc.
  • Some types that can potentially be defined recursively: Drawings-as-value, Maybe integers, Lists.
  • Some types are designed to collect other kinds of values: Lists. (Okay, maybe that's it for now.)
• We're about to learn a few more. Vectors today. Pair structures (particularly trees) on Monday.

List Deficiencies

• Now that we've worked with lists for a while, we've identified some things that make lists inappropriate for some situations.
  • List are expensive to use; to find the length of a list or to access an element late in the list, you need to cdr down the list.
  • Lists are fixed; you can't easily change an element of a list.
• At the same time, there are some advantages to lists:
  • Lists are dynamic; it is easy to grow and shrink a list.
  • Lists are inherently recursive; the type is defined recursively.
  • Lists are simple; you can build almost every list operation through just a few basic operations (car, cdr, null, and null?).

An Alternative: Vectors

• Vectors provide an alternative to lists.
• They have two primary advantages:
  • Vectors are indexed: You can quickly access elements by number.
  • Vectors are mutable: You can change the elements of a vector.
• In order to obtain these benefits, vectors lack some key features of lists. In particular,
  • Vectors are static: Once you've created a vector, you cannot change its length.
• Some key vector procedures:
  • (vector val1 ... valn): Create a vector
  • (make-vector length val): Make a vector of specified length, with duplicates of val as the contents.
  • (vector-ref vector position): Extract a value from a vector.
  • (vector-set! vector position newvalue): Change an element of a vector.
  • (vector-length vector)

Implementing Vectors

• To be done live in class: Memory layout and more.

Lab

• Do the lab