Transcript Analyzer Zoom .vtt → who said what

CS 201 Week 5: Open addressing (sample)

sample-class.vtt · 07:53 long · 7 speakers · 49 lines · summaries by claude-haiku-4-5 via Fire

6 lines may be two people on one connection. Review them.

Speakers

Dana Reyes
26 lines 663 words 59% of words 04:08 talking
Summary
Dana Reyes taught the CS 201 class on open addressing in hash tables, covering linear probing, primary clustering, quadratic probing, double hashing, and the deletion problem with tombstones. She explained how open addressing differs from chaining, walked through concrete examples of key insertion, and discussed load factor thresholds and rehashing strategies.
Contribution
Dana introduced and explained the concept of tombstones as a solution to the deletion problem in open addressing: instead of emptying a slot (which breaks lookup), you leave a special marker that says something used to be here so probing continues, and insert can reuse tombstones while lookup skips past them.
Priya Patel
7 lines 179 words 16% of words 00:57 talking
Summary
Priya discussed collision resolution strategies in hash tables, including chaining with linked lists and open addressing with various probing techniques. She explored how table size and step size relate to probe sequence coverage, and worked through a concrete example of quadratic probing with specific insertions.
Contribution
Suggested that making the table size a power of two and forcing the step to always be odd would ensure the step and table size are always coprime, which would guarantee full table coverage during probing.
Marcus Lee
4 lines 95 words 8% of words 00:31 talking
Summary
Marcus asked clarifying questions about open addressing hash tables, including the problem set deadline, whether the second hash function in double hashing must be relatively prime to the table size, and what load factor triggers rehashing. He also worked through a concrete example of inserting values (10, 17, 24, 3) into a hash table of size 7 using linear probing.
Contribution
Asked whether the second hash function in double hashing needs to be relatively prime to the table size, which prompted discussion of an important property of double hashing.
Room 214 Zoom Room
4 lines 67 words 6% of words 00:26 talking
Summary
The participant (speaking as part of a group in Room 214) raised concerns about clustering in open addressing hash tables, asking whether clusters grow larger once they form and whether tombstones accumulate and slow down the table over time.
Contribution
Asked a clarifying question about whether clusters keep growing once they start forming, and separately raised a concern about tombstone accumulation degrading table performance.
Jordan's iPhone
3 lines 52 words 5% of words 00:20 talking
Summary
Jordan explained that the worst case for open addressing hash tables is O(n) when all elements hash to the same bucket, and identified a critical issue with deletions in open addressing: lookups fail because probing stops at empty slots.
Contribution
Pointed out that deletions break lookups in open addressing because the probe sequence terminates at empty slots, causing the algorithm to incorrectly conclude that keys don't exist when they're actually further along in the table.
Grace Kim
3 lines 51 words 5% of words 00:20 talking
Summary
Grace Kim joined late due to technical difficulties and asked about the problem set. She inquired about whether a fixed prime table size was acceptable for part three of an assignment.
Contribution
Asked a clarifying question about problem set requirements: whether part three requires supporting a growing table size or if a fixed prime table size is allowed.
Unknown caller
2 lines 24 words 2% of words 00:10 talking
Summary
Leo called in via phone because their internet was out and wanted to let the class know they would be listening in.
Contribution
Informed the class that they were joining by phone dial-in due to internet outage and would participate by listening.

Possibly two people on one connection

Heuristic flags for a human to check: someone addressing the labelled speaker by name, answering their own question, or introducing themselves under someone else's label.

