Video 0: Administrativa

0:03 So officially welcome to advanced algorithms. Today we're going to look over some administrative parts, how the module will be organized, assessments, these lovely things and I'll give you an overview of what the module will be about uh without digging into anything much deeper. Um that's for the remaining weeks. Um so much for that. So advanced algorithms is my my abbreviation for that. That's also the slider code that you've uh been using on the slide before. Um I guess I'm I'm correctly assuming that this module cannot be a compulsory module for anyone. Correct?

0:45 I think it's I'm not aware of any course of studies where this is a compulsory module. So, uh, with that in mind, um, it's even more important to give you, um, a preview of what I'll I'd like you to do in this, so that you can decide if this is something you'd like to do. [snorts] I'm Sebastian V. Um, if you ever need to find me, that's my office. easier is if you send me an email first, but I will say on uh other um modes of communication later, campus wire might be preferable for some reasons. Uh we'll come to that. And here's um the signup pin that you need. So, uh this is what you only find in the slides. The link to join next to it, this part is also on the on the public website. In in theory, it's not a secret how to join with the PIN because the slides are online, but at least it's a a tiny bit of um an a signal that this is intended for us as a more closed group.

1:59 Yeah. Important things first. Um as required by our regulations, all the mark will come from one final exam. Um my understanding is that we can't deviate from that. Given that we're a small group, I would go for oral exams. It's a typical thing in in Germany for M's level. Um, to be allowed to take this exam more as a kind of incentive to prepare properly, you'll need some Oh, that's not up to date. Sorry, I think I removed that. Okay. Um, you need points from our exercise problems. Uh the seminar was an experiment last time. Um the goal of the exercises is not really to keep people away from the exam, but rather just a a preparation for you and a bit of a early feedback. We'll usually mark these rather generously and you'll also do them in groups. Um but you should take them as as an indication whether you're on track. And we also try to just find some fun puzzles there.

3:12 Now a few um comments about various parts that we'll use. Uh and I'll I'll briefly give you my my philosophy behind it. Um slider again for a small group not so important but it's it's useful to once in a while pass the ball back and let people do something. uh maybe in a smaller group this can be more interactive in general uh kind of as a catchall system. The least interaction I can get from you is to press one button [snorts] and that's what slido does. It asks polls uh with multiple choice answers and you can uh you can vote on those. It's anonymous which sometimes is very convenient to get everyone um to kind of take part without any fears. uh is really just a psychological trick to get you activated. Uh in particular, I don't care if um your answer is correct. In a way, it's only informative. If all of you feel like something is unclear, then probably you should take a quick pause.

4:15 And the other thing that Slider supports are questions from the audience. Again, in the small group, you can also always just shout. Uh if you prefer, you can also type it up though. And in case you have to at some point uh participate remotely then that's also an option to reach us here. Um there's at least a couple of people in the live stream. Hi guys. So um I'll try to be a bit attentive to the Q&A on Slido. Uh so if you ask a question there in principle I should see it sooner or later. Okay.

5:00 Uh question questions about that for now. Uh we'll have a bit of a play with it. Um let's first go to the intro question I asked you uh at the beginning. Uh if you have any expectations or any goals for this uh randomized algorithms will definitely feature uh I'll I'll say more about the content in the next unit. Um, you can also take this question uh more more philosophically, more broadly.

5:34 I'll give you half a minute. Um, I want to still say something about that. There's no right or wrong answers for this, of course. uh is essentially just um a fun exercise to take take some of these votes now and then in a bit in a few weeks time you can revisit it and uh see if it lived up to your expectations. Everyone loves a hard problem. uh also more about that of course I've essentially spent last week working on a problem where now people feel it might not even be in NP it might be worse than NP hard pspace hard that doesn't feature much in this in this lecture maybe I'll smuggle in a few comments about it now that um it reached closer to a problem dear to my heart. Um, of course you all want to pass pass exams but also understand I love the kind of order stress on the first.

