Eboard 09 (Section 1): Dictionaries and Associative Arrays
You are probably being recorded (and transcribed) [at least if Sam is here and can get the technology working]
Approximate overview
- Preliminaries
- Notes and news
- Upcoming work
- Tokens
- MP4 / Design challenges
- Questions
- Work on MP3/MP4
Preliminaries
News / Etc.
- I’m still here. I’m unsure about whether I’ll be here on Tuesday.
- Some time today, you should receive an invitation to join a testing
repository on GitHub. Please make sure to accept that invitation.
- If I don’t respond to email within 24 hours, it’s probably lost in
my mailbox. Email again.
- Warning! We’ll be spending a lot of time talking about MP3.
- Warning! The upcoming work was rearranged after class.
Struggles
Comment from student: “I feel like I’m struggling.”
- Many of you are. It’s the nature of the beast. Semi-(un)cooperative tools
and a (fill-in-adjective) professor don’t help.
- Survey!
- I feel like I’m struggling a lot in 207 [7]
- I feel like I’m struggling a bit in 207 [9]
- I don’t feel like I’m struggling in 207 [3]
- I worry that folks aren’t asking enough questions. You really shouldn’t
spend more than five or ten minutes stuck on a problem before you reach
out for help.
- For example, I hear many people had difficulty with “the parameters
can appear in (almost) any order on MP1”. Yet I received no questions
on that issue.
Upcoming work
- TODAY, 2024-09-26 @ 10:30 p.m.
- Friday, 2024-09-27 @ 10:30 p.m.
- Submit Post-reflection for MP3 on Gradescope.
- Do this individually.
- Recommend that you submit immediately after submitting the MP
- Sunday, 2024-09-29 @ 10:30 p.m.
- Monday, 2024-09-30 @ 10:30 pm.
- No readings to submit.
- No lab writeups to submit.
- Submit SoLA 3
- Wednesday, 2024-10-02
Tokens
If you’d like to suggest token events, please let me know in advance of
class.
Academic/Scholarly
- Thursday, 2024-09-26, 11:00 a.m.–noon, JRC 101.
Scholars’ Convocation:
Anthony Pinn - “Thoughts on Why Music Matters for the Study of Religion”
- Thursday, 2024-09-26, 4:00–5:00 p.m., Science 3821 (I think).
CS Extras: Study abroad for CS majors
- Sunday, 2024-09-29, 7:00–9:00 p.m., Science 3819.
Mentor Session
- Tuesday, 2024-10-01, Noon–1:00 p.m., JRC 224A (Day PDR).
CS Table
Cultural
- Friday, 2024-09-27, 7:00–9:00 p.m., Wall Theatre.
Neverland Players
- Saturday, 2024-09-28, 2:30–4:30 p.m., Wall Theatre.
Neverland Players
- Saturday, 2024-09-28, 7:00–9:00 p.m., Wall Theatre.
Neverland Players
- Sunday, 2024-09-29, 2:30–4:30 p.m., Wall Theatre.
Neverland Players
- Tuesday, 2024-10-01, 11:00a.m.–Noon, Bucksbaum 131.
Royce Wolf Recital
Multicultural
- Friday, 2024-09-27, 4:00-5:00 p.m., HSSC N1170 - Global Living Room.
Middle of Everywhere
- Tuesday, 2024-10-01, 1:00–2:15 p.m., Steiner 205.
Crip SpaceTime watch party
Peer
- Grinnellephants in Small Pop (Mini-soda) this weekend.
- Friday, 2024-09-27, 5:30–8:30 p.m., Natatorium.
Men’s and Women’s Swimming Time Trials
- Friday, 2024-10-04, 5:30–8:30 p.m., Natatorium.
Scarlet and Black
- Monday, 2024-09-30, 8:00–10:00 p.m., Bob’s Underground.
Open Mic Night
Wellness
- Tuesday, 2024-10-01, 4:30–6:30 p.m., BRAC P103 (Dance Studio).
Wellness Yoga
- Tuesday, 2024-10-01, 4:30–6:30 p.m., ???.
Forest Bathing (signup required)
Misc
- Friday, 2024-09-27, 7:30–10:00 p.m., Central Park.
Dessert and Dance Reception for Renfrow Hall
- Saturday, 2024-09-27, Noon–1:00 p.m., Renfrow Hall.
Renfrow Hall Dedication
- Friday, 2024-10-04–Sunday, 2024-10-06. JRC 101.
Pioneer Weekend
Other good things (no tokens)
- Friday, 2024-09-27, 6:00–8:00 p.m., Darby Gym.
Volleyball vs. Central
- Saturday, 2024-09-28, 11:00 a.m.–1:00 p.m., Springer Field.
Men’s Soccer vs. Lake Forest
- Saturday, 2024-09-28, 1:30 p.m.–3:30 p.m., Springer Field.
Women’s Soccer vs. Lake Forest
- Tuesday, 2024-10-01, 4:30–6:30 p.m., Springer Field.
Men’s Soccer vs. Knox
- Tuesday, 2024-10-01, 7:00–9:00 p.m., Darby.
Volleyball vs. Beloit
- Wednesday, 2024-10-02, 4:00–6:00 p.m., Springer Field.
Women’s Soccer vs. Knox
Mini-project 4
TLAs
- ADT: Abstract Data Type
- SAM: Strategy, Applications, Methods
- AAA: Arrangement, Algorithms, Analysis
- TLA: Three Letter Acronym
The ADT (SAM), which we’ll call “Dictionary”
We are designing an ADT similar to the association lists or hashes that you may have learned in CSC-151.
Strategy
Generalize arrays so that we can use “any” comparable object as a key,
rather than just integers.
Applications
- A dictionary: We want to use words (strings) to look up definitions (strings).
- A ticket tracker. We use ticket ids (strings) to look up complaints
(complex objects). [Note: Many people would use integers for the ticket
IDs.]
- A calender in which we can look up what is happening (e.g., birthdays)
for each date. So the date is the key, and a list of events is the
associated value.
- Google image search: A string is the key and a list of AI-generated images
is the result. [Note: We generally treat dictionaries as key/value
pairs we store in advance.]
Methods
public class Dictionary<K, V>
V get(K key) throws NoSuchKeyException, NullKeyException
- MIght have a memory issue; we’re leaving that for future programmers.
void set(K key, V val) throws NullKeyException
- Might throw an
OutOfMemoryRuntimeException, but we don’t
have to document that.
- Design question: What happens if we try to store something under
a key we’ve already used?
- Overwrite what is there.
a[1] = 2; a[1] = 42 in arrays
rewrites, we should do the same thing.
- For some applications, we might want give the client a warning.
boolean containsKey(K key)void remove(K key) - Remove the entry with a particular key. If the
key is not in the dictionary, do nothing.
More assignment methods
String toString() - return “{key:value, key:value, key:value, …, key:value}”Dictionary<K,V> clone() - return a copy of the dictionary.
Notes
- Dictionaries are also called “Tables”, “Maps”, “Hashes” (even though they
aren’t always implemented as hashes), and some other things.
The data structure (AAA)
Arrangement
See whiteboard.
Algorithms
get - iterate through the array, looking at the key of each pair
until we find a key that matches, return the associated value. If
we don’t find a matching key, we throw a NoSuchKeyException.
set - (v1) Go to the first empty slot in the array and add the pair there.
set - (v2) Iterate through the array, looking at the key of each pair.
If we find a matching key, replace the value. If we run out of room, expand
the array. If we reach an empty slot, store a new key/value pair.
- We will use
v2
- If we find that there’s not enough room, we will have to resize the array.
- Note that it will help to have a field that keeps track of how many
elements are in the dictionary (vs. how many elements are in the array).
- Note: If
set is just “add a new pair to the end”, we should search
backwards from the end, rather than forwards from the front.
hasKey - Iterate throught the array. If we hit the the end of the
array or an empty spot, return false. If we hit a matching key along
the way, return true.
remove (v1) - Iterate through the array to find the space. Make that point
to an empty key/value pair.
remove (v2) - Iterate through the array to find the space. Put null in
the key and value parts of that pair.
remove (v3) - Iterate through the array to find the space, Put null
in that space.
remove (v4) - Iterate through the array to find the space, swap the
last element into that space and put a null at the end.
remove (v5) - Iterate through the array to find the space, shove everything
down to fill the space.
remove (v6) - Copy the array with everything but that one element.
Analysis
If there are n k/v pairs in the array, how many do we have to look at
to do each of the following? (“About n” or “the same number each time”)
get - As many elements as there are in the array, so linear.
set - As many elements as there are in the array, so linear.
hasKey - As many elements as there are in the array, so linear.
remove - As many elements as there are in the array, plus the additional
effort of removing
- v5 requires that we potentially move all elements (but 1) in the array,
which is a linear algorithm (depends directly on the number of elements
in the array). So does v6.
- v4 requires only a few steps, independent of the size of the array.
We call this a “constant-time algorithm). It seems better. It assumes
we can quickly access the last element.
Notes
remove v1, v2, and v3 are likely to add complications because all of
our other algorithms will need to deal with “holes” in the middle of
the array.- Can we just use the built-in dictionaries? No! We’re working on the
learning objective of “How do I implement those damn things?”
- For Associative Arrays (the Data Structure we’re building), the order
of key/value pairs in the array does not matter.
set, get, and hasKey all have to iterate through the array, so
we should have a helper method. int find(K key), which returns the
index of the matching key and throws a ??? exception if the key is
not in the array.- You could also try to store the things in order by key (assuming that
keys are comparable), although that requires a lot of extra work.
The assignment
See the assignment and the repo.
Testing
Write tests early. Pull other tests. Tell me when you add tests.
Questions
Which version of remove should we use?
Whichever you want. I just wanted to give you practice with SAM/AAA.
Will we have merge conflicts?
I hope not. But part of the point is to get you used to working on a
large collaborative repository.
Questions
Questions on SoLAs
Will you add tips for each LA so that we don’t go in the wrong direction?
Part of the broader goal of the course is that you develop skills at
figuring out how to describe your skills.
But yes, I will try to add tips. I may also add some verbally in class
(or ask you to come up with some).
If we are just having a reading in composition, why do we have
to answer an LA on that?
Because you’ve been dealing with the more basic form of composition
since you started writing objects, and the LA only asks you to
explore the more basic form of composition.
Also: You don’t have to answer tha LA. You can hold off another week
or more.
Questions on MPs
I’m spending significantly more than five hours on mini-projects. Any
suggestions?
Ask for help (preferably on the Questions channel) after you’re stuck for
five minutes. Generally, if you can’t solve it in five minutes, you also
won’t solve it in thirty minutes.
Will the redos for the mini-projects be posted soon?
Yes.
How many group mini-projects will there be?
Probably between three and four.
Do both partners need to turn in a token for a late group mini-project?
Yes.
Other administrative questions
Will we get grade reports soon?
Yes. Probably this weekend.
Questions on MP3
What is a “good commit”?
It has a good description.
It’s not “I committed everything”.
Smaller is better.
Does it count if the commit is on a branch?
Yes.
We couldn’t push and pull. Why?
Next time, send me the message.
If someone has changed the repo, you’ll need to pull before you push.
When you pull, you may get merge conflicts. If you do, read through
the file that has the merge conflicts, choose which code to keep,
add and commit.
Questions on the readings
Is the way inheritance works in a way that pointers do?
Inheritance requires pointers (or “references”) behind the scenes,
but it’s more the concept that you automatically delegate method
calls to the parent class, which I’d say is independent of pointers.
What should I do if I want to inherit from three classes, ex
SmileStudentTeacherChef? (I felt composition + inheritence could
only deal with 2 parent classes.)
Use composition. Composition can handle an arbitrary number of
delegated classes. It’s just a bit more work on your end.
Other questions
Wrapup
If you like, talk to your parter about MP3.
Set up your MP4.