About

Jeff Erickson has been a faculty member at the University of Illinois since 1998 and became a full professor in 2010. He was named the Sohaib and Sara Abbasi Professor in 2020. His research spans computational geometry, computational topology, graph algorithms, and related topics at the intersection of computer science and mathematics. Most of his recent work focuses on computer science education, particularly on best practices for teaching algorithm design effectively, equitably, and at scale. He has published over 100 technical papers and is the author of a popular free algorithms textbook. Erickson has held various leadership roles, including chairing the community-elected steering committee for the International Symposium on Computational Geometry and serving as a SafeTOC advocate for SOCG and SODA. He primarily teaches large algorithms classes and has been recognized with numerous awards, including a Sloan Research Fellowship, an NSF CAREER award, and a University Distinguished Teacher-Scholar Award. His professional background also includes roles such as associate department head, faculty advisory committee chair, and project manager, among others.

Research topics

• Computer Science
• Mathematics
• Artificial Intelligence
• Discrete mathematics
• Mathematics education
• Programming language
• Engineering
• Combinatorics
• Algorithm

Selected publications

• Shelling and Sinking Graphs on the Sphere

  ArXiv.org · 2025-01-01

  articleOpen access1st authorCorresponding

  We describe a promising approach to efficiently morph spherical graphs, extending earlier approaches of Awartani and Henderson [Trans. AMS 1987] and Kobourov and Landis [JGAA 2006]. Specifically, we describe two methods to morph shortest-path triangulations of the sphere by moving their vertices along longitudes into the southern hemisphere; we call a triangulation sinkable if such a morph exists. Our first method generalizes a longitudinal shelling construction of Awartani and Henderson; a triangulation is sinkable if a specific orientation of its dual graph is acyclic. We describe a simple polynomial-time algorithm to find a longitudinally shellable rotation of a given spherical triangulation, if one exists; we also construct a spherical triangulation that has no longitudinally shellable rotation. Our second method is based on a linear-programming characterization of sinkability. By identifying its optimal basis, we show that this linear program can be solved in O(n^{ω/2}) time, where ω is the matrix-multiplication exponent, assuming the underlying linear system is non-singular. Finally, we pose several conjectures and describe experimental results that support them.

  PublisherOA PDFDOI

• Novice Difficulties in Graph Layering for Algorithm Design

  2025-02-18 · 1 citations

  articleSenior author

  Graph data structures and algorithms play an essential role in computer science, and one of the ultimate goals of learning graphs is to solve more complicated algorithm design problems with them. A common way to solve a novel, complex problem is to reduce the problem to a standard graph problem, which often requires modeling a graph, and one essential way to model a graph is a technique called graph layering. Graph layering is often considered difficult by students and rarely studied by computer science education researchers despite its significance in algorithm design. To understand students' struggles with graph layering and improve teaching of algorithm designs, we conducted this qualitative study using think-aloud interviews with current students from an algorithm course. Participants were asked to solve algorithm design problems meant to be solved with graph layering. We used thematic analysis to extract difficulties observed in these interviews. We share our preliminary findings in this poster, and propose next steps for this study and future research.

  PublisherDOI

• FSM Builder: A Tool for Writing Autograded Finite Automata Questions

  arXiv (Cornell University) · 2024-05-02

  preprintOpen accessSenior author

  Deterministic and nondeterministic finite automata (DFAs and NFAs) are abstract models of computation commonly taught in introductory computing theory courses. These models have important applications (such as fast regular expression matching), and are used to introduce formal language theory. Undergraduate students often struggle with understanding these models at first, due to the level of abstraction. As a result, various pedagogical tools have been developed to allow students to practice with these models. We introduce the FSM Builder, a new pedagogical tool enabling students to practice constructing DFAs and NFAs with a graphical editor, giving personalized feedback and partial credit. The algorithms used for generating these are heavily inspired by previous works. The key advantages to its competitors are greater flexibility and scalability. This is because the FSM Builder is implemented using efficient algorithms from an open source package, allowing for easy extension and question creation. We discuss the implementation of the tool, how it stands out from previous tools, and takeaways from experiences of using the tool in multiple large courses. Survey results indicate the interface and feedback provided by the tool were useful to students.

  PublisherOA PDFDOI

• A Survey of Undergraduate Theory of Computing Curricula

  2024-12-02 · 9 citations

  article

  Theory of Computing (ToC) is an important aspect of nearly every undergraduate CS curriculum, as it concerns what computation fundamentally means. However, there has been little research into ToC pedagogy, both within the classroom and how it fits within its institutional context. We propose in this working group to create a survey of current ToC pedagogy. Our goals are to create a standard for teaching ToC, find trends, determine under-researched areas, and to build a community among ToC educators.

  PublisherDOI

