Final
Lecture book:
Ch 1-6

Multiple choice (mostly)
Fill in the blank (less)
Short answer (even less)

30-50 questions

CS313 - data structures
you have a bunch of data. you want to store it in some way. you want to perform actions upon that data. what are the repercussions of how you store it.

collection of numbers

dense list, or an array

linked list
doubly-linked list
arrows also point to previous item

diff ways of storing same data
why do we care?

remove bob from telephone list
pretend that I have n records, where n is very large, such as 1 million.

Does my computer program "scale"

in an array based list, we would need to shift all elements one up, to take Bob's place (and then Sally's place, etc.)


array is simpler
but, deleting is VERY slow
O(n)

deleting from a doubly-linked list
is
O(1)
constant time


Algorithms:
selection sort:
http://en.wikipedia.org/wiki/Selection_sort
each time, find the smallest item, put it into the appropriate slot
linear search for the smallest item
swap the items
repeat
O(n^2)

insertion sort
http://en.wikipedia.org/wiki/Insertion_sort
repeatedly grow sorted section by taking the next element, shifting over elements greater than it, and INSERTING the new element into the correct slot
O(n^2)