Video 0-1: Welcome, teaching mode, overview, assessment, academic integity, Campuswire,

0:00 Module introduction

0:04 So, welcome to uh advanced algorithms. Um, in the first part, we'll just talk about some organizational bits. I'll go relatively quick. Uh, but I wanted to have this on record uh so that it's um there to refer back to. Uh the goals is to show you how the module is run and how it's assessed and then the follow-up little unit will give a bit of an overview of what it is about.

0:38 I'm Sebastian V. Wild is fine if you prefer. Um I'm occasionally sitting in my office up there. Uh best if you want um some if you need something uh best is via an email or use campus wire for things that are specific to this module especially if they're relevant to other students. Uh I'll come back to that. Um, we'll have uh Muhammad help us in tutorials. Uh, we'll come back to what happens there. The most important piece of information is the module website. If you haven't run across it, that's where you find um all key information. I'll try to make everything that can be on a public website onto this public website. I just find it myself so much more convenient not to have to log in every single time you look up some little bit. Um I feel this is uh also helpful. I didn't at all copy paste the slides. Um other bits that we're going to use are campus wire which is a Q&A forum. I'll explain a bit more what this looks like but you can already sign up.

1:46 Uh there's a the join link is on the public website. the link and the pin is on Elas um but it's also here if you want to do that uh later uh slider you already already saw what we use it for and as a rough summary as we're forced to do it like this um the final mark will come from the final assessment whatever that is and that's it uh there's no way to do partial marks in an easy set in an easy way uh but you have to earn the admission to the exams via um points in the exercise sheets and the mini seminar that I'll comment on later. Uh we've seen slider already so you know what it uh feels like. Um I just want to motivate a bit why I'm using it. Uh I feel it's a very helpful psychological little trick to activate people from time to time. uh otherwise it's easy to fall into the mode of uh watching TV which um is fine but uh uh sometimes is not as effective for learning something as other modes of listening. Um it also gives me a little bit of feedback whether you're following along. That's helpful for for both of us. Uh you've seen what it looks like.

3:09 does polls, which is I push a question out to you and you get to answer usually multiple choice and you can answer a question. You can ask questions on the audience Q&A uh at any time in between. If it's hidden because there's a poll running, you can still switch the tabs. Um I hope it's intuitive enough. Uh let's skip this because we've done uh an intro question already in all my lectures. Um there's always the question how do you organize lectures in general and um you've many of you will have had the dubious pleasure of having to do studies during uh the pandemic where everyone was forced to do some experiments with um alternative modes of teaching. Um I've actually done my experiments with alternative modes of teaching well before then and concluded I don't like it. um at least not pre-recorded videos and then flip teaching where I send you off to watch videos and then we meet and discuss afterwards. I just couldn't get it to work. And that might be my fault, but I always felt it's very hard also if if I'm experiences myself to stay on track with the lecture if you're not forced to synchronize at specific times.

3:30 Lecture and teaching approach

4:30 So that's what we'll do. We'll have synchronous live lectures. Uh, but I give you the option to watch them from your couch at home if you feel that's helpful for focusing or if you can't come for some reason. And if you can't make it at all, there's recordings which are not interactive, but at least you can still catch up what we've covered and you can rewatch uh if uh your memory is fading. Now if you want to do anything interactive there needs to be some something coming back from the audience to me and uh the traditional way would be some students occasionally ask questions and you're encouraged to do that whenever you feel um that's helpful. My experience is only a very small subset of students do that for many reasons and that's fine. Uh so I'll always try to have other back channels. There's slido for questions which you can use during the lecture and campus wire later and uh little polls in between just to keep you awake. I've covered most of this already. So we have lectures and we'll have these slido questions and we have campus wire. More on this I'm keep referring to this. Uh we'll come back to this. Uh we'll also have some um tutorials with exercise problems. Many of the topics that we'll cover only really get understood by doing it yourself by proving things yourself by designing algorithms yourself and by doing reductions yourself. So there will be handy in exercise sheets. Uh this will only start after the mini seminar which um which should be here too together with the tutorials. Let's add it. Um the exam of course in the end is um is a requirement. uh and I'll do this experiment again of having a collaborative exam question gallery where you can collect possible exam questions and the more work you do there up front the more I promise to comment on those questions and we'll see how that goes.

5:50 Assessment overview

