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: kzfaq.info/get/bejne/pdOjpZBmmtSrZ6c.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 (kzfaq.info/get/bejne/p696dtKSudishn0.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!

Thanks for commenting!

great to hear, thanks!

I am not completely sure, whether I understand your comment correctly, but there is no factor i in the sum(Prob(#prob>i)). This corresponds to the sum at the bottom at 01:55, see e.g. also Theorem 1 here: www.cs.princeton.edu/courses/archive/fall02/cs341/lec22.pdf .

I assume you are referring to approx. timestamp 14:00? Insert creates a tree of size 1, and then takes the union of this tree with the trees of the previous heap. Now, for instance, lets assume we are inserting the 8th element. Then the previous binomial heap had 7 elements, and consisted of a tree of size 1, a tree of size 2, and a tree of size 4. Insert will now link the new tree of size 1 with the existing heap of size one, resulting in a tree of size 2. Because there is already a tree of size 2, we link this with the existing tree of size 2, resulting in a tree of size 4. This we link with the existing tree of size 4, finally getting a tree of size 8. Here is a cute animation of this process: www.chrislaux.com/binomialheap Thus, for each of the trees that we "iterate through", we do one link operation. Link operations take constant time. So, this contributes O(k) to the actual cost, and this is captured by the "+k" in c_i. Does that answer your question?

@@algorithmslab Yes you answered my question. Thank you very much ! I finally understand 😊

Thanks for your comment, happy to hear this!