Видео

Thanks for the comment! I expect there is simply a misunderstanding about the base case of the recursion. In short, the algorithm chooses as vertex cover the vertices v which have w(v)=0 in the base case (i.e. when the recursion stops). I think the problem is that I say this very late in the video (starting at 10:44) and never write down the full algorithm. (Yes, reordering the presentation and adding pseudo-code seems like a good idea.) Here is a simple, non-recursive formulation of the algorithm in pseudo-code: 1. While there exists an edge (u, v), such that min{w(u), w(v)} > 0: 2. Let eps = min{w(u), w(v)}. 3. w(u) ← w(u) − eps. 4. w(v) ← w(v) − eps. 5. Return the set C = {v | w(v) = 0} LIne 5 here corresponds to the base case of the recursion. I hope this clarifies the algorithm. This algorithm is by Bar-Yehuda and Evan ["A local ratio theorem for approximating the weighted vertex cover problem". Ann. Discr. Math. 25, 27-46.], and a nice article about it is here: www.wisdom.weizmann.ac.il/~oded/bbfr.pdf [Bar-Yehuda, R., Bendel, K., Freund, A., & Rawitz, D. (2004). Local ratio: A unified framework for approximation algorithms. In memoriam: Shimon Even 1935-2004. ACM Computing Surveys (CSUR), 36(4), 422-463.]

There are certainly many excellent books and notes on linear programming. My lectures/videos are based on the book "Understanding and using linear programming" by Jiří Matoušek and Bernd Gärtner (2007). It is a great book, because it strikes a good balance between the underlying maths and how LPs are actually used.

Thanks, good point. From the perspective of the algorithm it makes sense to order the cases as they are (i.e. discuss the corresponding slide from left to right). But for explaining why we have the cases, it might be better to go from right to left (i.e. what do we want to achieve, how we get if from case 3, and then how we get case 3, in case we have case 2). Anyway, you figured it out, so I achieved my goal!

In the first implementation, if we would want to delete the 12, the whole second half of the list would need to change. The 13 would need to take the role of the 12 with 4 levels, while 15 would now only have 1 level instead of 2, and so on. But if it is a randomized skip list, deleting the 12 is easy. All the references into the 12 now need to continue to the next nodes as seen from the 12; however none of the nodes need to change its number of levels.

@@algorithmslab oh thanks, changing of level is a key to understand the difference :)

The main prerequisite is basic knowledge of “algorithms and data structures”, and the prerequisites for that. Prerequisites for “algorithms and data structures” are basic programming skills (language does not matter, it is more about the concepts) and “high-school maths”++. So the pathsway would be: A. Introduction to programming B. Mathematics for Computer Scientists (must include proof techniques & basic probability theory) C. Introduction to Algorithms and Data structures And now you should be set. The more exposure you had to algorithms & basic maths, the easier it should be, but in principle the above should be sufficient. A and B are independent of each other, and may be known partially from school. “Mathematics for Computer Scientists” is of course a bit vague, but a solid mathematical foundation is crucial for algorithms. And sometimes a basic maths course for computer scientists does not yet include probability theory, so it might be necessary to learn that separately. All of the above are standard first-year courses in a computer science curriculum, so you will find plenty of excellent online resources. For Algorithms and Data Structures I also have videos, but there are also excellent MOOCs, e.g. from Princeton and Stanford. Finally, I do have a video where I list prerequisites for my advances algorithms course: ruclips.net/video/omsr-55nG7s/видео.htmlsi=bwRs7wCMCA-8ZWgb I think this comes quite close to what I would expect for computational geometry.

@@algorithmslab thank you so much!

I switched to a different set of slides a while ago, and don't have these lying around anymore. If you send me an e-mail (to my TU Dortmund address), I could see whether I can help you with a different slide set (also based on the Cormen et al.)

the slides are the second half of the following: github.com/kbuchin/slide-archive/blob/main/advanced-algorithms-2024/02-Amortized-Analysis.pdf

In the video I just gloss over this, so I assume you are referring to the Jupyter notebook. The comparator class there unfortunately turned out rather complicated, since it has to handle quite a few edge cases to make the code reasonable robust. The horizontal line segments are handled in the last two cases in the method "_check_special_cases". There one can see that a segment comes later in the comparison, when the y-coordinates of the two end points are (nearly) the same and the other segment is not to the right of the event point. The latter is necessary, because (as is written in the book) "If there is a horizontal segment, it comes last among all segments containing p".

