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

Grau en Enginyeria Informàtica

Grau en Ciència i Enginyeria de Dades

Master in Innovation and Research in Informatics

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

M. Blesa, A. Duch, J. Gabarró, J. Petit, and M. Serna. Economía aplicada al estudio de la evolución de un curso. ReVisión, 10(1), January 2017. web

J. Petit, S. Roura, J. Carmona, J. Cortadella, A. Duch, O. Gimenez, A. Mani, J. Mas, E. Rodriguez-Carbonella, A. Rubio, J. de San Pedro, and D. Venkataramani. Jutge.org: Characteristics and experiences. IEEE Transactions on Learning Technologies, PP(99), 2017. DOI

Marta Ruiz Costa-jussà, Lluis Formiga, Oriol Torrillas, Jordi Petit, and José Adrián Rodríguez Fonollosa. A MOOC on approaches to machine translation. International Review of Research in Open and Distributed Learning, 16(6), December 2015. DOI

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

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

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

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

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. DOI

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

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. DOI

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. DOI

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

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. DOI

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

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

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

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. DOI

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

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. DOI

Conferences

Alex Vidal-Obiols, Jordi Cortadella, and Jordi Petit. Under-the-cell routing to improve manufacturability. In Proceedings of the on Great Lakes Symposium on VLSI 2017, GLSVLSI '17, pages 125–130, New York, NY, USA, 2017. ACM. DOI

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

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

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

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

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

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

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. DOI

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. DOI

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. DOI

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. DOI

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. DOI

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

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.

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. DOI

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. DOI

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. DOI

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. DOI

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. DOI

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. DOI

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

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. 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, 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

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. 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, 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. 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. 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. 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. 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

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

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

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ó.