Video 0: Administrativa & motivation

0:00 Module introduction

0:03 Once again, welcome to Advanced Data Structures. In the first part, I'll quickly run through some organizational bits. If you've done modules with me, then uh this will be similar or will be familiar to you. Uh if not, I'll quickly tell you some of the things we I like to use and why, but I won't spend uh a ton of time on it. So that we can also get a glimpse of the actual material and you can make your decisions. I always try to have one slide with all the key information. Uh Sebastian Wild, that's me. Um Tomyu Nakashima, my postdoc, is not here, but he'll take He's not here today. He's traveling this week. Uh but he will take care of of the tutorials from next week onwards. Um probably will will join the lecture and say hi at least once.

0:57 All the key information is on the module website. And maybe before we move on, let me show you what that looks like. I suppose uh people know how to navigate our uni website. Um you can find us from our department, the working groups at the very bottom. It's alphabetic, so my name comes last. There is the algorithms group, and from there you can go to teaching. From there there's a link here. You can also find it in other ways. Uh so that's the module website. The important part is this table, which has the topics um that I plan to cover. It might change a little bit and the timing might change a little bit. Uh once we get there, there will be exercise uh sheets that pop up in the same table. And uh important part is you can click on these uh sub units once they're filled with life. And that's where the slides are available and where the recordings will pop up.

2:00 And sometimes more things like uh extra sources specifically to that unit I'll I'll put there as well. Um and some extra links down here. We'll come back to that.

2:16 So, anything that can will be on the public website. I just find it more convenient myself and hope that you do, too. Uh we'll also use CampusWire for a Q&A forum. It's a fairly small group, so maybe it's a bit overkill, but it doesn't hurt. It's nice markdown and LaTeX formulas and uh you can help each other. Um I'll show you a bit later what this is. Uh what you need for joining is your Marburg uh email and this PIN. Otherwise, the system doesn't let you in. You've already seen Slido for the questions. And the other part is we'll have some final exam. I guess from the group size, oral exams would be my preference. Uh to be admitted to the exam, you have to achieve 50% of the points. I'm going to go through all of this a little more slowly and a little more in detail, but that's basically the key information. Um So, the goals for today are to see a bit what this module is about and how we approach it.

3:11 Interactive polls

3:22 Um Slido was the first thing. Uh you've already seen the polls. That's uh how I asked you about your courses of studies. The more usual one is a multiple-choice question, but you can also do free text as you've seen. You can use the same tool also for asking questions. Uh sometimes that's uh convenient to just collect questions and then go over them uh at the end entire together.

3:51 I mostly like to use Slido to keep you awake once in a while. Since we're a small group, it's may it may not be as as important. Um for curiosity, let's see what kind of tools people know.

4:17 For some of them, I very much hope that we'll see essentially 100%. Some others, uh I care less. I'm just curious. Anyone still thinking? We had 13 before. But maybe no need to uh wait forever. I'm very happy to see that people know Ilias. This a course a module or a course for for this module uh which you should sign up for because that's where you will hand up hand in your exercises. I I guess people seem to know Slido more. Okay, now it's tied. Fun. Uh cool. So, people also know ChatGPT. I'm not so surprised. Not so many know Campuswire. Uh hope we'll change that. And then there's a few other uh similar LLM-based systems. Uh of course, there's tons more, right? So, it's a bit uh it's annoying to keep up. Mm It's fun how ChatGPT is still somehow dominant. Uh any You want to comment on this? Any specific reasons or is just uh What are you try first you you're stuck with?

6:04 Any any thoughts you want to share on this? They were the first in the market. That's very true. Yeah. Yeah. Uh they were first. Uh they're still good, I guess. Uh Ah, there you go. Depends, I guess, what you what you want to do. Okay. Uh I mean, this this question was just an excuse to wake you up again a bit.

6:30 Course content and goals