6:46 Uh I'll uh my experience is if I if I tell you to do this now nobody does because you haven't learned that much in this module. So, um, I'll reopen this a bit later in the term, try to raise enthusiasm for it when we get to it. Let's speak about let's talk about assessment briefly. Um, as I said, the actual um points you get at the end come from the final exam. That's the only option you have. The only option we have um I I'll announce soon what whether it's written or oral. Um, and the material that's covered in either of those uh forms of exams is everything that we cover in class except maybe sometimes I feel I'm making comments that are useful if you want to go into researching this further but are really a bit over the top. Then I'm sometimes marking them with not part of the exam. Anything else is covered. Uh, and also the tutorials and exercise sheets because these are often complementing what we do in class. Uh so they're part of the exam material. Uh to be admitted for the exam um uh we decided to set the rules so you can you can skip up to two of the exercise sheets. Um might be a lot because u I'm planning to do them bi-weekly instead of weekly. Uh but we'll uh I'll I'll let you know. um and uh 50% of the available points but the marking will be mostly rewarding um genuine attempts not only completely solved. Uh and the last bit is um a little extra thing we'll do over the next two weeks. That's the u mini seminar on NP completeness.

7:06 NP-completeness mini-seminar

8:42 So because the group is a bit diverse and you come from different backgrounds uh much of the later parts of the module really don't make sense if you don't have a solid foundation in the classical complexity theory NPA completeness and uh I can of course run through this here and I'll do that this week but um to make sure that you have a chance to grasp this you'll have to do something from your end and so what we'll do instead of lectures the next two weeks is a little mini seminar where you prepare in groups um one topic from NP hardartness um and present it in in two forms. So again the goal is is to make make sure everyone's on the same page uh with respect to NP completeness before we move on. Um and it's a master's module so you're supposed to go towards the cutting edge of research. Now we'll do this with a very old research paper. So cutting edge is not s not a literal term here. Uh but it's still primary research literature. Uh which is is always a bit um of a different type of reading. If you uh read textbooks, everything has been pre-digested a few times before it's presented in a way uh that the author thought at least is is most useful. uh primary research literature is often a bit more rough and uh uh concise. Um so it needs practice to read those. Um and that's that's one way to do it. And same as in the exercise classes, I want you to be able to write proofs in a way that is rigorous. And so that's another way to test that.

10:30 So what you'll what you'll do concretely is um make a written report of one NP hardness reduction and we'll we'll pick some classic examples where it's not incredibly hard to find material online where people already explain this but the point of the whole mini seminar is that you put this in your own words and you dig through this one example very deep. So one deliverable is the written proof and it should be the general construction plus um a fully worked example for the two cases that you always have in MP hardness reductions a yes instance and a no instance just to make 100% sure you understood the construction you'll have um you'll have done some of this in a theoretical computer science module if you've done one um but hopefully hopefully not exactly the problems uh that are on the list and I think it's it's a good refresher before we move on. Uh the second bit maybe is a bit more fun part um try to make a nice explainer video out of this.

11:39 So this first the report the written report should be completely formal mathematical language and formulas and all that. Um you're very welcome to use latte for that. Um if you feel a different system is better that's fine. uh the second part is is a bit more conversational and is just supposed to make it easy to understand your construction. So in a way your video could be a highle introduction to your report. Uh so that if someone wants to dig into the details of the proof they can watch the video and get the gist of it and then see the full details in the report. And so that these videos are not write only documents. Each group will also watch over the video and the report from three other groups and write a little report just summarizing how well it it worked for them to understand the reduction. Um, I'll send out some some specific guidance. This will be very narrowly guided. So, you don't have to write a lengthy essay how you liked it. It'll be specific guiding questions. Um, but I think it would be a shame if you make nice videos and then nobody sees them apart from us.

12:58 So the goal is to have this over roughly uh weeks two and three. Um and my my original idea was to pick the original and first and only paper where NP completeness was introduced. I don't know if you know the story behind this. This was uh when did he publish? I think it's 1973 73. It's c certainly early 70s but uh uh don't quote me on the year and also I guess the results were known bit before and then it took a while to publish. Um Richard Carb published one paper that uh I have here um a nice typewriter uh where he invented the idea of npleteness and gave 21 npmplete problems uh where for most of them he just lists very shortly very briefly the construction and he doesn't even bother to spell out the correctness argument. uments why the reduction works. So um the goal would be to pick these are 21 problems but it's really just 20 reductions because one of them is boolean satisfiability which is separately proven that's the cook leaven theorem.