6:43 Any more thoughts you want to share or like preserve now and um look back to later. Oh, pee hard problems. Yeah. uh we we'll see some um not much of the theory on on uh these lower level complexity classes also like for for the experts if you don't know what I'm talking about that's totally fine but last week was a rather interesting week there was the open AI releases of all these uh let's call them papers but this is really um well lots more to say let me not do that now uh But there was another paper that was a bit more silent and was a day before that shattered the world of um fine grain complexity where also these p hard problems may play a role. There's um a class of problems if you want to Google for it. The threesome problem is is the one I'm talking about that people conjecture you cannot solve faster than a certain runtime quadratic. And uh this was for a long time even a bit like uh np hard problems. Uh a problem you would compare other problems to and say oh this is threesome hard seems at least as hard as threesome to solve in a certain running time. at least as hard to solve in a certain running time as threesome is to solve in less than quadratic time.

8:09 Now it turns out threesome can be solved in less than quadratic time and the story behind it is rather interesting. Uh that's a another paper from last week and in this case properly published um by humans but AI was involved in finding the result. So much for pard problems. Um uh I'll probably have to disappoint you a bit on that. But you know one famous p hard problem. Does anyone know a p hard problem?

8:47 Well linear programming is is one I think flows in a general setting too. So, so max flows min cost flows in a graph is essentially a linear programming and in some form linear programming is is p hard and we'll talk about that a bit. Okay. Um the less interesting controversial question was just to get a feel um where people are. Uh um I think you can do the module in both masters and advanced bachelors.

9:36 So we're six here, but there's uh fourish concurrent views of live stream. I don't know what that means or if this is just devices and not people. Okay, it dropped to two at this point. I don't know if we should wait for more. Everyone's doing masters, it seems.

9:52 Good. That's slido. So, you've seen what that works like. As I said, just a little nudge to stay awake or become active again. Um a slide I always um very briefly want to mention um lots of experimentation with different modes to teach. For me um the uh flipped class approaches of here are some videos, some book chapters, go read them and then we uh talk about it in class. Uh I couldn't get that to work the way I wanted. So for me, synchronous lectures seem to be best in in keeping everyone uh up to speed, at least have this um minimal engagement um for a certain number of slots per week. It's just easier to stay on track. So I'm I'm happy to keep those. Uh but it's useful to have some other ways for people to reach back because the standard lecture often has the same few vocal students speak up and the rest maybe has clever thoughts but is um for some reason not voicing them. So I hope to give you some uh options to do that.

11:14 And the live streams are just um a rather lowc cost thing for me to do to be honest. And it's is somewhat fun. So treat it as a kind of when it works it works um service that may may help you sometimes and if so that's great and if not you can ignore them. Uh overall the module consists of mainly the lectures that's what we're doing today. Then uh also talked about slider already. We'll have tutorials. There's a slide for that as well coming up. These are exercise problems where you're supposed to puzzle through some algorithmic questions or puzzles of various forms. Um in a way for the learning they're almost as important as the lecture. So try to take them seriously. And I I'll come back to this but you know uh many of these puzzles may be possible to solve by AI. That's not because AI is super powerful and can do everything.

12:13 Not at all. Like uh stories about that from current research questions where it completely fails. The thing is these problems are just known. Everyone in the world is teaching similar algorithms classes. There's only so many problems out there and the AI labs are pretty good at gobbling up these in benchmarks. So they will work with AI for whatever reason. The point is rather if you cheat yourself and uh solve the exercises B by AI, it's a bit like bringing a forklift to the gym. You get the weights lifted, but it's not going to help you build any muscle. [snorts] Easier said than done. Um when the temptation Friday night deadline approaches uh rises, think of this uh image again and try to resist. That's uh I think the best I can I can tell you. um will mark the the submissions rather generously think taking into account that a serious attempt is more worthy these days than a completely fleshed out solution.

