Saturday, January 26, 2008

Minicourse at Univ Bucharest

Update: The room is 220 (second floor) at the University of Mathematics. See you Thursday.

Original post:

On Jan 31 and Feb 1 (Thursday and Friday), I am giving a minicourse at the University of Bucharest. It extends far beyond my own research (rough topic is "geometry in theoretical CS"). I am hoping that it will provide a taste of what modern algorithmic research is like, as well as present some really cool algorithms.

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

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.


Alexandru said...

I've managed to come to you first conference and it was very nice (including math part).

I 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?

Mihai said...

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.