6:33 Let's uh have a look at the content of the module. Mhm. My goals are to show you some just beautiful ideas in data structures that are somehow clever and and insightful. Um make something possible that isn't at first clear that it would be possible, but then with the right approach, it works. >> [snorts] >> Um the hope is that after seeing some examples of this, you'll also be able to do this on new problems of a similar type. And it's a master's uh specialization module, so the goal is should also be to bring you close to the state of the art. So, that you would be uh equipped to do research in this area or I mean, get close enough that with a bit of further reading, you're there or depends a bit how how strictly you want to interpret that sentence. But, it's a good goal to have. Uh here's the the rough outline of things I have planned. This is potentially a bit ambitious. I might have to thin out a few of the topics at the end if we run out of time. I was too enthusiastic at this point to kick them out right away.

7:43 Uh but if there's uh some of the last three that you're extremely keen to see, maybe uh you're you'll have to let me know. Um we'll roughly start with fairly elementary data structures. Well, that's what we'll maybe start a little bit today and tomorrow. Um alternatives to the good old binary search trees and um maybe uh also the the reasons why you would maybe not want to use them sometimes. Uh that's the first two chapters in a way. Uh for the for the experts, if you've seen some of this, uh look at at treaps as one example and at splay trees at another, but I'm not sure if you've seen the full glory of the um theoretical guarantees that they have.

8:33 Um I'm sure you've seen some priority queues, binary heaps, etc. Uh maybe someone has tortured you with Fibonacci heaps as well. Uh there's a few more out there that are I think maybe more elegant. Um persistence is kind of time traveling for data structures, very cool. Uh well, it's a fairly light topic. Sounds sounds harder than it is. And then we get into some a bit more advanced and more specialized topics. There's data structures that are better than the general purpose data structures if you know that you're working with integers, with numbers, and assume uh the word RAM model. Again, for the experts, we'll cover all of this in uh in slow pace and detail. The next few are um something from closer to my research area, space-efficient data structures. Uh again, there's mm a few that are very very clean and nice to see as uh an introduction. And then we'll try to get a bit closer to the state of the art in some areas.

9:37 And the last topics are a bit about the machine models that we otherwise assume in in algorithms and how they are maybe um how they need to be adapted.

9:55 Okay, that's the that's the rough plan. The goal would be to cover roughly one of these units per week. And that might be ambitious. We'll see. >> [snorts] >> In all of this, this is a list of areas. Uh in all of this, in a way orthogonal to the topic is you can you can focus on what works well in implementations, or you can look at what is the theoretically asymptotically best possible. I'll strive for the second most of the time because that's uh it's still a theory specialization. But we'll also look a bit at uh implementation concerns, say uh so from the data structures that work well in theory or have good guarantees in theory, we'll we'll look a bit a bit like um at what they could be implemented like.

10:47 Data structures in industry

10:51 And to maybe motivate a bit uh the module in general and data structures in general, let me tell you a few stories of where data structures really saved the day. Um two are examples of tech startups that completely centered around the data structure. Uh maybe you even know about some of these. Akamai is is a I guess one of the first companies that started something like these content delivery delivery networks that now are completely responsible for you being able to stream efficiently uh a lot of a lot of uh data that passes through uh our backbones is essentially video streaming. And if we would send, say, all the Netflix series that all of us watch or any pick any other streaming service, if they would all go through the uh transatlantic cables, they would be completely clocked. So, instead, the content delivery networks set up local data centers closer to you, say, somewhere in Germany, and cache the data that you would want to access.

12:01 But, this is highly nontrivial how to do this efficiently in a way that adapts to how people access uh different parts of the data and uh without hardcoding this. So, it's a somewhat recent thing. Yeah, if you read up about the story. Uh some of the first was was Akamai. Um I think it's a startup out of MIT, and the first kind of theory idea that that kickstarted it was a a type of hashing that is used to uh handle which server stores which piece of data in the abstract. And the challenge that they had to overcome there was that you uh you want this to be resilient if there's servers coming and going because they crash or you want to add more to increase your capacity. If you do that in the standard hashing way with some, say, a hash number hash hash value then modulo the number of servers, then whenever you add a new server, a lot of the hash codes change. And so, all the servers would have to be exchanging the data because they're now responsible for different pieces of the data.

