andreamad8/Algo2Problems

VeB tree EX15

andreamad8 opened this issue · 3 comments

andreamad8 commented

There are 3 possible solution, it would be great if we could vote for the more easy to understand one. We will still keep all of them in the folder, but it would be better to propose a more compact one as PROBLEM15_SOLUTION.

Thank again

Andrea

Andrea-V commented

I uploaded (yet another ) solution to ex15 , mostly based on 2014 solution. I did my best to keep exaplanations clear, and i tried to use words instead of pseudocode whenever i could (it is a pain in the ass to study and learn pseudocode for the exam :V ), instead focusing on the intuition behind (the solution is (should be, please double check!) formally correct anyway). I think the solution is quite clear and elegant, it may be a good candidate for the "official" solution. Let me know whether you agree with me or not. it's located in the "yet_another_solution" sub-folder.

andreamad8 commented

Really thank you, I was waiting for something like that. I will go through that soon!

Thanks a lot

Aanok commented

Yeah, your description is correct and a lot lighter, great job!

However, I don't quite get your discussion (or Grossi's request, for that matter) of a vEB as a heap: vEB trees are inherently a static data structure so it makes little sense to me to talk about insertions and deletions. The only way I can think of a dynamic vEB implementation is using something like a logarithmic merge strategy (see slide 47 and following of lecture3-indexconstruction.pdf).

I'm probably missing something...