Contact

address
Jordi Petit
Departament de Ciències de la Computació
Universitat Politècnica de Catalunya
Campus Nord, edifici Omega, despatx 227
Jordi Girona Salgado, 1-3
08034 Barcelona
Catalunya (Spain)

Teaching

Research

Interests

My main area of research is Algorithm Engineering. I have worked on topics such as the design, analysis and implementation of algorithms and data structures (in sequential, distributed and parallel settings), heuristic approaches to combinatorial optimization problems, and the use of probabilistic models to study fundamental aspects of sensor networks. My current work deals with the design of combinatorial algorithms for the placement and routing of transistors in nanometric geometries.

Current projects

Past projects

Publications

Journals

Marta Ruiz Costa-jussà, Lluis Formiga, Oriol Torrillas, Jordi Petit, and José Adrián Rodríguez Fonollosa. A MOOC on approaches to machine translation. IRRODL, 16(6), December 2015. DOI web

Jordi Cortadella, Jordi Petit, Sergio Gómez, and Francesc Moll. A Boolean Rule-Based Approach for Manufacturability-Aware Cell Routing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 33(3):409–422, March 2014. DOI web

Jordi Petit. Addenda to the survey of layout problems. Bulletin of the European Association for Theoretical Computer Science, (105):177–201, 2011. .pdf

L. Frias, J. Petit, and S. Roura. Lists revisited: Cache conscious STL lists. ACM Journal of Experimental Algorithmics, 14:5–27, 2009. DOI web

J. Petit. Book review: Algorithms and Data Structures by K. Mehlhorn and P. Sanders. Computer Science Reviews, 3:47–51, 2009. web

C. Àlvarez, J. Díaz, J. Petit, J. Rolim, and M. Serna. High level communication functionalities for wireless sensor networks. Theoretical Computer Science, 406:240–247, 2008. web

C. Àlvarez, R. Cases, J. Díaz, J. Petit, and M. Serna. Communication tree problems. Theoretical Computer Science, 381:197–217, 2007. web

E. Alba, F. Almeida, M. Blesa, C. Cotta, M. Díaz, I. Dorta, J. Gabarró, C. León, G. Luque, J. Petit, C. Rodríguez, A. Rojas, and F. Xhafa. Efficient parallel LAN/WAN algorithms for optimization. Parallel Computing, 32:415–440, 2006. web

M. Blesa, J. Petit, and F. Xhafa. Generic parallel implementations for tabu search. International Journal of Computer Systems Science and Engineering, 21(6):413–432, 2006. web

J. Petit. Experiments on the minimim linear arrangement problem. ACM Journal of Experimental Algorithmics, 8, 2003. web

J. Díaz, J. Petit, and M. Serna. A random graph model for optical smart dust networks. IEEE Transactions on Mobile Computing, 2(3):186–196, 2003. web

J. Petit. Combining spectral sequencing and parallel simulated annealing for the MinLA problem. Parallel Processing Letters, 13(1):77–91, 2003. web

J. Díaz, J. Petit, and M. Serna. A survey on graph layout problems. ACM Computing Surveys, 34(3):313–356, 2002. web

J. Díaz, J. Petit, and M. Serna. Faulty random geometric networks. Parallel Processing Letters, 10(4):343–357, 2001. web

J. Díaz, M. D. Penrose, J. Petit, and M. Serna. Approximating layout problems on random geometric graphs. Journal of Algorithms, 39(1):78–116, 2001. web

J. Díaz, J. Petit, M. Serna, and L. Trevisan. Approximating layout problems on random graphs. Discrete Mathematics, 235(1–3):245–253, 2001. web

J. Díaz, M. D. Penrose, J. Petit, and M. Serna. Convergence theorems for some layout measures on random lattice and random geometric graphs. Combinatorics, Probability and Computing, 9(6):489–511, 2000. web

Conferences

M.J. Blesa, A. Duch, J. Gabarró, J. Petit, and M. Serna. Análisis de la evolución de un curso: productividad y desigualdad. In Actas de las XXII Jornadas sobre Enseñanza Universitaria de la Informática, volume 1, pages 161–168, 2016. web

M.J. Blesa, A. Duch, J. Gabarró, J. Petit, and M.J. Serna. Continuous assessment in the evolution of a CS1 course: The pass rate/workload ratio. In Computer Supported Education - 7th International Conference, CSEDU 2015, Lisbon, Portugal, May 23-25, 2015, Revised Selected Papers, volume 583 of Communications in Computer and Information Science, pages 313–332. Springer, 2015. DOI web

A. Duch, J. Gabarró, J. Petit, M. J. Blesa, and M. J. Serna. A cost-benefit analysis of continuous assessment. In Proceedings of the 7th International Conference on Computer Supported Education, pages 57–66. SCITEPRESS, 2015. DOI web