13:23 Uh and also what AI gives you is um not always all that good. Okay, but this is um a moving target. Now campus wire, I'll speak a bit more about it. This is when the lectures or tutorials are not going on is a way to reach the rest of the group and I call it collaborative because I hope that people when they ask when there are questions also some of you might uh want to chip in and answer things explain what p hard problems are what what else not uh the exam obvious um we're forced to put a mark on your performance through one final exam I can speak more about that uh when it gets more serious or closer to that. And the last bit is in preparation for the exam, I try to offer you some some shared Google doc, that's all that it is to collect questions. Um it's just a little nudge to encourage you to think about problems ahead of the exam and maybe start not two weeks before the exam, but a bit earlier during the term. Um often helps.

14:28 Questions? Awkward so far. Um not sure I have much more to say about assessments at this point. Uh the material is everything we covered in the lectures. That's maybe obvious but also what we cover in the tutorials. Uh the precise rules are standard I think in the department at this point. Um there's weekly exercises some some smaller some bigger exercise sheets. you're allowed to do two, not at all, or completely zero them. With more, then you get into trouble. On the other hand, a series attempt that gives you more than zero points isn't that much. So, uh I'm not I don't think this is a hurdle if you engage. Um the 50% of the points again is not intended to be a hurdle but it's intended to be a goal to like shoot a bit towards.

15:32 Um you'll find the exercise sheets on the module website. The module website is something I didn't stress at all. Let me maybe go back briefly here to the beginning. That's the module website. Um I love our university systems but I hate loginins especially on mobile. Um so uh whatever can go to a public website I put on this public website. Uh so that's the main main point of um information and any links to internal um systems the UNI has should be on the on the page as well.

16:15 That's where you find the exercise sheets. As I said, no uh reason to keep them secret, so they go there. They're all well-known exercises to some degree. Um if we're if we're saying a group of singledigit numbers, then maybe four people per group is not needed. Uh maybe you can form twos or threes instead. Um, if you totally insist the point is we plan with certain effort for marking and there we try to be a bit more conservative. If it's a smaller group, I think you get more feedback if you're in a in a smaller group. Okay. Okay. And we'll we'll meet once a week to discuss briefly the solutions the exercises from the previous week after they're uh they're marked questions at this point.

17:27 Again, I I'm going to say this five times. Don't cheat yourself by uh somehow avoiding thinking through the problems. If you can't solve them thoroughly, that's fine. If you don't even attempt, you'll not get there. That's the experience at least. And in that realm, let me say a few things about AI. Again, um I had to smile when I put up that slide because this is a bit dated. And I I thought okay I could of course replace some of the buzzwords with the with the current ones. Um but maybe more interesting is this is from a year ago or one and a half for this module. But um uh essentially uh the thing at the time was oh shocking AI has generated a picture that artists think is worthy of being considered a creative artifact.

18:21 We're a bit beyond that now. I think um even though it's still a rather checked picture overall. The main conclusion from that has not changed a bit. That's also sometimes um reassuring. I think nobody talks about Gen AI even anymore. It's just AI, right? Or if you go by other world leaders call it even differently. I'm not going to say that. Uh it remains to be jagged intelligence. It works for some things extremely well and for others rather not. Um it's fun to use. I'll show you a bit what I've done this morning, but uh later. So it's rather tempting to do it to use it for everything. But you'll I trust you'll have your own experience with this. Whenever you stop doing something manually, you also lose some of the skills. Maybe some skills are fine to be lost. Maybe we don't need to ever get lost in a city that we don't know. Uh it's just something to keep in mind. Now, in education, you've taken years out of your maybe productive life that that's coming up to study at uni.

19:38 And that is kind of constantly being in the gym exercising, not really uh doing work that you have to deliver. All you're doing here is kind of for you and for fun or for growing on it, not really to deliver something. Yeah, that's there's exams, but um if if all you take out of uni is this sheet of paper that tells you a few numbers, then you've kind of lost the game. I think this is uh you've lost a lot of what Uni can offer and uh people can sell you pieces of paper. That's not what we're here for. So don't don't waste your time here. It's it's your precious time. I'm paid anyways, but uh you'll you really lose this opportunity of deeply thinking about fun puzzles that you may not have time to uh think about uh in in your productive life unless you choose to stay in research. Don't take away the thinking even though thinking means struggling, right? It's it's kind of hard work and it hurts a bit.