14:16 If none of this makes any sense to you, by the way, it will after the end of tomorrow's lecture. I'll go over the basics of this um at a at a crazy pace, but so that at least if you haven't heard anything about this before, um you'll know your basic way around. So there's 20 reductions in there. If uh we stay at 120 people, that would be um a bit big groups. uh if we uh roughly of the size here it might work out if we don't cover all problems that's also fine but I think group sizes beyond five people is getting uh tricky um yeah I have a have a website prepared with more details on how this is going to run but if you have specific questions now uh let me know there's one question also on slidoh um to no you can see it's part of this module that's why I call it a mini seminar it's it's not as much work you're uh in the master seminar that also exists um you're usually reading full papers and maybe several of them and compare them something like um and you do it alone. So here we have three to five people working on it and the part that you have to read from the paper technically might be something like just a a single formula or so. Uh many of the reductions in here are really really short. Uh you'll probably have to read the definitions to understand them. But is is far less intense than the seminar modules.

16:19 Uh other questions about the mini seminar for now. Okay. Um let me go back. Uh there's one thing we haven't talked about uh which is campus wire but okay tutorials first that as well. So formally the mini seminar is part of the admissions for the exam. You'll do a few less of the exam uh exercise sheets. You'll do the uh mini seminar instead. And those two things together are the admission requirements. Um I hope it's it's not supposed to be a super overwhelming task. Uh and the videos can also be low fidelity. So essentially have some have some uh someone film with a smartphone while you write on a piece of paper is not a stupid idea or a theory thing. I've seen that done with um pandemic tutomic time tutorials. It was super effective. Uh it doesn't need to be uh any flashy animations. Although if you want uh you're welcome to um after probably put this here somewhere. Uh we'll start with this after the mini seminar.

16:24 Tutorials and exercises

17:40 Um more traditional exercise problems uh on a sheet that you hand in in a group as most modules have it in some form. Um, so that's uh that's what we'll do as well.

17:55 Um, and um I'll probably have the pleasure to present some solutions to you in some uh some uh central exercise tutorial. Uh but we'll have to find a room for that. Uh so I'll again because we only start after the mini seminar, I'll delay the decision depending a bit on how big the audience still is.

18:22 As I mentioned before, we'll be a bit more lenient on the marking um because the intention of more lenient than in an exam. Uh the intention is to get you working on on problems. Um while we talk about exercises, uh I noticed there's a new thing around and you noticed too. uh is amazing fun to play with all sort of I mean deepseek for for these kind of problems theory problems um is pretty useful I wouldn't say it kind of solves anything um without guidance but it's useful uh as a research tool for sure and for many other things what it doesn't do is help you learn quite the opposite and if you take a step back why are you doing this all of this like uh your your degree uh why are you studying here? Uh maybe there's many reasons, but hopefully one good one will be that you take skills out of this that uh help you in your career, set you apart from maybe other people who haven't invested the same amount of time. All of this is kind of compromised if you let some uh some AI do the work for you specifically for these exercise problems. They're designed for you uh to help you acquire skills. Um so don't cheat yourself.

18:37 Academic integrity and AI

19:45 um by using by taking away the thinking. And it's I mean I'm I'm not even saying that uh we try to catch you cheating. That's not my point. Um if you're smart about doing it, you won't be caught because you let AI make suggestions and you just rewrite it in some human form. I'm never never going to find out. But you're also never going to get the skills that you wanted if you don't bang your head against the problems for a while. Uh, I know it's very tempting. It's pretty hard. Um, especially if time pressure ramps up. Uh, but try to remind yourself of just not doing it is similar to um, that's why I put this quote here. It's a bit of a a jokey quote, of course, but the point of of doing exercise in a physical sense is also not to uh, be 10 kilometers away. If you run in circles, for sure not. uh is about what you get out of the exercise and if you let a robot do the same thing or if you drive by car it's not the same right okay enough about that um just to be very clear it's acceptable to do prepar prep preparatory research so replace Wikipedia in a in a sense use it as a point to jump to the right place to then read more that's fine uh I'm also fine if you use it for proof reading ing your writing um is always nice to read well formulated text. Uh don't use it to generate old parts of your submission without uh proper acknowledgement, citation and so on. Uh don't use it to make something that you took from somewhere else sound different so that you're not caught. It's obviously ethically problematic. Um and also avoid letting it do all the thinking for you.

21:47 Time management discussion

21:49 Uh, okay. I should have prepared this one. Um, let's do this quickly because I think this is this is a a key question. So, you can think about this while I'm setting up Slido. Uh uh uh what I'm looking for here is uh a criterion self-reported from students that had the strongest correlation with them also cheating on assessments. So there was a there was a specific thing uh interestingly striking how much it stood out um that that correlated well with uh also cheating. Now this it's called correlation not causation uh but I think it's still an insightful thing. So have a guess. Uh what do you think um of all I mean it could be personality traits, it could be habits, it could be god demographics, gender, whatever.