Marta R. Costa-jussà, Lluís Formiga, Jordi Petit, and José A. R. Fonollosa. Detailed description of the development of a MOOC in the topic of statistical machine translation. In Alexander Gelbukh, Félix Castro Espinoza, and Sofía N. Galicia-Haro, editors, Human-Inspired Computing and Its Applications, volume 8856 of Lecture Notes in Computer Science, pages 92–98. Springer International Publishing, 2014. DOI web

A. Mani, D. Venkataramani, J. Petit, and S. Roura. Better feedback for educational online judges. In Proceedings of the 6th International Conference on Computer Supported Education, pages 176–183. SCITEPRESS, 2014. DOI web

J. Cortadella, J. de San Pedro, N. Nikitin, and J. Petit. Physical planning for the architectural exploration of large-scale chip multiprocessors. In 7th International Symposium on Networks-on-Chip (NOCS 2013), 2013. web

J. Cortadella, J. de San Pedro, N. Nikitin, and J. Petit. Physical-aware system-level design for tiled hierarchical chip multiprocessors. In International Symposium on Physical Design (ISPD'13), pages 3–10, 2013. web

A. Duch, J. Petit, E. Rodríguez-Carbonell, and S. Roura. Fun in CS2. In Proceedings of the 5th International Conference on Computer Supported Education (CSEDU'13), pages 437–442. SCITEPRESS, 2013. DOI web

J. Carmona, J. Cortadella, J. de San Pedro, and J. Petit. Integrating formal verification in an on-line judge for e-learning digital circuit design. In Proc. of the 43rd ACM Technical Symposium on Computer Science Education (SIGCSE-2012), pages 451–456. Association for Computing Machinery, 2012. web

O. Giménez, J. Petit, and S. Roura. Jutge.org: An educational programming judge. In Proc. of the 43rd ACM Technical Symposium on Computer Science Education (SIGCSE-2012), pages 445–450. Association for Computing Machinery, 2012. web

M. Blesa, J. Anguera, J. Farré, V. López, and J. Petit. Topology control algorithms in WISELIB. ICSE Workshop on Software Engineering for Sensor Network Applications, 0, 2010. web

L. Frias and J. Petit. Combining digital access and parallel partition for quicksort and quickselect. ICSE Workshop on Multicore Software Engineering, 0:33–40, 2009. web

O. Giménez, J. Petit, and S. Roura. Programació 1: A pure problem-oriented approach for a CS1 course. In C. Hermann, T. Lauer, T. Ottmann, and M. Welte, editors, Proc. of the Informatics Education Europe IV (IEE-2009), pages 185–192, Freiburg, 2009. ISBN: 978-84-692-2758-9.

J. Petit and S. Roura. Programación-1: Una asignatura orientada a la resolución de problemas. In I. Jacob and D. López, editors, XV Jornadas de Enseñanza Universitaria de la Informática, pages 185–192. ISBN: 978-84-692-2758-9, 2009. web

L. Frias and J. Petit. Parallel partition revisited. In C. McGeoch, editor, Experimental Algorithms, volume 5038 of Lecture Notes in Computer Science, pages 142–153, Berlin, 2008. Springer. web

L. Frias, J. Petit, and S. Roura. Lists revisited. In C. Àlvarez and M. Serna, editors, Experimental Algorithms, volume 4007 of Lecture Notes in Computer Science, pages 121–133, Berlin, 2006. Springer. web

J. Díaz, J. Petit, and D. Thilikos. Kernels for the vertex cover problem on the preferred attachment model. In C. Àlvarez and M. Serna, editors, Experimental Algorithms, volume 4007 of Lecture Notes in Computer Science, pages 231–240, Berlin, 2006. Springer. web

E. Levy, G. Louchard, and J. Petit. A distributed algorithm to find hamiltonian cycles in gnp random graphs. In A. López-Ortiz and A. Hamel, editors, First Workshop on Combinatorial and Algorithmic Aspects of Networking, CAAN 2004, volume 3405 of Lecture Notes in Computer Science, pages 63–74, Berlin, 2005. Springer–Verlag. web

C. Àlvarez, J. Díaz, J. Petit, J. Rolim, and M. Serna. Efficient and reliable high level communicatioon in randomly deployed sensor networks. In 2nd ACM International Workshop on Mobility Management and Wireless Access Protocols (Mobiwac 2004), pages 106–110. ACM Press, 2004. web

G. Arzhantseva, J. Díaz, J. Petit, J. Rolim, and M. Serna. Broadcasting on networks of sensors communicating through directional antennas. In P. Spirakis, A. Kameas, and S. Nikoletseas, editors, International Workshop on Ambient Intelligence Computing, pages 1–12, CTI Press, 2003. Ellinika Grammata.

J. Díaz, J. Petit, and M. Serna. Evaluation of basic protocols for optical smart dust networks. In K. Jansen, M. Margraf, M. Mastrolli, and J. Rolim, editors, Experimental and Efficient Algorithms, volume 2647 of Lecture Notes in Computer Science, pages 97–106, Berlin, 2003. Springer–Verlag. web

E. Alba, F. Almeida, M. Blesa, J. Cabeza, C. Cotta, M. Diaz, I. Dorta, J. Gabarró, C. León, J. Luna, L. Moreno, C. Pablos, J. Petit, A. Rojas, and F. Xhafa. MALLBA: A library of skeletons for combinatorial optimization. In B. Monien and R. Feldmann, editors, Euro-Par 2002 Parallel Processing, volume 2400 of Lecture Notes in Computer Science, pages 927–932, Berlin, 2002. Springer–Verlag. web

J. Petit. Hamiltonian cycles in faulty random geometric networks. In C. Kaklamanis, editor, Proceedings of the 2nd International Workshop on Approximation and Randomization Algorithms in Communication Networks (ARACNE 2001), volume 12 of Proceedings in Informatics, pages 97–110, Canada, 2002. Carleton Scientific. .ps.gz .pdf

E. Alba, F. Almeida, M. Blesa, C. Cotta, M. Diaz, I. Dorta, J. Gabarró, J. González, C. León, L. Moreno, J. Petit, J. Roda, A. Rojas, and F. Xhafa. MALLBA: Towards a combinatorial optimization library for geographically distributed systems. In J. Duato, editor, Actas de las XII jornadas de paralelismo, number ISBN 84-9705-043-6 in Editorial Universitat Politècnica de València, pages 105–110, 2001. web

C. Àlvarez, R. Cases, J. Díaz, J. Petit, and M. Serna. Routing trees for random graphs. In J. Rolim, editor, ICALP Workshops 2000, volume 8 of Proceedings in Informatics, pages 99–110, Canada, 2000. Carleton Scientific. .ps.gz .pdf

J. Díaz, M. Penrose, J. Petit, and M. Serna. Linear ordering of random geometric graphs. In P. Wiedmayer and G. Neyer, editors, Graph Theoretic Concepts in Computer Science, volume 1665 of Lecture Notes in Computer Science, Berlin, 1999. Springer–Verlag. web

J. Díaz, M. D. Penrose, J. Petit, and M. Serna. Layout problems on lattice graphs. In T. Asano, H. Imai, D. T. Lee, S. Nakano, and T. Tokuyama, editors, Computing and Combinatorics, volume 1627 of Lecture Notes in Computer Science, pages 103–112, Berlin, 1999. Springer–Verlag. web

J. Díaz, J. Petit, and M. Serna. Random geometric problems on [0,1]2. In J. Rolim, M. Luby, and M. Serna, editors, Randomization and Approximation Techniques in Computer Science, volume 1518 of Lecture Notes in Computer Science, pages 294–306, Berlin, 1998. Springer–Verlag. web

J. Díaz, J. Petit, P. Psycharis, and M. Serna. A parallel algorithm for sampling matchings from an almost uniform distribution. In Kyung-Yong Chwa and Oscar H. Ibarra, editors, Algorithms and Computation, number 1533 in Lecture Notes in Computer Science, pages 457–466, Berlin, 1998. Springer–Verlag. web

J. Petit. Approximation heuristics and benchmarkings for the MinLA problem. In R. Battiti and A. Bertossi, editors, Alex '98 — Building bridges between theory and applications, pages 112–128. Università di Trento, 1998. .ps.gz .pdf

J. Gabarró and J. Petit. ParaDict, a data parallel library for dictionaries (extended abstract). In Euromicro Workshop on Parallel and Distributed Processing, pages 163–170. IEEE Computer Society Press, 1997. web

Chapters in books

J. Díaz, J. Petit, and M. Serna. A guide to concentration bounds. In S. Rajasekaran, P. Pardalos, J. Reif, and J. Rolim, editors, Handbook on Randomized Computing, volume II, chapter 12, pages 457–507. Kluwer Press, New York, 2001. web

M. J. Blesa, J. Petit, and F. Xhafa. Computación en Internet: Librería MALLBA para problemas de optimización. In Ciencia y Tecnología, volume II, pages 9–12. Tibidabo Ediciones, Barcelona, 2001. ISBN: 84-8033-145-3. web

Resources

Jutge.org
The Virtual Learning Environment for Computer Programming.

CellRouting
Layouts of the Nangate FreePDK45 Generic Open Cell Library automatically generated by EDA tools for automatic transistor placement and detailed routing for the paper A Boolean Rule-Based Approach for Manufacturability-Aware Cell Routing.

MinLA
Minimum Linear Arrangement Problem: instances, codes and results.

AlgoTeX
Tools to write algorithms in Latex.

Concurs UPC
Concurs de Programació de la UPC.

AlgoProg
Lliçons d’Algorísmia i Programació.