Original post:
On Jan 31 and Feb 1 (Thursday and Friday), I am giving a minicourse at the
The course begins at 3pm each day. The room will be announced here in a few days.
In good theory tradition, I hope you will also come to a beer on Thursday evening, after the course. Details to be arranged.
The language will be Romanian. See below for announcement:
Titlu: Perspective geometrice in dezvoltarea algoritmilor
Abstract:
Cum ajuta o constructie Cantor pentru cardinalitatea numerelor rationale la obtinerea unor structuri de date eficiente? De ce estimarea normelor in dimensiuni inalte este necesara la optimizarea cautarilor in baze de date? Cum pot progrese in intelegerea geometriilor ne-euclidiene sa ajute la constructia microprocesoarelor?
Perspectiva geometrica s-a dovedit din ce in ce mai utila in progresele recente in dezvoltarea algoritmilor. In acest curs, vom discuta cateva idei matematice reprezentative, si cativa algoritmi frumosi care se obtin.
Cursul este la nivel introductor si speram ca va contine idei interesante si pentru informaticieni care urasca matematica si pentru matematicieni care urasc informatica.
I've managed to come to you first conference and it was very nice (including math part).
ReplyDeleteI have a question about predecessor search. I'm looking for an algorithm with better time complexity than binary search, but with memory consumption less than 2N (condition satisfied by binary search but not by van Emde Boas data structure). Do you know any?
Thanks, alexandru! In fact, predecessor search is a decomposable problem, and the space can be reduced easily for any data structure. You take an arbitrary (high-space) data structure, you build it for O(n/lg n) of the elements, and then solve the subproblems (which have size lg n) by a simple binary search.
ReplyDelete