Theory of Computation (ToC) is fundamental but notoriously challenging for undergraduates, often resulting in high dropout rates and low engagement. In this paper, we argue that incorporating gamification and carefully chosen analogies can significantly improve student comprehension and motivation in ToC and related theoretical computer science topics. Drawing on constructivist and experiential learning theories, we present a position that game-based activities and concrete analogical models help students actively construct understanding of abstract concepts. Building on prior literature and classroom experience, we propose a reusable curricular framework that organizes revised games and analogies across major ToC topics—regular and context-free languages, Turing machines, and decidability. For each topic, we outline an in-class gamified activity or analogy and summarize these methods and their pedagogical usage in a structured table. Our position is that these approaches are pedagogically effective and adaptable for enhancing instruction across upper-level theoretical computer science courses.

Learning formal concepts in Theory of Computation (ToC) can be challenging for students, and visualization tools can assist in comprehension of ToC concepts. We present a literature review of visualization tools developed for teaching ToC topics, including automata theory, computability theory, and complexity theory. Using a comprehensive search strategy across major libraries, we identified 47 primary studies from 1988--2025 that met our inclusion criteria. We found that the majority of tools target automata (especially finite automata), while relatively fewer tools address proof techniques and complexity topics, though interest in these areas has recently grown. We observed two periods of heightened development of ToC visualization tools: an initial wave around the late 1990s to mid-2000s, and a resurgence in the early 2020s with more interactive and web-based tools.

Collaborative learning has been promoted for decades as a way to increase engagement, equity, and learning gains in computer–science (CS) classrooms. The evidence for where and how these practices are studied across the CS curriculum has not yet been assessed. This poster gives an initial literature review of peer-reviewed CS-education publications that explicitly investigate collaborative learning strategies. Using a ACM Digital Library query, we identified 218 relevant publications about collaborative learning and CS education. Over two-thirds of the literature targets introductory programming and algorithms courses; more ''advanced'' topics such as operating systems, computer architecture, and theoretical CS collectively account for under 10%.

How do we help undergraduates master the rigorous material of Theory of Computing and Algorithms courses while keeping them engaged and confident, especially in the era of Generative AI? Additionally, what goals do educators of these courses believe are important? This panel's goal is to further the discussion of these questions. The panel consists of four educators from distinct institution types who will share evidence-based, classroom-tested strategies for these courses. After the panel gives their position statements, the moderator will guide a structured discussion on motivating abstract topics, assessment and feedback at scale, integrating contemporary tools, and aligning theory/algorithms courses with varied curricula. Specifically, the panel will discuss Generative AI and Large Language Models' place within these courses, the pedagogical implications of autograder usage in these courses, and broader learning goals educators should strive for in these courses.

Traditional assessment methods often fall short in promoting the critical thinking and argumentative skills necessary for understanding and mastering abstract topics. This paper addresses the challenge of conceptual understanding and communication skills in upper division Computer Science (CS) courses, specifically theory of computing (ToC). We describe a three-year implementation of a formal writing and peer reviewing project within our ToC course. The project iteratively evolved over this time based on incentives involving student workload and feedback opportunities to allow student groups to iteratively improve their writing and to collaborate more. We performed quantitative analysis of formative and summative grades and qualitative thematic analysis of reviewer comments. We found that increasing the number of peer review opportunities correlates with a shift in feedback focus from fundamental proof correctness to clarity and presentation.

Automating the grading of theoretical computer science (TCS) problems has the potential to save instructors significant time while providing students with consistent feedback. This poster explores the efficacy of a large language model (LLM) in automatically grading undergraduate-level TCS problems. We focus on common topics such as creating context-free grammars and pushdown automata, converting grammars to Chomsky Normal Form, designing Turing machines, and proving languages undecidable via reductions. For each problem type, we developed a rubric and generated a dataset of student-like solutions, some correct and others with typical student errors. The LLM was tasked with scoring these solutions according to the rubric, and its grades were compared to human instructor grades. Our results show that the LLM can often mimic human grading trends with moderate accuracy, but notable discrepancies arise in specific rubric categories. In particular, the LLM tends to over-penalize formatting and notation issues and sometimes overlooks deeper logical errors.

Large Language Models (LLMs) promise explanations at a scale that traditional office-hours or even intelligent tutoring systems struggle to match. However, their suitability for Computer Science subjects such as Theory of Computing (ToC) remains unanswered due to how LLMs can frequently hallucinate information; the goal of ToC courses is proving precise statements rigorously. In this poster we evaluate OpenAI's GPT-4 model across 18 ToC sub-topics involving regular languages, context-free languages, Turing machines, and (un)decidability. We generated realistic ''average-student'' questions and follow-up ones and then scored each answer with a five-criterion rubric: accuracy, completeness, clarity, pedagogical scaffolding, and quality of follow-up questions. Our overall results show that GPT-4 is marginal at performing as a ToC tutor, and our analysis identifies strengths in conceptual explanation and weak spots for proof-oriented questions, e.g., reductions.

