You are being recorded and transcribed.
Approximate overview
Academic/Scholarly
Cultural
Peer
Wellness
Misc
AssociativeArray class.AACCategory primarily wraps
AssociativeArray in that its primary functionality requires us to
call AssociativeArray methods).Once again, a reminder that Without looking at any resources (e.g., readings, labs, your notes), write down everything you know that might be useful for this assignment exists to encourage you to start dumping your brain. You can also use it as an opportunity to do “free writing” on some of the key methods or classes.
Also: I ask you do to the pre-reflection to encourage you to read the assignment carefully a few days before it is due. Responses that say “I haven’t really read it” should not suffice.
A lot of you seem to be reluctant to get started. What would help you? Should I reserve time on Fridays for demoing how to get started?
Also: This assignment is less scary than it looks!
mg/Please don’t clutter your repo with unnecessary files (e.g., .class).
.DS_store.
Demo
What should we do about the things on Gradescope that you told us not to submit anything for.
Remind me and I’ll delete them.
Sam takes forever to grade. How will I know whether to redo an LA on the next set?
Assume you’ll do them alternating weeks.
When we write to a file in mappings, where does that file go?
Probably the top level. Try it and see. You get something like
AACMappings-New.txt
What’s AACMappings.txt?
It’s the file that gets provided to your constructor.
When should you use an adapter and when should use inheritance?
Wrapper/adapter: When you have a specification for what methods you need to provide, and you have something with similar methods, but different names.
If you use inheritance for adapting, you’re providing not only the new methods, but the inherited methods, too.
You can adapt multiple things, you can only inherit from one.
Our goal as programmers / computer scientists is to build algorithms that (help us) solve problems. We also build data structures to help with that.
We want to know things about our algorithms, so that we can, for example, decide which algorithm is best for our particular problem.
Key ways we analyze algorithms:
int mid = (lb + ub) / 2;We need techniques to talk about the running time and space usage of algorithms.
Important issues that come into play
Big-O, usually notated as O(f(n)). The time or space graph for a function is bounded above by some constant times f(n), for sufficiently large inputs.
Big-Omega: The time or space is bounded below
Big-Theta: Bounded above and below by the same function.
In 207, we’ll do informal analyses of these things (mostly Big-O), in 301, you’ll do more formal analyses.
Most computer programmers use Big-O a lot like like “approximately Big-Theta”.
carfoo[i](last lst)(index-of val lst)find-key(key) - Note that you won’t always have to do twice as
much work. Maybe the key is at the beginning. But you might have
to search the whole array, and we’re doing an upper bound.As good computer scientists, we should analyze our algorithms carefully and, once we’ve analyzed an algorithm, ask “Can we do better?”
When we get really good, we prove that we can’t do any better.
Iterative algorithms are algorithms in which we handle repetition with loops rather than recursion.
In general, we analyze iterative algorithms by “counting steps” as best we can.
int find(K key) throws KeyNotFoundException {
for (int i = 0; i < this.size; i++) {
if (this.values[i].key.equals(key)) {
return i;
}
}
throw new KeyNotFoundException(key.toString + " does not exist");
} //
Since I may do the body of the loop this.size times, I’d call this
an O(n) algorithm.
int findInSortedArray(K key) {
int lb = 0;
int ub = this.size;
do {
int mid = lb + (ub - lb) / 2;
int ordering = key.compareTo(this.values[mid.key]);
if (ordering < 0) {
ub = mid - 1;
}
else if (ordering > 0) {
lb = mid + 1
}
else {
return mid;
}
while (lb < ub);
throw new KeyNotFoundException(key.toString + " does not exist");
} //
How do we analyze this? We might note that, at ever repetition, the distance between lb and ub halves. Presuming all the parts of the loop are constant time, we can do this in O(logn).
Often, we turn algorithmic loops into what I’d call “analysis loops”. Our loop (or loops) will compute the running time on a particular input, rather than anything directly related to the original algorithm.
int count = 0;
while (n > 1) {
n = n/2;
count++;
}
int count = 0;
for (int i = n; i > 0; i = i/2) {
count++;
}
Analyzing these kinds of loops can be useful.
int count;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
count++
}
} // for
How does the value of `count` relate to `n`? It's in O(n^2). For each
`i`, it runs `n` time. There are `n` repetitions of the outer loops, so
this will be n*n.
int count; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { count++; } // for } // for
How does the value of `count` relate to `n`? It's n(n+1)/2 which is
approximately n*n/2, which is "a constant times n^2". This is also
O(n^2).
int count; for (int i = 1; i <= n; i *= 2) { for (int j = 0; j < i; j++) { count++; } // for } // for ```
Is this O(2.5^n) O(n^2), O(nlogn), O(n), O(logn), O(1) or …?
It’s definitely O(n^100). We want a closer bound.