20:47 Uh it's fine to use AI for various things especially improving your writing. I'm I'm fine with that. Or for for literature's work. It works much better than back then to not just fabricate any uh references. Still um at some point you want to start reading primary literature and try to read some some proper ones not AI slob uh which is often what the literature surveys are. Uh many times I've been frustrated with some summaries where after spending half an hour trying to digest what the summary means, I went back to the actual paper and it was much clearer. Uh depends on the use case. Uh certainly don't do any of these. Um it all subsumes. Try try to be reasonable and use the exercises so that they're productive for you. I think you know what this means.

21:45 >> Okay. Um, my favorite question at this point, maybe we don't need slider for that. Uh, and you can just, um, if you've not seen it before, make an educated guess. This came out of, uh, self-report asking students whether or not they cheated on some uh, assessments. I think usually these will be homework assessments where it's a bit easier, but maybe you can think of exams as well. uh but focus on on on homework um type of problems and they asked them whether or not they cheated and they asked them about many other things in their life and then tried to find correlations and there was one thing that stood a bit out which is uh is rather telling in a way guesses if you see I used this question in in sever several modules if you've seen it before don't spoil it all >> [laughter] >> Perfect. Yeah. Also not perfect. [laughter] My teaching had no impact.

22:53 Any thoughts? Like for example, one correlation could be overall poor marks. They're more in need for support. This could have been one outcome. And that would be rather um rather disillusioning or rather bad because there's not much we can do about if cheating is a compensation for a lack of ability in some general vague sense. But this was not at all the case.

23:24 Any other any any guesses? It's not color of the hair or all of these things are kind, you know, um I don't know if they asked for color of hair. Probably not. Yeah. >> Might be not showing up to lecture. >> Not showing up to lecture, just attendance. Um I would bet that there's some correlation there. It was not the one the strong one that they found. Uh there's there's a connection in maybe. Yeah.

23:58 >> Um that one's interesting, right? Uh however, if the exercise uh marks themselves are what they cheated in, it might funnily be the other way around. Now, these days it's often the other way around. people who score perfect on the exercise problems um didn't do them themselves and so score worse on exams. I've seen that in the summer. It's rather um is counterintuitive, but if you think about it, it makes some sense in these outliers. Yeah.

24:30 So, I think also um this was not what uh what they were getting at. Yeah. Other thoughts? Yeah, there it nicely summarizes in a single word and if you want to see the full thing, there's a YouTube video, you can find it on the slides later than uh where they go through this a bit in more detail. The single thing was procrastination.

24:56 Students who self-reported that they often procrastinate or spend time on things where a deadline is coming up and they really know they should be working on A but they do B, C, D, E. that was strongly correlated with them cheating, of course, because they didn't have time to do the exercises themselves, right? But that's really not how time works in a way or how procrastination works. We all have the same amount of time in a way. Uh I mean, life circumstances aside, it's usually time management that was what they were lacking. And of course, if if you're not good in keeping your time or keeping your time free for things you need to do at a certain point in the future, um then that shows as procrastination, but it also brings you in this in this tough spot where now suddenly you have to produce something and you don't have time left. Yeah.

26:03 So, find something that works for you to manage your time. That's the lesson. Also, like on these kind of soft meta topics, I'm happy to chat about that uh outside of class a bit. Um all of all of us are on a journey there. Um, okay. Uh, last bit on on the tool side is Campus Wire. It's a bit like Reddit. You can ask questions and answer things and they're ordered by how many people upvoted. Uh, the main thing why I like it is that you can ask questions publicly and everyone gets the same answer if it's something that I'm answering. Uh even better is if someone uh else answers. Not because I don't have to write the answer. I mean that too. But it's much more educating if you answer someone else's question after thinking through it. And I'll I'll promise if someone posts something I'll eventually read it and say indoors, thumbs up if it's correct or I'll leave some comment. Uh but if you answer first that is a double help, right? the person that asked got helped but also the helper learned something. You often notice whether you understand something properly once you try to explain it.