Theoretical Computer Science educators often need to generate solutions to problems in a variety of forms, requiring diagrams and detailed explanations for every step. Currently, solution generation is largely a manual and time-consuming process on the part of the educator. We introduce AUTO-X, an automatic solution generator and explainer, designed for a variety of standard theory problems and conversions. AUTO-X distinguishes itself by producing not only the visual and formal components of a CS theory solution but also by providing step-by-step explanations of the underlying process. Additionally, it is an easily extensible tool for educators when either adding a new CS theory conversion or algorithm, or adapting our existing templates for institutional-specific terminology/standards.

The rapid expansion of Generative AI (GenAI) presents both opportunities and challenges for higher education, particularly in Computer Science. This study investigates the learning and assessment effects of GenAI assistance within an undergraduate Theory of Computing (ToC) course. We used a semester-long project where students documented their GenAI usage for extra credit, and provided the GenAI model choice used, output modifications, self-efficacy, and GenAI usage recommendations. We also collected data on pre- and post-course knowledge tests and project grades. We found that while students predominantly chose OpenAI models and used them for direct output utilization and scaffolding, the overall level of GenAI usage did not significantly correlate with changes in self-efficacy or knowledge gain.

GenAI is playing an increasingly important role in computing courses at all levels, offering new opportunities to support teaching and learning. However, using GenAI effectively raises important concerns regarding trust, academic integrity, and broader social and ethical dimensions. This Working Group was formed to report on the current state of the art in using GenAI in upper-level computing courses to aid educators. The working group will undertake a methodological review of published work and solicit input from the computing educational community as part of the report.

Theory of Computing (ToC) courses are essential because of their connections to other CS courses, serving as a foundation. Traditional ToC courses are structured to be heavily weighted with in-class examinations and the rest for proof-type assignments. Recent published research created a new type of assignment for a ToC course: a ''mock conference'' project. Here, students approach and present ToC problems as if they were submitting to a ''real'' CS conference, and separately anonymously referee other student projects. This prior research noted a disadvantage in that curation of different project topics for groups is prohibitively time-consuming. In this paper we outline a framework about adding scaffolding this assignment and provide our experiences in running such a conference in a small-scale ToC course. We anecdotally found that students were more engaged and can see the connections with other CS courses, both directly and indirectly. On the other hand, we found no statistically significant difference between our scaffolded project and the non-scaffolded version in prior work. We conclude with an extended version of our framework that could be applied to large-scale ToC courses.

Theory of Computing (ToC) courses are important in CS curricula as they promote formal reasoning and writing skills about computation. Large language models (LLMs) have recently upended standard pedagogy in CS courses, but ToC courses have so far been fairly resistant to LLMs as they generally have lacked reasoning abilities. Prior work showed that GPT-4 performed at an ''average'' student level, specifically with a B-/C+ average. Considerable advancements since that prior work have occurred with LLMs in that some now provide ''reasoning'' capabilities. In this poster we tested whether the ChatGPT o1 LLM can perform better than GPT-4 on our ToC course's exams. We found that o1 can solve ToC questions approximately two letter grades higher than GPT-4 could, specifically at an A+ level.

This poster details preliminary work on developing a suite of tools, called TheoryViz, for assisting students within traditional Theory of Computing (ToC) courses. Our goal is for these tools to generate animations automatically. As of this poster, TheoryViz can generate step-by-step animations for building DFAs, simulating them on a given input string, and minimizing them. Crucially, each step links the formal definition of the machine and the visual depiction of that machine with the created animations, and each step moves to the next seamlessly. Our desire is that TheoryViz becomes a new tool for ToC educators to use in the classroom.

Theory of Computing (ToC) courses have important connections to other CS courses as ToC is a foundation for them. ToC course grading schemes often involve mostly exams, and sometimes a small weight for traditional assignments. Recent work experimented with a "mock conference'' project where students write up solutions to ToC problems as if they were submitting them to a "real'' CS conference. In this poster we give our experiences in scaffolding this existing project idea.

