.:. Roberto Grossi

---

Dipartimento di Informatica Università di Pisa Largo Bruno Pontecorvo 3 56127 Pisa, Italy grossi@di.unipi.it  342-DN (room) +39-050-221-2793 (voice) +39-050-221-2726 (fax) robertogrossi (skype)

-:- ABOUT ME

• Professor at the University of Pisa.
• Ph.D. and Laurea in Computer Science at the University of Pisa.
• Member of the Algorithms and Data Structures group at the Department of Computer Science.
• Formerly, at the University of Florence as assistant, and at the University of Pisa as associate.
• EB member of Theory of Computing Systems (TOCS), Springer-Verlag, and RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications , EDP Sciences.
• PC member of CIAC03, CPM03, STACS03, ESA04, FUN04 (cochair), IS04-TCS, SPIRE04, ICTCS05, SODA05, SPIRE05, ALENEX06, SWAT10, IWOCA10, ESA10, FOCS10, SPIRE11 (cochair), WADS11, IWOCA11, IWOCA12, CIKM12.
• Member of the Scientific Council of the Italian Chapter of EATCS and of the International Olympiad in Informatics.

-:- TEACHING (in Italian)

• 316AA - Algoritmica 2.
• 039AA - Algoritmi e Strutture dei Dati (Matematica).
• Ricevimento degli studenti:
  1. per le date di giugno, consultare la pagina Web del corso d'interesse;
  2. per appuntamento (per email o telefono).
• Appelli di esami: calendario ufficiale.

-:- RESEARCH

• Design and analysis of algorithms and data structures.
• Dynamic and external memory algorithms; graph algorithms.
• Experimental and algorithm engineering; fast lookup tables and dictionaries.
• Pattern matching algorithms on strings, matrices and trees.
• Text indexing and compressed data structures; compressed suffix array and suffix tree.
• Proudly advised Ph.D. students: Gianni Franceschini (U. di Roma "La Sapienza"), Ankur Gupta (Duke U. & Purdue U., advisor Jeff Vitter), Iwona Bialynicka-Birula (Microsoft), Giovanni Battaglia (ION Trading), Alessio Orlandi (Google), Mauriana Pesaresi (1983-2008, unforgettable), Rui Andre' Ferreira (Galilei International Ph.D. school), Giuseppe Ottaviano (Galilei International Ph.D. school and Microsoft Research).
• Ph.D. schools/seminars: Bertinoro 2000, Lyon 2003, Lipari 2003, Rennes 2004, Chennai 2004, Haifa 2005.

-:- ON LINE PAPERS

