Novice Difficulties in Graph Layering for Algorithm Design

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.