Theory of computing (ToC) courses are a staple in many undergraduate CS curricula as they lay the foundation of why CS is important to students. Although not a stated goal, an inevitable outcome of the course is enhancing the students' technical reading and writing abilities as it often contains formal reasoning and proof writing. Separately, many undergraduate students are interested in performing research, but often lack these abilities. Based on this observation, we emulated a common research environment within our ToC course by creating a mock conference assignment where students (in groups) both wrote a technical paper solving an assigned problem and (individually) anonymously refereed other groups' papers. In this paper we discuss the details of this assignment and our experiences, and conclude with reflections and future work about similar courses.

Best practices in programming need to be emphasized in a CS1 course as bad student habits persist if not reinforced well. The C++ programming language, although a relatively old language, has been regularly updated with new versions since 2011, on the pace of once every three years. Each new version contains important features that make the C++ language more complex for backwards compatibility, but often introduce new features to make common use cases simpler to implement. This poster contains experiences in designing a CS1 course that uses the C++ programming language that incorporates "modern" versions of the language from the start, as well as recent conferences about the language. Our goals were to prevent many common bad habits among C++ programmers.

The over-arching question that is continually asked in nearly every Theoretical Computer Science (TCS) course is: " what are the limitations of computers?" The motivation is to start with "simple" machines, explore them, and to determine that they are not sufficiently powerful to handle problems that everyday computers can. Then the course would add " computational power" to these machines so that they can more accurately compute answers to problems students should already know how to do with their own machines. Students then learn about decidability and undecidability, and observe that as computer models get more powerful, the fewer questions about them remain decidable, which is a trade-off. One of the main issues with this approach is the justification of which "simple'' machines to consider initially.

Programming a solver for a video game is a simple way for students to become engaged with solving complex problems within CS1 courses. This assignment involves writing a partial solver for the Alphabear video game, which is to find English words among letters present on a board with decreasing timers. The goal of the game is to maximize earned points, and using each letter before its timer runs out achieves that goal. This partial solver is to determine the "best" word choice at a given point in the game. Students here are to assign a weight to each word, which is specified in the assignment, and to find any word of smallest weight. Some skills necessary to solve the assignment are reading potentially large files, designing a nontrivial algorithm to calculate which word is best, and being exposed to different weighting functions.

Analogies have long been proposed as a valuable teaching mechanism, but the question of whether student-generated analogies are more effective for learning compared to those generated by the instructor has not been answered. We compare three different treatments: no analogy, an analogy provided by the instructor, and analogies generated by students. We apply these treatments to two upper-division computer science courses--Operating Systems (OS) and Programming Languages (PL)--and evaluate student learning. Our findings show that any effect of these treatments on student learning is minimal. We found no practical or statistically significant differences between them. Anecdotally, the student-generated analogies provided an active learning activity, and the instructor-provided analogies were the only ones mentioned in written responses to graded events. Given the small differences in learning, instructors can select the treatment based on their needs; for example, selecting the student-generated option for active learning or the instructor-provided option when time is short.

There is a substantial and growing body of malware samples that evade automated analysis and detection tools. Malware may measure fingerprints (“artifacts”) of the underlying analysis tool or environment, and change their behavior when such artifacts are detected. While analysis tools can mitigate artifacts to reduce exposure, such concealment is expensive and limits scalable automated malware analysis. However, not every sample checks for every type of artifact—analysis efficiency can be improved by mitigating only those artifacts most likely to be used by a sample. Using that insight, we proposeMimosa, a system that identifies a small set of “covering” configurations that collectively and efficiently defeat most malware samples in a corpus.Mimosaidentifies a set of configurations that maximize analysis throughput and detection accuracy while minimizing manual effort, enabling scalable automation for analyzing stealthy malware. We evaluate our approach against a benchmark of 1535 meticulously labeled stealthy malware samples. We further test our approach on an additional set of 1221 stealthy malware samples and successfully analyze nearly 99% of them using only 2 VM backends.Mimosaprovides a practical, tunable method for efficiently deploying malware analysis resources.

It is imperative for testing to determine if the components within large-scale software systems operate functionally. Interaction testing involves designing a suite of tests, which guarantees to detect a fault if one exists among a small number of components interacting together. The cost of this testing is typically modeled by the number of tests, and thus much effort has been taken in reducing this number. Here, we incorporate redundancy into the model, which allows for testing in non-deterministic environments. Existing algorithms for constructing these test suites usually involve one "fast" algorithm for generating most of the tests, and another "slower" algorithm to "complete" the test suite. We employ a genetic algorithm that generalizes these approaches that also incorporates redundancy by increasing the number of algorithms chosen, which we call "stages." By increasing the number of stages, we show that not only can the number of tests be reduced compared to existing techniques, but the computational time in generating them is also greatly reduced.