• Will be updated sooner or later... a random subset is here
• Amortized Rigidness in Dynamic Cartesian Trees, with I. Bialynicka-Birula, International Symposium on Theoretical Aspects of Computer Science (STACS 2006).
• Squeezing Succinct Data Structures into Entropy Bounds, with K. Sadakane, ACM-SIAM Symposium on Discrete Algorithms (SODA 2006).
• Rank-Sensitive Data Structures, with I. Bialynicka-Birula, String Processing and Information Retrieval (SPIRE 2005).
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching, with J.S. Vitter, SIAM Journal on Computing, 2005.
• When Indexing Equals Compression: Experiments with Compressing Suffix Arrays and Applications, with A. Gupta and J.S. Vitter, ACM Transactions on Algorithms (special issue of ACM-SIAM SODA), 2005, accepted with revisions.
• Optimal In-Place Sorting of Vectors and Records, with G. Franceschini, International Colloquium on Automata, Languages and Programming (ICALP 2005).
• Distilling Router Data Analysis for Faster and Simpler Dynamic IP Lookup Algorithms, with F. Geraci, International Workshop on Efficient and Experimental Algorithms (WEA 2005).
• Optimal Implicit Dictionaries over Unbounded Universes, with G. Franceschini, Theory of Computing Systems, 2005.
• Bases of Motifs for Generating Repeated Patterns with Wild Cards, with N. Pisanti, M. Crochemore, and M.-F. Sagot, IEEE/ACM Transactions on Computational Biology and Bioinformatics 2(1) 40-50, 2005.
• No Sorting? Better Searching!, with G. Franceschini, IEEE Symposium on Foundations of Computer Science (FOCS 2004), [full version].
• A Comparative Study of Bases for Motif Inference, with N. Pisanti, M. Crochemore, M.-F. Sagot, in NATO volume on String Algorithmics, 2004.
• A General Technique for Managing Strings in Comparison-Driven Data Structures, with G. Franceschini, International Colloquium on Automata, Languages and Programming (ICALP 2004).
• A Trie-Based Approach for Compacting Automata, with M. Crochemore, C. Epifanio and F. Mignosi, Symposium on Combinatorial Pattern Matching (CPM 2004).
• Fast Compression with a Static Model in High-Order Entropy, with L. Foschini, A. Gupta and J.S. Vitter, IEEE Data Compression Conference (DCC 2004).
• Implicit B-trees: A New Data Structure for the Dictionary Problem, with G. Franceschini, J.I. Munro and L. Pagli, Journal of Computer and System Sciences 68(4) 788-807, 2004 (special issue of IEEE FOCS).
• When Indexing Equals Compression: Experiments with Compressing Suffix Arrays and Applications, with A. Gupta and J.S. Vitter, ACM-SIAM Symposium on Discrete Algorithms (SODA 2004).
• A basis of tiling motifs for generating repeated patterns and its complexity for higher quorum, with N. Pisanti, M. Crochemore and M.-F. Sagot, International Symposium on Mathematical Foundations of Computer Science (MFCS 2003) [TR-03-02].
• Optimal worst-case operations for implicit cache-oblivious search trees, with G. Franceschini, Workshop on Algorithms and Data Structures (WADS 2003).
• Optimal cache-oblivious implicit dictionaries, with G. Franceschini, International Colloquium on Automata, Languages and Programming (ICALP 2003).
• Search data structures for skewed strings, with P. Crescenzi and G.F. Italiano, International Workshop on Efficient and Experimental Algorithms (WEA 2003).
• High-order entropy-compressed text indexes, with A. Gupta and J.S. Vitter, ACM-SIAM Symposium on Discrete Algorithms (SODA 2003).
• Implicit dictionaries supporting searches and amortized updates in O(lg n lglg n) time, with G. Franceschini, ACM-SIAM Symposium on Discrete Algorithms (SODA 2003).
• Text sparsification via local maxima, with P. Crescenzi, A. Del Lungo, E. Lodi, L. Pagli and G. Rossi, Theoretical Computer Science 304(1):341-364, 2003.
• Implicit B-trees: New results for the dictionary problem, with G. Franceschini, J.I. Munro and L. Pagli, IEEE Symposium on Foundations of Computer Science (FOCS 2002).
• Compressed Indexes for fast search in sequencs, with J.S. Vitter, keynote address at Joint Conference on Information Sciences (JCIS 2002).
• Optimal deterministic protocols for mobile robots on a grid, with A. Pietracaprina and G. Pucci, Information and Computation 173(2) 132-142, 2002.

-:- STRUTTURE DI DATI E ALGORITMI

Strutture di dati e algoritmi Progettazione, analisi e visualizzazione P. Crescenzi, G. Gambosi, R. Grossi Addison-Wesley Pearson Education, 2006 PREFAZIONE     SOMMARIO   cap.1     cap.5     cap.6   www.algoritmica.org

-:- MISCELLANEA

• Contact me for some interesting programming contests:
  ACM International Collegiate Programming Contest (Gara per studenti universitari)
  International Olympiad in Informatics (Olimpiadi Internazionali di Informatica) [1] [2] [3] [4]
  Turing Machine Contest (Gara di Informatica per studenti delle scuole superiori)
• Glossary for students (in Italian).
• Local weather forecast and webcam for PISA.
• Fabrizio Luccio believes that this piece of great literature refers to me :-)
• The old version of these pages is here.