27:23 Uh there's also a feature to ask private questions if you think it's inappropriate. Again, this is our closed system, but within the closed system, try to be public. You can ask questions anonymously if you want. Okay. Uh try it out and if there's um problems with it, let me know. uh philosophy behind it. I think I mentioned um it's more relevant for larger classes. The traditional version of this would be office hours. Some set time where you can come and ask questions and then I can give you an answer and then next time someone else comes with the same question and I give a slightly different answer because I'm a human and so it's is a bit better to give the same answer to everyone. I think this is rather compelling to me and the other parts we've talked about. Okay. Um, where possible, I'll I'll redirect your question. So, if you email me, I'll I might just reply campus wire.

28:16 Don't treat take this as um me not being polite, but I'm nudging you. Um, and when it's a question where I think someone might have to say something, I might hold back for a for a bit to give you time [snorts] unless it's urgent.

28:36 Uh, we also have ELAS. That's the official um online learning virtual learning environment. I find it not so convenient to use also from my perspective. So rather egoistically I'm restricting the use to the cases where um for data protection reasons that's the only system we can use which is assessments and marks and we'll use it for the exercise submissions for essentially that reason too because there we need to have a submission pinned to your name hence your name is in the system for all the other things. Uh if you if you feel strongly about not signing up to any of these essentially US companies, Slido is European. Uh Campus Wire is is a US company. If you feel strongly about not signing up, let me know. Also happy if you put in fake names. I don't care. Um you can treat campus wire as essentially anonymous, but you're not forced to. Elas, you're forced to have an account because that's your university account. I will use that for any any assessment related things >> That's bad. I thought I I thought it is.

29:48 I at least meant to publish it uh two weeks ago. Mhm. So I'm trying I can also show there's the module website and it should have a link to IAS. Now of course um now of course I'm not signed in but if I sign in I of course see the module because um it's always visible to me.

30:45 I meant to click publish and everything. Um, in case I made a mistake, let me know. Then, uh, we'll fix that. >> Ah, what did I open that instead? That's the question.

30:57 >> And did you follow the link from the website or some some other >> interesting? I'll briefly log in and see if uh it's a very obvious thing to solve.

31:33 If not, then um I'll do it later. Ah, it says offline. Why? I ticked online. Okay, I ticked it now. Okay, the important part is um Elas doesn't add some important fields like it doesn't ask for your metric regulation number. It doesn't give me access to your metric regulation number which is rather important. So we always add this manually. Maybe it was somehow I was doing this while traveling. Maybe the connection wasn't uh stable enough. Okay. Now, now it should work if you click on on that link and yeah, I should be able to self-enroll. Okay, the other one I didn't mess it up for the undergrads. That's good.

32:40 I don't think others take this. >> No, not this one. Oh, okay. Maybe with some um maybe not impossible. Okay, maybe with special allowance only. Then the other thing I can show because there's the question when our tutorials are um things that are centrally planned you'll find on Marvin for the tutorials. We didn't book a slot yet uh because this is the first time this module is happening in winter so it's not included in the uh general schedule yet.

33:21 So, I think given that we're a small group, we can probably find some slot that works. That was this. So, um, of course, uh, we'll we'll have to do that. Um, we're certainly not starting this week. I think I was ambitious here and said we start with a sheet but that's uh to be submitted end of next week. So this week you kind of don't have to work too hard yet and then uh at the end of this week you'll get the first sheet released and then over the course of the next week you can work on this which means only in week three we really need the first tutorial slot for discussing problems. Uh we could maybe have one next week just to uh um say hi or see that the tutorials work for everyone. As a very quick one maybe only I will send some uh poll for the days maybe. Uh last thing here on my list is the exam question gallery that I briefly mentioned.

34:44 Uh again, um it's just a shared Google doc where you can type questions. And I decided to keep this rolling from year to year. So you'll see what people came up last time around and you can take those questions or and add your new ones. Maybe don't delete the old ones, please. Uh and thinking about exam questions is a very good exercise for um practicing and preparing.