Outline 38: Vectors

Held: Wednesday, 8 April 2015

Summary

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

Related Pages

Overview

Administrivia

New Partners!
I'm working on making more office hours available. For some reason, http://rebelsky.youcanbook.me is not showing Thursday 3:15-4:30. If you'd like an appointment in that time frame, let me know.
Review sessions Thursday 9am, 1:15pm, 8pm.

I'm going to try to get a good "rough draft" of an answer for each problem, and then make final copies for each answer individually.
Don't fiddle with stuff after you've written it and it works
I plan on starting the more difficult problems first so I have time to get any questions answered.
Work on it each day.
Talk to Sam in person when I have questions.

Scholars Convocation today at noon: Alison Bechdel.
No CS Extras Thursday.
CS Table Friday: Design for User Empowerment http://interactions.acm.org/archive/view/march-april-2015/design-for-user-empowerment

KY's radio show, "We Think We're Funny", 9-10pm Mondays.
Julia's radio show, "The Hot Box". Wednesday night/Thursday morning 1:00-2:00 a.m.
How an admitted student this coming Sunday night (or the following Sunday night)! Contact JMU for info.
Maybe: ISO Show, Saturday night 7-9 pm at Harris. Many live performances.

Wednesday at 4:30. Psychology Alumni Job Talk Series, Alum '##, a Senior Research Analyst from ACT.
Womens Tennis Sunday against Central.
ISO Show, Saturday night 7-9 pm at Harris. Many live performances.
How an admitted student this coming Sunday night (or the following Sunday night)! Contact JMU for info.
Many things the following weeks.

Nothing at present

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.

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?).

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)