CSC151 2010S, Class 36: Vectors

Overview:
* Assignment 7: Fractals.
* Thinking about Data Types.
* Problems with lists.
* A solution: Vectors.
* Behind the scenes: How Scheme implements 
  vectors.
* Important vector procedures.

Admin:
* Reading for Monday: Pairs and Pair Structures.
* Today will be a "Sam speaks for too much time" day.
* Prospies! (I hope.)
* EC for today's overcrowded lunch with Dan Garcia. 3821
* EC for tonight's opening reception and/or talk with Kluber and Simon.
* Any thing else of interest?
* Dag new fighter day 4-6 Macasdfasd field.

Algorithms need
* The ability to name values
* Procedures/functions/subroutines
  Things that take values as inputs (parameters) and
    output other values
  Encapsulate computation
* Conditionals, like ifs and things
  Um, a means of testing things and then
  making decisions based on those tests
* Loops, the ability to repeat operations
* UM, Universal Manure
* Built in types and operations on those types

Assignment 7
* Cool triangle things
  How do I use recursion?
  Base case: n is 0
    Just draw the line
  Recursive case: n > 0
    Draw the line 1/3 of the way,
    Turn left by radfasdf degrees
    Draw a line 1/3 of the way,
    Turn right by asdfasdf degreees
    Draw a line 1/3 of the way,
    Turn left by mmm degrees
    Draw a line 1/3 of the way
 "Draw a line" means "Draw a line using the same algorithm"

Types: Basic kinds of values and the operations on those values (your basic building blocks)
* Very basic types which are a finite set of values, often built by listing the values
  * Characters
  * Colors: 
* More complex types that we may think of as being defined recursively
  * drawings as values
  * integers
    0 is an integer
    for any integer i, (increment i) is an integer
  * Lists
* Types that are used to collect other values
  * Specific kinds of values
    * Images collect colors
    * Strings collect characters
  * Lists
  * Arbitrary kinds of values
  * Vectors (about to learn)
  * Trees (about to learn)
  * Graphs (take some other CS courses)

Lists are wonderful because the collect values
* But you can't change the values
  * You have to build new lists
* And we don't know a lot about them
  * What types do they contain?
  * How long are they?
  * we can figure these things out
    * But it's costly.
* It's hard to find specific elements

Vectors solve all of these problems
* Mutable: You can change values (with the help of Prof. Xavier)
* Quick to do some basic things, such as grab the nth element or find the length

But ... there must be a catch
* You can't grow or shrink vectors