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