22:55 Uh it could have been. Uh thankfully that um is not what it was. It's a good point that cheating can become a habit. Uh but the point here was there's something that correlated with having the habit. Uh not going to class, not studying. Uh, word perfection is an interesting one. Yeah. Yeah. Language I mean barriers of all sorts don't help. I'm reusing the poll from different lectures. So maybe someone remembers um the right answer is among the options. Uh pressure in general is also a is an interesting is an interesting one. I would have that was that would have my been my guess. Uh the more desperate you are, the more you're going to cheat. But that was wasn't quite true. Um yeah so the uh the answer is among there and it's it's procrastination uh students that tended to procrastinate to not get things done in time and not necessarily because of pressure or outward outer things or really like a hardship cases. It was the the habit of not planning and managing your time well enough that constantly led to being behind. And then I mean procrastinating is is the process of spending your time unwisely, but it also means that you have trouble reserving the time for the important things, right? That's the flip side of it, of course. Um, and it's interesting that it correlated so well because it it kind of seems to be the the source the root of uh time problems later on and many other correlating things maybe pressure and and desperation and all that kind of flow from it. Okay, I'm I'm not going to uh be able to analyze more. This is just something uh the source is is um is uh given in a video where the context is explained a bit more. I found this useful to push out just as a nudge. Get your time management right. Um it's another obvious one. Uh not telling you any uh any news Um, I would say it's it's a closest to Reddit before it became apparently not a nice place anymore. Um, you can ask questions. They pop up at the top and you can post answers and the answers are ranked by how many people upvote them.

25:46 Using Campuswire and Elias

26:08 You can reply to answers. So, it has the same kind of structure. Uh the difference in campus wire is it's a bit more specific to the setting of a lecture of a a university lecture. Uh so you can you can only sign up with your university email by default for example in case you're having trouble try to use something with the uni marborg uh domain.

26:33 Um the other feature is uh you can ask questions anonymously. If you don't want to expose yourself in front of the whole class, that's uh that's okay and you can ask anonymously also answer. Um but the idea is really that the whole group also tries to help out others because the best way um to learn is to teach others. Uh it has two features that we use. The class feed is what I was speaking about. That's the Reddit like feature. There's also chat rooms uh that are just a little less structured and maybe for instantaneous things are sometimes useful.

27:11 Um the class feed should be the standard Q&A place. If you have a question that relates to the content of the material or also organizational things that are not super super urgent, uh the best is to put a question out on on campus wire because then everyone can see it and I can answer it once if it's organizational and you can try answer it for others if it's content based. uh any of of these types of questions. Um if you found an an answer helpful then upvote for it. That will influence the ranking and it also has a credit system so you get some uh you can you can climb up the ranks by being active. Uh there's an option to ask a question privately just to instructors if you feel it's spoiling some assessment. Uh that's the way to go. most other things I think is fine to have public and uh anonymously if you um just to be explicit I'm trying to push campus wire if you send me an email and some and I feel it's something that should go on campus wire I'll reply to your email but I'll just say campus wire okay I'm never going to reply with an actual useful answer. But if you put it on campus wire, I'll if it's urgent, I usually have it quick on the phone and see it on the day. Um, but I'll might not respond if it's a content question to give other students a chance to answer. Uh, the goal is is to be fair because everyone gets the same answers, which is different if you come up after class um than depending on how much time we have. I think it's it's preferable to do it on campus wire. Uh it helps you to help to learn if you can answer for someone else and it's more inclusive if everyone uh has a way to express themselves. I think um as I said I'll redirect you to the class feed on campus wire with wherever that's the most appropriate place. I'll hold up um answering a little bit um and I'll promise if someone answers the question for me and does a good job I'll eventually put an endorsed or um forget what what the term was on campus wire but there's a way to mark it as okay instructor has said this is actually right um yeah something like that but uh it's a different term and you can you can assign it to several answers so it's not it's not uh not like Stack Overflow. Um yeah, see see how you get on. Um first sign up and then we'll we'll have a play a bit and maybe we can discuss tomorrow again if something doesn't work or if you have questions about it. There's also ELAS, the official university online uh learning platform.

30:11 Communication platforms

30:16 Uh, I'll mostly use it for anything that cannot go to a non-university university server, which is all your personal data, especially anything relating to marks. If you sign up on campus wire with some fake name, I guess that's all right. Uh, I don't really need you to be identifiable there. Uh, Elias is different. That's where uh, anything official happens, which also means um, I'm going to use not that much, especially announcements. The only thing you can do is send out emails. But then if you signed up for the module late, you cannot see the past emails as far as I know. And uh whereas Campus Wire, if you join later, you can still go through all the old posts and and read up on what happened.