In this paper, we address a natural question at the intersection of combinatorial game theory and computational complexity: “Can a sum of simple tepid games in canonical form be intractable?” To resolve this fundamental question, we consider superstars , positions first introduced in Winning Ways where all options are nimbers . Extending Morris’ classic result with hot games to tepid games, we prove that disjunctive sums of superstars are intractable to solve. This is striking as sums of nimbers can be computed in linear time. Our analysis shows that the game Paint Can is intractable and also yields a new intractable game, Blackout . We present web-playable versions of both games.

Concept inventories are standardized assessments that evaluate student understanding of key concepts within academic disciplines. While prevalent across STEM fields, their development lags for advanced computer science topics like dynamic programming (DP)---an algorithmic technique that poses significant conceptual challenges for undergraduates. To fill this gap, we developed and validated a Dynamic Programming Concept Inventory (DPCI). We detail the iterative process used to formulate multiple-choice questions targeting known student misconceptions about DP concepts identified through prior research studies. We discuss key decisions, tradeoffs, and challenges faced in crafting probing questions to subtly reveal these conceptual misunderstandings. We conducted a preliminary psychometric validation by administering the DPCI to 172 undergraduate CS students finding our questions to be of appropriate difficulty and effectively discriminating between differing levels of student understanding. Taken together, our validated DPCI will enable instructors to accurately assess student mastery of DP. Moreover, our approach for devising a concept inventory for an advanced theoretical computer science concept can guide future efforts to create assessments for other under-evaluated areas currently lacking coverage.

Algorithms courses are a core part of many CS programs, but have received little focus in computing education, lacking statistical data about how they are generally taught. To remedy this, we present the results of the first large-scale comprehensive survey of undergraduate introductory algorithms courses at four-year institutions in the United States. Questions in the survey targeted instructor information, course concepts, the ways students are evaluated, challenges instructors encountered, and instructor envisioned improvements. We received 87 responses from 34 different states, across a wide variety of 4-year institutions. The results indicate that algorithms courses vary dramatically in most surveyed areas.

We settle two long-standing complexity-theoretical questions—open since 1981 and 1993—in combinatorial game theory (CGT). We prove that the Grundy value of Undirected Geography is PSPACE-complete to compute. This exhibits a stark contrast with a result from 1993 that Undirected Geography is polynomial-time solvable. By distilling to a simple reduction, our proof further establishes a dichotomy theorem, providing a sharp “phase transition to intractability”: The Grundy value of the game over any degree-three graph is polynomial-time computable, but over degree-four graphs—even when planar & bipartite—is PSPACE-hard. Additionally, we show, for the first time, how to construct Undirected Geography instances with Grundy value *n and size polynomial in n. We strengthen a result from 1981 showing that sums of tractable partisan games are PSPACE-complete in two fundamental ways. First, we extend the result to impartial games, a strict subset of partisan. Second, the 1981 construction is not built from a natural ruleset, instead using a long sum of tailored short-depth game positions. We use the sum of two Undirected Geography positions. Our result also has computational ramification to Sprague-Grundy Theory (1930s) which shows that the Grundy value of the disjunctive sum of any two impartial games can be computed—in polynomial time—from their Grundy values. In contrast, we prove that, assuming PSPACE is not equal to P, there is no general polynomial-time method to summarize two polynomial-time solvable impartial games to efficiently solve their disjunctive sum. Our proof enables us to answer another long-term structural question in the field. We establish the following complexity independence: Unless$\mathrm{P}= \text{PSPACE}$, there is no polynomial-time reduction from winnability in misere-play setting to the Grundy value, and vice versa (in Undirected Geography).