13:11 That doesn't work at all. And so, consistent hashing, the first first piece that they uh invented, is a way uh to circumvent that. And maybe I can even sketch the idea. It's so cute and simple. Uh you imagine a unit circle and now you hash both the data and the servers somewhere randomly onto this um in you know, a real interval between zero and one. We just deliberately say this is this is zero and then it goes around here from zero to one. You have a a random position on this circle for each data item and for each server. And then the consistent hashing scheme just says the data item always goes to the next server in cyclic order. And now if you add another server or if a server drops out, some of the data has to move to a different server, but most don't.

14:17 Very simple, clever idea. Now it's a bit more there's a bit more to it because they also need to deal with uh unequal load. But let's leave it at that. Essentially a data structure that kickstarted this uh large company.

14:34 Another example on a slightly different scale uh less well-known uh is Tokutek. It doesn't exist anymore in this in this way. It's been bought up several times and now things get confusing. Uh but it it was originally a database engine. So this just the storage part and you could use this uh on one of the uh one of the large well-known databases. Um And the innovation here was um a write-efficient B-tree.

15:04 So B-tree, as you know, is the bread and butter data structure for indices indexes in data structures. Uh but if uh if you insert something, you always move down the entire tree and then change something. So it's a lot of writing for a single update. And you can try to cache these updates and bulk updates the nodes that's at the base of this plus then cache oblivious etc. Uh properties that work with the memory better. And at least here I know I know the people that founded it and that they made uh a nice nice uh amount of money out of it.

15:50 Some other examples um are not specific companies but entire applications that essentially became possible because of a data structure. One example is is uh genome wide read mapping DNA mapping. That's what you've essentially done or had done for you for a PCR test during the pandemic. And what you still do with uh genomic analysis. Uh and for that essentially the the data structure behind it is a compressed text index. Of Of the sort we'll we'll come a bit close to this. But you want to see this specifically in detail then you have to wait for the next round of uh algorithms in bioinformatics. And a last example uh are Merkle trees that maybe people know uh are used both in in Git, the version control system, and in Bitcoin. Is a way to efficiently check consistency of data. Uh I think Linus Torvalds said that this is uh without this nothing would work in Git. It's entirely focused around this.

16:58 I also learned when researching into this that Git is fundamentally fun uh in that it completely relies on cryptographic hashing never colliding. If uh if you somehow can make uh the SHA-256 hash collide then Git breaks because it treats two different files as the same. >> [snorts] >> Is essential Git is using the hash of your file as the name of that file. And that's uh mathematically speaking a bit troubling. On the other hand, the chances I mean if if cryptographic hashes are broken, we have other problems than Git no longer recognizing our files. Maybe it's a it's fair game.

17:48 Yeah, well, at least here we can quantify that it's extremely unlikely because the this the size of the hash is very big and nobody is seems to have found a way to force a collision. But it happened before with the previous SHA, so it's not an impossibility.

18:10 I'm trying to show you that although we focus on the theory of data structures, the gap between theory and practice is not that big. A good data structure can, when implemented right, quickly change the practice of computing. And that's what makes it That's part of what makes it so enticing. I also think it's just a lot of clever and beautiful ideas. But both is a a good motivation.

18:40 And maybe you can add another one if you take something from this module and invent something cool, then maybe you're the next bullet on this on this list, right?

18:49 Assessment and tutorials

18:53 Back to the boring stuff. The assessments I already sketched. We essentially have the final oral examination, I would say is kind of clear. Uh that determines the module mark to be admitted. The standard rule, I think that's standard in the department. You need half of all the points from our exercise problems. And two of the sheets you can zero out at most.

19:19 Standard rules. And the tutorials themselves or the exercise sheets themselves are handed in in groups. It's very small group, maybe we don't need four people per group. I think you can handle a few a few more groups. Um all relatively standard stuff.

