Видео

Thanks for the pointer!

Thanks!

You are right: strictly speaking limiting m to n is not necessary. For m>n the algorithm would do exactly the same as for m=n. But the algorithm is formulated as it is, because there is also no point in using an m>n. I'd say the exact formulation boils down to a matter of taste. The original formulation by Chan bounds m to n, on the slides we follow this formulation.

@ Thank you for the confirmation :)

Summary of reply: At the inner nodes of the associated trees, we store (dummy) keys to guide the search on the y-coordinates, just as we have previously seen in the 1d case. For a visualization see here: zhoujoseph.github.io/Orthogonal-range-tree-visualization/ Longer answer: First lets have a look at the 1D search trees again (see 4:58). We use a balanced binary search tree with the points stored at the leaves. The inner nodes only store information to guide the search. Now in 2d we use the same type of binary search tree on the x-coordinates as primary data structure. Thus, again the inner nodes store information to guide the search on the x-coordinate. Additionally, we store at each node a 1d-range tree of all points that fall into the corresponding x-range, but now this range tree is on the y-coordinates, see 16:45. And now to answer your question: Since these are 1D range trees on the y-coordinates, the inner nodes store information to guide the search in y. Thus for the example in 16:45, we could store a 4 at the root, which tells me that if the y-coordinate I am search for is <=4, then I go into the left (lower) subtree, otherwise into the right (upper) subtree. And so on. Here is a nice demo: zhoujoseph.github.io/Orthogonal-range-tree-visualization/ Just click to add a couple of points e.g. 4, and then "Build range tree", and it will nice visualize the tree below including the information stored at the inner nodes. Hope this clarifies it.

each node stores the subtree with the root as that node and they are ordered using the y-coordinate

Thanks for pointing this now. Yes, I have noticed that some of the videos out of this series unfortunately have audio issues. I fixed my setup by now for future videos.

The slides are here: github.com/kbuchin/slide-archive/blob/main/advanced-algorithms-2024/07-approx-03-steiner-tree_multiway-cut.pdf They were created in ipe (ipe.otfried.org/), so there is no ppt. You can edit the pdf in ipe.

I assume this question is about the multi-pop stack. Lets say the actual costs per operation are: - push: 1 - pop: 1 - multi-pop(k): k Now, lets try to use amortized costs: 1, 1, and 1. The sum of amortized costs should always be at least as high as the sum of actual costs. But if my sequence is: 8*push(), then 1*multi-pop(8), then the sum of amortized costs is 9*1=9, but the sum of actual costs is 8*1 + 1*8 = 16. So the condition above is violated. If we want to assign the multi-pop constant amortized cost, the only way to solve this, is to increase the amortized cost of push to (at least) 2. And if we do so, then we actually save enough to set the amortized cost of pop and multi-pop to 0. Of course, if we wanted to, we could give pop and multi-pop amortized costs of 1 (or 2 or even higher), but this would simply be unnecessary. For a deeper understanding of amortized costs in the accounting method it can be helpful to look at the potential method; see follow-up video. After defining the potential (which in this case is simply the number of elements currently in the stack), the amortized costs can be simply calculated, and the result is push:2, pop:0, multi-pop:0. And to summarize: increasing the amortized cost of pop and multi-pop is of course possible (but useless), decreasing the amortized cost for push is not possible. I hope this clarifies why the costs are set as they are.

Thanks for the comment, it is always great to hear about applications of computational geometry!

glad to be of help!

@@luca-ik2bo thanks!

The corresponding figure and explanation is at 11:10. We need to build the data structure in advance without knowing query. Therefore the query might be in any of the Theta(n) slabs, and therefore we need to build a binary search tree for each of the slabs. In the example, every binary search tree has size Theta(n), so that ends up giving us Theta(n^2) overall. Does that make sense?

Great to hear! Thanks for the kind words!

Thanks for the kind words! I am really glad to hear that the videos are helpful.

Happy to hear that it was helpful! Videos are a great tool for flexible learning. On the other hand, lectures provide a great opportunity for real-time interaction. I'd generally encourage students to take advantage of both formats.

Thanks, great to hear! I usually post videos when I teach a new topic. Luckily for me, I’ll be teaching the course on approximation algorithms and linear programming again next semester. But there will surely be in the not-to-far future new topics, and with them, new videos.

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

@@VidushJindal 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!