Відео

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: ua-cam.com/video/omsr-55nG7s/v-deo.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 (ua-cam.com/video/qIJCoaTrHVI/v-deo.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!

That's great to hear!

Thanks for commenting!