Computing theory is often perceived as challenging by students, and verifying the correctness of a student’s automaton or grammar is time-consuming for instructors. Aiming to provide benefits to both students and instructors, we designed an automated feedback tool for assignments where students construct automata or grammars. Our tool, built as an extension to the widely popular JFLAP software, determines if a submission is correct, and for incorrect submissions it provides a “witness” string demonstrating the incorrectness.
We studied the usage and benefits of our tool in two terms, Fall 2019 and Spring 2021. Each term, students in one section of the Introduction to Computer Science Theory course were required to use our tool for sample homework questions targeting DFAs, NFAs, RegExs, CFGs, and PDAs. In Fall 2019, this was a regular section of the course.We also collected comparison data from another section that did not use our tool but had the same instructor and homework assignments. In Spring 2021, a smaller honors section provided the perspective from this demographic. Overall, students who used the tool reported that it helped them to not only solve the homework questions (and they performed better than the comparison group) but also to better understand the underlying theory concept. They were engaged with the tool: almost all persisted with their attempts until their submission was correct despite not being able to random walk to a solution. This indicates that witness feedback, a succinct explanation of incorrectness, is effective. Additionally, it assisted instructors with assignment grading.
more »
« less
Witness Feedback for Introductory CS Theory Assignments
Computing theory analyzes abstract computational models to rigorously study the computational difficulty of various problems. Introductory computing theory can be challenging for undergraduate students, and the overarching goal of our research is to help students learn these computational models. The most common pedagogical tool for interacting with these models is the Java Formal Languages and Automata Package (JFLAP). We developed a JFLAP server extension, which accepts homework submissions
from students, evaluates the submission as correct or incorrect, and provides a witness string when the submission is incorrect. Our extension currently provides witness feedback for deterministic finite automata, nondeterministic finite automata, regular expressions, context-free grammars, and pushdown automata.
In Fall 2019, we ran a preliminary investigation on two synchronized sections (Control and Study) of the required undergraduate course Introduction to Computer Science Theory. The Study section (n = 29) used our extension for five targeted homework questions,
and the Control section (n = 35) submitted these problems using traditional means. The Study section strongly outperformed the Control section with respect to the percent of perfect homework grades for the targeted homework questions. Our most interesting
result was student persistence: with only the short witness string as feedback, students voluntarily persisted in submitting attempts until correct.
more »
« less
- Award ID(s):
- 1819546
- NSF-PAR ID:
- 10296082
- Date Published:
- Journal Name:
- 52nd ACM Technical Symposium on Computer Science Education (SIGCSE)
- Page Range / eLocation ID:
- 1300 to 1300
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Step-based tutoring systems are known to be more effective than traditional answer-based systems. They however require that each step in a student’s work be accepted and evaluated automatically to provide effective feedback. In the domain of linear circuit analysis, it is frequently necessary to allow students to draw or edit circuits on their screen to simplify or otherwise transform them. Here, the interface developed to accept such input and provide immediate feedback in the Circuit Tutor system is described, along with systematic assessment data. Advanced simplification methods such as removing circuit sections that are removably hinged, voltage-splittable, or current-splittable are taught to students in an interactive tutorial and then supported in the circuit editor itself. To address the learning curve associated with such an interface, ~70 video tutorials were created to demonstrate exactly how to work the randomly generated problems at each level of each of the tutorials in the system. A complete written record or “transcript” of student’s work in the system is being made available, showing both incorrect and correct steps. Introductory interactive (multiple choice) tutorials are now included on most topics. Assessment of exercises using the interactive editor was carried out by professional evaluators for several institutions, including three that heavily serve underrepresented minorities. Both quantitative and qualitative methods were used, including focus groups, surveys, and interviews. Controlled, randomized, blind evaluations were carried out in three different course sections in Spring and Fall 2019 to evaluate three tutorials using the interactive editor, comparing use of Circuit Tutor to both a commercial answer-based system and to conventional textbook-based paper homework. In Fall 2019, students rated the software a mean of 4.14/5 for being helpful to learn the material vs. 3.05/5 for paper homework (HW), p < 0.001 and effect size d = 1.11σ. On relevant exam questions that semester, students scored significantly (p = 0.014) higher with an effect size of d = 0.64σ when using Circuit Tutor compared to paper HW in one class section, with no significant difference in the other section.more » « less
-
In this proposal, we will share some initial findings about how teacher and student engagement in cogenerative dialogues influenced the development of the Culturally Relevant Pedagogical Guidelines for Computational Thinking and Computer Science (CRPG-CSCT). The CRPG-CSCT’s purpose is to provide computer science teachers with tools to enhance their instruction by accurately reflecting students’ diverse cultural resources in the classroom. Additionally, the CRPG-CSCT will provide guidance to non-computer science teachers on how to facilitate the integration of computational thinking skills to a broad spectrum of classes in the arts, humanities, sciences, social sciences, and mathematics. Our initial findings shared here are part of a larger NSF-funded research project (Award No. 2122367) which aims to better understand the barriers to entry and challenges for success faced by underrepresented secondary school students in computer science, through direct engagement with the students themselves. Throughout the 2022-23 academic year, the researchers have been working with a small team of secondary school teachers, students, and instructional designers, as well as university faculty in computer science, secondary education, and sociology to develop the CRPG-CSCT. The CRPG-CSCT is rooted in the tenets of culturally relevant pedagogy (Ladson-Billings, 1995) and borrows from Muhammad’s (2020) work in Cultivating Genius: An Equity Framework for Culturally and Historically Responsive Literacy. The CRPG-CCT is being developed over six day-long workshops held throughout the academic year. At the time of this submission, five of the six workshops had been completed. Each workshop utilized cogenerative dialogues (cogens) as the primary tool for organizing and sustaining participants’ engagement. Through cogens, participants more deeply learn about students’ cultural capital and the value of utilizing that capital within the classroom (Roth, Lawless, & Tobin, 2000). The success of cogens relies on following specific protocols (Emdin, 2016), such as listening attentively, ensuring there are equal opportunities for all participants to share, and affirming the experiences of other participants. The goal of a cogen is to reach a collective decision, based on the dialogue, that will positively impact students by explicitly addressing barriers to their engagement in the classroom. During each workshop, one member of the research team and one undergraduate research assistant observed the interactions among cogen participants and documented these in the form of ethnographic field notes. Another undergraduate research assistant took detailed notes during the workshop to record the content of small and large group discussions, presentations, and questions/responses throughout the workshops. A grounded theory approach was used to analyze the field notes. Additionally, at the conclusion of each workshop, participants completed a Cogen Feedback Survey (CFS) to gather additional information. The CFS were analyzed through open thematic coding, memos, and code frequencies. Our preliminary results demonstrate high levels of engagement from teacher and student participants during the workshops. Students identified that the cogen structure allowed them to participate comfortably, openly, and honestly. Further, students described feeling valued and heard. Students’ ideas and experiences were frequently affirmed, which served as an important step toward dismantling traditional teacher-student boundaries that might otherwise prevent them from sharing freely. Another result from the use of cogens was the shared experience of participants comprehending views from the other group’s perspective in the classroom. Students appreciated the opportunity to learn from teachers about their struggles in keeping students engaged. Teachers appreciated the opportunity to better understand students’ schooling experiences and how these may affirm or deny aspects of their identity. Finally, all participants shared meaningful suggestions and strategies for future workshops and for the collective betterment of the group. Initial findings shared here are important for several reasons. First, our findings suggest that cogens are an effective approach for fostering participants’ commitment to creating the conditions for students’ success in the classroom. Within the context of the workshops, cogens provided teachers, students, and faculty with opportunities to engage in authentic conversations for addressing the recruitment and retention problems in computer science for underrepresented students. These conversations often resulted in the development of tangible pedagogical approaches, examples, metaphors, and other strategies to directly address the recruitment and retention of underrepresented students in computer science. Finally, while we are still developing the CRPG-CSCT, cogens provided us with the opportunity to ensure the voices of teachers and students are well represented in and central to the document.more » « less
-
Real-time decision making in IoT applications relies upon space-efficient evaluation of queries over streaming data. To model the uncertainty in the classification of data being processed, we consider the model of probabilistic strings --- sequences of discrete probability distributions over a finite set of events, and initiate the study of space complexity of streaming computation for different classes of queries over such probabilistic strings. We first consider the problem of computing the probability that a word, sampled from the distribution defined by the probabilistic string read so far, is accepted by a given deterministic finite automaton. We show that this regular pattern matching problem can be solved using space that is only poly-logarithmic in the string length (and polynomial in the size of the DFA) if we are allowed a multiplicative approximation error. Then we show how to generalize this result to quantitative queries specified by additive cost register automata --- these are automata that map strings to numerical values using finite control and registers that get updated using linear transformations. Finally, we consider the case when updates in such an automaton involve tests, and in particular, when there is a counter variable that can be either incremented or decremented but decrements only apply when the counter value is non-zero. In this case, the desired answer depends on the probability distribution over the set of possible counter values that can range from 0 to n for a string of length n. Under a mild assumption, namely probabilities of the individual events are bounded away from 0 and 1, we show that there is an algorithm that can compute all n entries of this probability distribution vector to within additive 1/poly(n) error using space that is only Õ(n). In establishing these results, we introduce several new technical ideas that may prove useful for designing space-efficient algorithms for other query models over probabilistic strings.more » « less
-
In online or large in-person course sections, instructors often adopt an online homework tool to alleviate the burden of grading. While these systems can quickly tell students whether they got a problem correct for a multiple-choice or numeric answer, they are unable to provide feedback on students’ free body diagrams. As the process of sketching a free body diagram correctly is a foundational skill to solving engineering problems, the loss of feedback to the students in this area is a detriment to students. To address the need for rapid feedback on students’ free body diagram sketching, the research team developed an online, sketch-recognition system called Mechanix. This system allows students to sketch free body diagrams, including for trusses, and receive instant feedback on their sketches. The sketching feedback is ungraded. After the students have a correct sketch, they are then able to enter in the numeric answers for the problem and submit those for a grade. Thereby, the platform offers the grading convenience of other online homework systems but also helps the students develop their free body diagram sketching skills. To assess the efficacy of this experimental system, standard concept inventories were administered pre- and post-semester for both experimental and control groups. The unfamiliarity or difficulty of some advanced problems in the Statics Concept Inventory, however, appeared to discourage students, and many would stop putting in any effort after a few problems that were especially challenging to solve. This effect was especially pronounced with the Construction majors versus the Mechanical Engineering majors in the test group. To address this tendency and therefore collect more complete pre- and post-semester concept inventory data, the research group worked on reordering the Statics Concept Inventory questions from more familiar to more challenging, based upon the past performance of the initial students taking the survey. This paper describes the process and results of the effort to reorder this instrument in order to increase Construction student participation and, therefore, the researchers’ ability to measure the impact of the Mechanix system.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1145/3408877.3439585