• Auto-graded Scaffolding Exercises For Theoretical Computer Science

  2024 · 8 citations

  1st authorCorresponding
  • Computer Science
  • Computer Science
  • Mathematics education

  Abstract This paper describes an ongoing effort to develop auto-graded scaffolding exercises to support an upper-division theoretical computer science class at a large Midwestern public university. The course covers a mixture of formal languages, automata theory, and design and analysis of algorithms. The course has a steady-state enrollment of 400 students per semester, almost all undergraduates majoring in computer science or computer engineering, for whom the course is required. Most of our auto-graded exercises are organized as guided problem sets. Each guided problem set consists of a small number of multi-stage exercises, implemented as a sequence of questions that guide students through the process of solving a design or proof question. Our guided problem sets support multiple correct solutions, detect common mistakes, automatically provide counterexamples for incorrect answers, provide helpful narrative feedback, and award partial credit consistent with grading rubrics for written homeworks and exams. Some exercises incorporate new interactive elements that enable students to submit solutions similar to written homework. These elements allow drawing finite state machines, writing structured sentences that are auto-graded and provide feedback, and drag-and-drop blocks for writing proofs and pseudocode. We report the results of a student survey to gauge the effectiveness of our scaffolding exercises to help students master the material, and just as importantly, to improve their confidence in that mastery.

  PublisherOA PDFDOI

• FSM Builder: A Tool for Writing Autograded Finite Automata Questions

  2024-07-03 · 7 citations

  articleSenior author

  Deterministic and nondeterministic finite automata (DFAs and NFAs) are abstract models of computation commonly taught in introductory computing theory courses. These models have important applications (such as fast regular expression matching), and are used to introduce formal language theory. Undergraduate students often struggle with understanding these models at first, due to the level of abstraction. As a result, various pedagogical tools have been developed to allow students to practice with these models.

  PublisherDOI

• A Survey of Undergraduate Theory of Computation Curricula in the United States

  2024-12-05 · 1 citations

  article

  Theory of computation (ToC), the subfield of theoretical computer science concerned with automata, formal languages, grammars, computability, and the foundations of complexity theory, among other topics, is a staple of undergraduate computer science programs. Nevertheless the teaching of ToC is severely understudied from the perspective of computing education research (CER).

  PublisherDOI

• Minimum Cuts in Surface Graphs

  SIAM Journal on Computing · 2023-02-13

  article

  We describe algorithms to efficiently compute minimum -cuts and global minimum cuts of undirected surface-embedded graphs. Given an edge-weighted undirected graph with vertices embedded on an orientable surface of genus , our algorithms can solve either problem in or time, whichever is better. When is a constant, our time algorithms match the best running times known for computing minimum cuts in planar graphs. Our algorithms for minimum cuts rely on reductions to the problem of finding a minimum-weight subgraph in a given -homology class, and we give efficient algorithms for this latter problem as well. If is embedded on a surface with genus and boundary components, these algorithms run in and time. We also prove that finding a minimum-weight subgraph homologous to a single input cycle is NP-hard, showing that it is likely impossible to improve upon the exponential dependencies on for this latter problem.

  PublisherDOI

• Reconstructing Graphs from Connected Triples

  Lecture notes in computer science · 2023-01-01 · 3 citations

  book-chapter
  PublisherDOI

• Reconstructing Graphs from Connected Triples

  arXiv (Cornell University) · 2023-03-12

  preprintOpen access

  We introduce a new model of indeterminacy in graphs: instead of specifying all the edges of the graph, the input contains all triples of vertices that form a connected subgraph. In general, different (labelled) graphs may have the same set of connected triples, making unique reconstruction of the original graph from the triples impossible. We identify some families of graphs (including triangle-free graphs) for which all graphs have a different set of connected triples. We also give algorithms that reconstruct a graph from a set of triples, and for testing if this reconstruction is unique. Finally, we study a possible extension of the model in which the subsets of size $k$ that induce a connected graph are given for larger (fixed) values of $k$.

  PublisherOA PDFDOI

Recent grants

• AF:Small:Optimization in surface-embedded graphs

  NSF · $500k · 2009–2014

• MSPA-MCS: Fundamental Geodesic Problems in Computational Topology

  NSF · $500k · 2005–2008

• CAREER: Realistically Efficient Geometric Algorithms

  NSF · $325k · 2001–2007

• AF: Medium: Collaborative Research: Fast and accurate optimization in planar graphs and beyond

  NSF · $550k · 2014–2019

Frequent coauthors

• Erin Wolf Chambers

  22 shared

• Erik D. Demaine

  21 shared

• Amir Nayyeri

  18 shared

• Éric Colin de Verdière

  11 shared

• Stefan Langerman

  11 shared

• Kyle Fox

  The University of Texas at Dallas

  11 shared

• David Eppstein

  9 shared

• Mark Overmars

  9 shared

Education

• Ph.D., Computer Science

  University of California, San Diego

  1996

• M.S., Computer Science

  University of California, San Diego

  1993

• B.S., Computer Science

  University of California, San Diego

  1991

Awards & honors

• Sloan Research Fellowship
• NSF CAREER award
• University Distinguished Teacher-Scholar Award