@@algorithmslab yes proffesor I understood and wrote the code, it works. I wrote the code in cpp and it is really fast it takes about 1 second for brute force for 10000 segments. it is a lovely code you wrote. Thanks and Regards

@@user-nw9ch3zi9d great to hear, thanks! (And the code was written by the other author of the notebook, so I will pass on the compliment)

Thank you! Happy to hear this.

great to hear, thanks!

Glück auf

Happy to hear that the videos are helpful!

The important observation here, is that #5 is actually never violated (i.e. assuming it holds at the beginning, all operations that we do don't break it). When inserting a new node, we make it red. So assuming that I had a correct tree before, the only violation that I now might have is one red child-parent pair. This is fixed in "Step 3". For all operations in Step 3 it is quite clear that they don't introduce a violation of #5. Only for the last rotation (the right rotation on the slide) we have to be careful. There we recolor z and b. But I explain, starting at 17:18, why property #5 still holds, assuming it was true before. So in short, the recoloring of z and b is what we do to make sure that #5 is not violated. I hope this answers the question.

Linking means that I take one of the trees and make it a subtree of another tree by connecting it via an edge to the root of that tree. That means that by linking the number of trees goes down by one. So if the number of trees before linking is some number k, it is k-1 after linking. The potential is c* number of trees. So before linking the potential was c*k, and after the linking it is c*(k-1) = c*k - c. The change in potential is therefore (c*k - c) - c*k = - c.

@@algorithmslab Thanks!

Thanks! This video is part of a series, and it is probably a good idea to first watch the video that introduces binary search trees (ruclips.net/video/qIJCoaTrHVI/видео.htmlsi=N-9x-yNDKw8VcHmi) Success with studying Data Structures and Algorithms!

okay, I didn't really have a good place to point at, but this should work for now: github.com/kbuchin/slide-archive

@@algorithmslab Thank a lot sir!!

Thanks! In the video description there is a link to the copy of the course (canvas.instructure.com/courses/3752774). It also contains the slides; for each unit, the slides are in the unit summary at the start of the unit. As a direct link to this slide set, the following should work: canvas.instructure.com/files/158068175/download?download_frd=1

That's great to hear! It is great to see that they are being used, just like I am happy that people find this videos useful. I also like reusing slides from colleagues.

It does not look minimal, because it is not minimal. In the video (at 40:21), I just wanted to show a cut to demonstrate the constraints; it was not intended to be minimal (sorry, if that wasn't clear). The cut fulfills the constraints of the ILP (if setting at least y_{2,5}=1, y_{4,5}=1 and y_{3,6} = 1) , but its objective value is 5 (= 1 + 2 + 2). Indeed, setting u_0=0 and u_2=0 and all other u_i=1, corresponds to the cut {o,a} and {b,c,d,e,n}, which results in an objective value of 4. Just one more remark about my cut, which was actually not intentional but is okay: it has the edge from 6 to 4, where we now go from a "1" to a "0". But that is okay since 0 - (-1) = 1 >= 0. I hope this clarifies the example and answers your question!

Yeah that clears things up! Thanks for taking the time to write such an elaborate answer!@@algorithmslab

Happy to hear this, thanks!

Great to hear that it's helpful! This video covers parts of three chapters from the Vazirani book (13,14,15), so I fully see how this could be spread out over several lectures. My aim here was to give a first overview of LP-based techniques for approximation algorithms.

That's great to hear!

This doesn't quite work, because Ci might not be constant. The first question you need to do is to define an appropriate potential function. For the binary counter it was the number of 1s, but here it has to look different (Hint: It has to involve the number of 2s. It can also involve the number of 1s.) c_i is the actual cost. Just like for the binary counter, this may vary, i.e., it is not necessarily constant. The trick then is (again like for the binary counter) to make sure to have defined the potential function in such a way, that whenever the counter has to change many digits, that then the potential drops by a similar number. This is a nice exercise.

We are working on a collection of Jupyter notebooks for the algorithms presented in the videos. I nice feature is that they don't just provide the code but also lets you visually explore the algorithms step by step. The repository is here: github.com/ls11ae/geoalg-notebooks Specifically, for line segment intersection the notebook is here: nbviewer.org/github/ls11ae/geoalg-notebooks/blob/master/notebooks/02-LineSegmentIntersection.ipynb To modify it and to use the interactive elements, you can use binder (and wait a bit) or simply download the repo.

Happy to hear, thanks!

Great to hear!