19:47 As always for master's modules, I consider the marking for the exercise sheets more as a a feedback for you than as a strict check that you followed every single step. So, we'll usually mark for serious attempts and not completely solved. Uh the the point being that it's a it's practice for you prepare you for the exam. Not so much checking on you. That's what the exam's for. Now, we have to talk about about this guy, the elephant in the room these days of AI tools. Uh I've opened the conversation on some most most people have used these tools. Of course, I encourage you to use them and and play with them. Just not for the exercise problems. Uh for the for the following reason, AI is is an exciting tool. It's it's very amazing in some things and can be less amazing in others. Um I'll come back to an example in a minute. But it also makes us lazy. That's um among other things a problem.

20:17 AI tool policies

20:56 So, uh we need people who can check whether the outcome of what an AI produced is actually accurate. Here's an example from before. Um of course I interviewed some some chat assistants about nice data structures applications. And it tried to convince me that precisely what I mentioned before Git has mathematical certainty that the hash is never collide. And it kept insisting until I told it this is nonsense. You're mapping infinitely many strings to a fixed set. There must be collisions. Oh, yeah, you're right. Uh I've I I gave you marketing certainty, not mathematical certainty. But it used literally the words mathematical certainty. So, you have to call out to the systems. And to be able to do that, you need to know your stuff. How do you get there? By practicing it. And so, for the assignments, don't cheat yourself. It's okay if you use it for background research or maybe language editing. Don't let it solve the exercise problems. You're defeating the purpose.

22:06 And the uh the main person suffering is is you. Of course, it's fun to make pictures with uh these tools. So, this is kind of the the Pixar vision might be that some benevolent AI is taking good care of us and we become a bit lazy and round. But otherwise, things are pretty dandy. I don't think that's realistic. I think it will soon look more like this and maybe at some point if nobody fixes things even more like this. And specifically for tutorials, think of the following analogy.

22:50 If you're If you're uh cheating in a competition, that's unethical. It's like doping in a in a sports competition. But the tutorials are your training sessions. And if you dope in the training, that's out that's utterly stupid. There's not just no competition to be won. You're not even winning the competition because the exam is without AI. Uh so you're only getting the uh the negatives. I know it's sometimes hard. Time can be short, etc. But try to resist. >> [snorts] >> Enough of the uh dark language. Um a quick few words about the other tools uh for those who haven't used them before. Campuswire, I would say, is a bit like Reddit specific for lecturers. It allows you to ask questions and people can answer the questions. The answers are sorted by upvotes. Uh so you can work on or reply to questions and refine them. Um and you can also answer or ask questions anonymously.

23:27 Communication platforms

24:02 The goal would be to use this as our main out of classroom communication platform. Uh just because then everyone gets the same answers. I think it's more effective. It's a nice markdown and LaTeX supports uh interface. So uh usually works fine. They have an uh mobile app that works okay. Again, you you need this PIN to sign up. Um And the hope is that it's not just a dump for your questions, but also that you answer other people's questions. That's the best way to learn.

24:43 Okay. Um The only other other system is ILIAS, which most of you know. Uh I find ILIAS workable, but not particularly nice to use. So I use it only for the things where it's the only sensible option. Which is the official parts and marks. And the assignment hand-ins. Everything else will either be Canvas fire or the website.

25:09 Collaborative exam prep

25:13 And one last thing that I would like to try again is a collaborative question gallery for the exam. It's a long way to go, so I haven't even put this on the website yet. The goal is just to have a shared Google Doc to collect questions that could be questions asked on an oral exam. And the double purpose is by making you think about these questions, you can try to anticipate what might be good questions. If you put them in, I promise to have a little comment saying, "Yeah, that's a good question. I could have asked that right like it is." Or yeah, that maybe is too much or leads too far or that's fine, but it's a rather shallow one. I'll comment on them, so you get some feedback. And maybe if I like your question, you know, could even be asked on your exam.

26:05 When I say your question, this is the general you. It's It's just a Google Doc, so nobody really tracks who says what. Okay, engage in this early. But not just yet. It's not up there.