03:16
Priya PatelYeah, I read that Python uses a power of two table but it doesn't do plain linear probing. It mixes in the higher bits of the hash with this perturb thing so the probe sequence spreads out.Priya Patel answers their own question within seconds — possibly a second voice
03:37
Priya PatelYeah, sorry, it's Sam here, we're sharing a laptop today because mine's in the shop.Someone introduces themselves as "Sam" on Priya Patel's connection
04:29
Room 214 Zoom RoomThis is Tom. Doesn't that mean the table fills up with tombstones over time and gets slow?Someone introduces themselves as "Tom" on Room 214 Zoom Room's connection
06:23
Priya PatelNo, you go. Okay, so 10 goes to 3. 17 starts at 3, plus one is 4. 24 starts at 3, plus one is taken, plus four is 7, mod 7 is 0. And 3 tries 3, then 4, then 0, then plus nine is 12 mod 7 which is 5.Priya Patel answers their own question within seconds — possibly a second voice
06:58
Unknown callerIt's Leo, my internet is out, so I'm calling in. I'll just listen.Someone introduces themselves as "Leo" on Unknown caller's connection
07:34
Room 214 Zoom RoomGrace, it's Aisha, are you coming back to the room after?Someone introduces themselves as "Aisha" on Room 214 Zoom Room's connection
Full transcript (49 lines)
00:02
Dana ReyesOkay, let's get started. Can everyone hear me? Give me a thumbs up in the chat.
00:08
Dana ReyesGreat. So today is week five, and we're picking up where we left off on hash tables. Last time we did chaining. Today is open addressing.
00:17
Marcus LeeSorry, before we start, is the problem set still due Friday or did that move?
00:23
Dana ReyesStill Friday at midnight. Okay, quick warm-up. Who can remind us what happens with chaining when two keys hash to the same bucket?
00:34
Priya PatelUm, you just keep a linked list at that bucket, so both keys live in the list, and lookup walks the list until it finds the key.
00:43
Dana ReyesExactly right. Thank you, Priya. And what does that cost us in the worst case?
00:49
Jordan's iPhoneWorst case is O of n, if everything lands in the same bucket.
00:56
Dana ReyesRight. And who was that? I just see "Jordan's iPhone." Jordan, is that you?
01:04
Jordan's iPhoneYeah, sorry, it's Jordan. My laptop died so I'm on my phone today.
01:09
Dana ReyesNo problem. Okay, so open addressing. The idea is there are no lists. Every key lives directly in the array. When you collide, you probe for another slot. The simplest version is linear probing: try the next slot, then the next, and wrap around.
01:25
Dana ReyesSo if I insert keys that hash to 3, 3, and 4, the first goes in slot 3, the second gets bumped to slot 4, and the third, which wanted 4, now goes to 5. Does that make sense?
01:38
Room 214 Zoom RoomSo doesn't that mean the clusters just keep getting bigger? Like once you have a run of full slots, anything that lands in it makes it longer.
01:46
Dana ReyesYes! That's called primary clustering, and it's the big weakness of linear probing. Great observation. Who's in the room, by the way? I just see Room 214.
01:59
Room 214 Zoom RoomThat was Aisha. There's three of us here, me, Tom, and Grace.
02:06
Dana ReyesOkay, thanks Aisha. If you three can each say your name before you talk, that'll help me later when I go through the transcript.
02:15
Dana ReyesSo the fix for primary clustering is to probe further away. Quadratic probing tries slot h plus one, then h plus four, then h plus nine. Double hashing uses a second hash function to decide the step size.
02:29
Marcus LeeWith double hashing, does the second hash have to be relatively prime to the table size? I remember something like that from the reading.
02:37
Dana ReyesGood memory, Marcus. Yes. If the step size shares a factor with the table size, you'll cycle through only part of the table and might never find an empty slot, even when one exists. That's why people often use a prime table size.
02:52
Priya PatelSo could you just make the table size a power of two and force the step to always be odd? Then they're always coprime.
03:01
Dana ReyesYes, that's a really common trick. Power of two tables let you replace mod with a bitmask, and an odd step is guaranteed to be coprime. Nice.
03:11
Priya PatelWait, so is that what Python does for dictionaries? Sam, didn't you look that up?
03:16
Priya PatelYeah, I read that Python uses a power of two table but it doesn't do plain linear probing. It mixes in the higher bits of the hash with this perturb thing so the probe sequence spreads out.Priya Patel answers their own question within seconds — possibly a second voice
03:29
Dana ReyesThat's right, the perturb shift. That's a great example of a real system solving the clustering problem. Thanks, both of you. Are you two on the same computer?
03:37
Priya PatelYeah, sorry, it's Sam here, we're sharing a laptop today because mine's in the shop.Someone introduces themselves as "Sam" on Priya Patel's connection
03:43
Dana ReyesTotally fine. Just say your name first if you can.
03:48
Dana ReyesOkay, now deletion. This is where open addressing gets tricky. If I just empty a slot, what breaks?
04:06
Jordan's iPhoneLookups for keys after it break, because the probe would stop at the empty slot and think the key isn't there, even though it's further along.
04:16
Dana ReyesExactly. So instead we leave a tombstone, a special marker that says something used to be here, keep probing. Insert can reuse tombstones, but lookup has to skip past them.
04:29
Room 214 Zoom RoomThis is Tom. Doesn't that mean the table fills up with tombstones over time and gets slow?Someone introduces themselves as "Tom" on Room 214 Zoom Room's connection
04:36
Dana ReyesYep. Which is why you rehash periodically. You count tombstones as part of the load factor, and when the load gets too high you rebuild the table and drop all the tombstones.
04:50
Marcus LeeWhat's a good load factor to rehash at for open addressing? For chaining you said like one.
04:58
Dana ReyesFor open addressing you want to stay well below one, because performance falls off a cliff as the table fills. A lot of implementations rehash around 0.5 to 0.75. Python dicts use two thirds.
05:12
Grace KimSorry I'm late, I had trouble with the room link so I joined from my own laptop. Did I miss the problem set announcement?
05:20
Dana ReyesStill due Friday at midnight. Marcus asked the same thing. Welcome, Grace.
05:26
Dana ReyesAlright, let's do a quick exercise. Table size seven, linear probing, hash is key mod seven. Insert 10, 17, 24, and 3. Where does each one go? Take a minute.
05:58
Marcus Lee10 mod 7 is 3, so slot 3. 17 mod 7 is also 3, so it goes to 4. 24 is 3 again, so 5. And 3 mod 7 is 3, so that goes all the way to 6.
06:09
Dana ReyesPerfect. Four keys, all in one cluster. That's the clustering problem in miniature. Does anyone want to try the same thing with quadratic probing?
06:18
Priya PatelI can try. Sam, do you want to do it?
06:23
Priya PatelNo, you go. Okay, so 10 goes to 3. 17 starts at 3, plus one is 4. 24 starts at 3, plus one is taken, plus four is 7, mod 7 is 0. And 3 tries 3, then 4, then 0, then plus nine is 12 mod 7 which is 5.Priya Patel answers their own question within seconds — possibly a second voice
06:37
Dana ReyesThat's right, and notice the keys are spread out more: 3, 4, 0, 5 instead of 3, 4, 5, 6. That's the point.
06:47
Unknown callerHi, sorry, this is a phone dial-in, can you hear me?
06:52
Dana ReyesWe can hear you. Who is this?
06:58
Unknown callerIt's Leo, my internet is out, so I'm calling in. I'll just listen.Someone introduces themselves as "Leo" on Unknown caller's connection
07:05
Dana ReyesOkay, thanks Leo. So, wrapping up. For Friday's problem set, part three asks you to implement open addressing with tombstones and resizing. Start early, the deletion edge cases are where people lose points.
07:18
Grace KimFor part three, are we allowed to use a fixed prime table size, or do we have to support growing it?
07:26
Dana ReyesYou have to support growing it. Double the size and round up to the next prime, or use powers of two with an odd step, either is fine.
07:34
Room 214 Zoom RoomGrace, it's Aisha, are you coming back to the room after?Someone introduces themselves as "Aisha" on Room 214 Zoom Room's connection
07:40
Grace KimYeah, I'll be there in five.
07:45
Dana ReyesGreat. Office hours are Thursday two to four. That's it for today. Thanks everyone, good discussion.