CSC153 2004S, Class 36: Arrays
Admin:
* Read O1: Designing Objects
* Rest of week: OOD (Generalities; Inheritance; Polymorphism)
* Questions on homework 5? Due Friday at 10:00 a.m.
* Will anyone else use our calculator class? What protection levels should we use? Answer: Consider it a challenge to design what you think is best. A "big long main" is acceptable.
* Will I get it done if I start at 5pm on Thursday? Probably not.
* Should I do it anyway? Yes.
Overview:
* Intro to arrays
* Arrays in Java
* Arrays and Fibonacci
* Box packing
Arrays (a lot like Scheme's vectors)
* Integer-indexed collections of values
* Design decisions:
* Homogenous (same type) or heterogeneous (possibly different types)
* User-defined range of indices vs. fixed range of indices (based on size)
* Resizable or fixed size?
* Dimensionality: Single dimension or multi-dimension
* Syntax: Special syntax or normal procedure call (method invocation) syntax
* Scheme
* Heterogeneous
* Fixed range [0 ... size-1]
* Fixed size
* Single dimensional
* Normal syntax
* Java Arrays
* Mostly Homogenous
* Fixed range [0 .. size-1]
* Fixed size
* Multi-dimensional
* Special syntax
* Java Vectors
* Hard to say: Only store objects
* Fixed range [0 .. size-1]
* Dynamic size
* Unidimensional
* Normal syntax
Syntax and semantics of Arrays in Java
* To turn any type into an array type, add square brackets afterwards
int[] grades;
* To create an array, use
new TYPE[SIZE]
int[] grades = new int[7];
* There's some ugly alternate syntax, like
int grades[7];
* To access a value in an array:
NAME[INDEX]
* To assign to a cell in an array
NAME[INDEX] = EXPRESSION
* Alternate initialization (with values)
int[] grades = { 82, 73, 94, 65 };
* Note that you can create arrays on the fly, which can be useful
* You can determine the length of an array with
NAME.length
How arrays are useful: Improve algorithms
See Fib.java
* What's wrong with this strategy for computing Fibonacci numbers?
fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2) for n >= 2
* Will take "a long time": O(2^n) (close, but not particularly so)
* How can we improve this strategy?
* Time/space tradeoff: Use more space to save time
* Create an array to "cache" (remember) values of fib already computed.
* Instead of doing a recursive call, we can check the cache.
* Expected time O(n), since each cell will be filled in once and checked at most three times (cell k is checked by k+1, k+2, and maybe by itself)
* You can also get rid of the recursion and compute it iteratively left-to-right (but then you wouldn't have learned the cool caching technique)
* The technique of caching values of recursive calls is valuable and called "dynamic programming"
New problem: Bin packing
* You have a bin (e.g., a UPS truck)
* You have lots of things to go in the bin (e.g., packages); They vary in size and shape and such
* Not everything will fit
* Assume each thing has a value
* Goal: Choose a subset of things that fit and maximize the value of that subset
Simplifying assumptions:
* For any particular value/size combination that you have one package, you have aribtrarily many packages
* We care only about volume, not about shifting things around to fit
* Volumes are integers
How would you solve this problem?
* Start by giving things "weighted values" (value/weight).
* Greedy solution: Repeatedly take the things with the highest weighted value and shove 'em in your truck.
* Greedy solution fails
* Assume truck holds 100 units
* High value thing: 80 units, value 81
* Low value thing: 33 units, value 33
* Pretty well, but not optimal
* Computer scientists are closer to mathematicians than physicists
* Exhaustive search: Try every possible combination and find the best one
* Correct
* But very slow
for each kind of package:
assume you take one of that package
compute the best fit for the remainder (recurse)
chose the best of those solutions
* Dynamic programming: Remember the recursive solutions
You can use a similar technique to minimize the number of stamps for a given price
A new optimization technique: What's the best day to go to Sushi Popo?
* Assume we leave at 11:00 and return by 3:00
* Monday: 3 conflicts
* Tuesday: 2 conflicts
* Wednesday: 4 conflicts
* Thursday: 4 conflicts
* Friday: 4 conflicts
* Tentative: Monday of finals week
* We'll work on cars (maybe bring Jesse)