- Read chapters one through three in Formal Languages and Automata by Peter Linz. These chapters teach the fundamental concepts and terminology needed to understand automata, formal languages, and grammars, including how to convert between different types of finite acceptors and regular grammars.
- Read chapters one through three in the JFLAP book by Rodger and Finley. These chapters cover the same structures as the chapters in the Linz book, focusing on how to create and manipulate the structures in the JFLAP program. I followed the instructions in the book and learned about the basic functionality of JFLAP for finite automata and regular grammars.
- Went through HTML tutorial on www.w3schools.com
Integrating JFLAP into OpenDSA paper by James Cho
Improving the Capabilities of JFLAP: Creating Effective User Interfaces in Learning for Theoretical Computer Science paper by Ian McMahon
This paper describes the current JFLAP program (version 7.0) and its shortcomings, and the changes that have been implemented with the newest version, 8.0 (beta). As JFLAP was originally developed more than a decade ago, version 8.0 represents efforts to majorly rehaul the underlying code to follow current coding practices and increase JFLAP's flexibility and extend its capabilities. Some of the changes/additions include:
- code rewritten to take advantage of class-based hierarchies
- formal definitions displayed for all structures (for educational purposes)
- change from string-based inputs to 'symbol'-based inputs, for greater flexibility and more complex languages
- more features in the GUI, allowing for greater customization and control
- new functionality: CYK parsing algorithm, increased transparency for brute force parsing and language generation, block Turing Machines and TM conversions
- full backwards compatibility, except with block TMs
JFLAP 8.0 was field-tested with near universal positive feedback, especially concerning the readability and flexibility changes to the GUI.
Rakesh M. Verma. 2005. A visual and interactive automata theory course emphasizing breadth of automata. SIGCSE Bull. 37, 3 (June 2005), 325-329. DOI=10.1145/1151954.1067535 http://doi.acm.org/10.1145/1151954.1067535
A description of the Theory of Computation course at the University of Houston and an attempt to enhance learning by integration of AV and by providing examples of current applications of automata theory. The author of this paper explains that the classes such as the Theory of Computation course teach important fundamental concepts in Computer Science, but students often do not learn the material well, due to the abstract and complex concepts involved and the sentiment that the concepts learned are not practically applicable and so are of little to no consequence. To create a more intellectually stimulating curriculum, the course was changed to incorporate a modified version of JFLAP for visualization and a new focus on teaching practical applications of automata: lecture presentations and assignments include recent applications and tree/DAG automata while taking advatage of JFLAP animations for visualization and conceptual understanding. Student response to the course changes were been positive, with increased student motivation into the field and positive feedback in end-of-course evaluations.
Pradip Peter Dey, Mohammad Amin, Gordon W. Romney, Bhaskar Raj Sinha, Ronald F. Gonzales, Alireza Farahani, and Hassan Badkoobehi. 2012. Relating automata to other fields. J. Comput. Sci. Coll. 27, 4 (April 2012), 168-173.
This paper explains that, in typical automata theory courses, the curriculum tends to focus on the concepts, and students spend the entire course busy studying proofs and theorems; it suggests an alternative way of teaching the material, with a focus on connecting automata theory with other fields of computer science. The paper provides an example of one such connection - the relation between pushdown automata and processing programming languages, with the example of reading patterns of brackets. AV tools and dynamic visualization are shown to be helpful for students when explaining this relation and how the material learned in the class could be relevant to other, more obviously practical fields. A new "Automata and Related Topics" course is suggested, which would incorporate active engagement tools and assignments along with such visualization aids, in order to teach how other courses relate to the field of automata theory.
Susan H. Rodger, Eric Wiebe, Kyung Min Lee, Chris Morgan, Kareem Omar, and Jonathan Su. 2009. Increasing engagement in automata theory with JFLAP. SIGCSE Bull. 41, 1 (March 2009), 403-407. DOI=10.1145/1539024.1509011 http://doi.acm.org/10.1145/1539024.1509011
This paper details the results of a two-year study (Fall 2005 - Spring 2007) on teaching automata theory and formal languages using JFLAP. A total of fourteen universities were studied, and data on usage and opinions of JFLAP were gathered through workshops and student surveys. The faculty in the study mostly used the tool for homework, allowing students to create automata and compare results using JFLAP. Some incorporated the program into lectures and presentations. JFLAP was not used for exams, understandably due to concerns on technology use for inclass exams. The results found that students responded positively to the use of JFLAP. Most of the students surveyed felt that JFLAP made understanding concepts easier and made the course more engaging and interesting. Furthermore, this paper describes some of the changes made to JFLAP in response to feedback collected during the study: new algorithms, such as a CYK parser, and new web resources, such as an online tutorial.
Nelishia Pillay. 2010. Learning difficulties experienced by students in a course on formal languages and automata theory. SIGCSE Bull. 41, 4 (January 2010), 48-52. DOI=10.1145/1709424.1709444 http://doi.acm.org/10.1145/1709424.1709444
This paper details research into what specific difficulties students have in learning formal languages and automata theory (FLAT). A single course with thirteen enrolled students was studied. The results from exams and weekly tutorial exercises were analyzed, to identify the difficulties in learning a range of FLAT topics: regular languages, transducers, context-free languages, and recursively-enumerable languages. JFLAP was made available as a visualization aid for exercises but was not used for lecture presentations. The study found that, for the most part, most learning difficulties came from a lack of problem solving skills - students made mistakes contructing and converting the various structures. This could be solved with more practice exercises, especially with step-by-step feedback. There are currently no AV tools or programs robust enough to help develop such skills, and more research must be done before such systems could be developed and implemented. Conceptualizing the algorithms and structures was not as large of a difficulty, possibly due to the use of JFLAP. Those students who did struggle with conceptualization might not have used the tool, as it was optional and not integrated into lectures.
Barry Fagin and Dino Schweitzer. 2012. MyTuringTable: a teaching tool to accompany Turing's original paper on computability. In Proceedings of the 17th ACM annual conference on Innovation and technology in computer science education (ITiCSE '12). ACM, New York, NY, USA, 333-338. DOI=10.1145/2325296.2325373 http://doi.acm.org/10.1145/2325296.2325373
This paper describes the development of MyTuringTable, an AV tool designed to simulate Turing Machines as specified in Turing's original paper on computability, and its use in the US Air Force Academy's "Great Minds in Computer Science" course. The Turing Machines in MyTuringTable are visualized as tables, with terminology and features lifted from Turing's paper. In the context of the course, students were expected to read Turing's paper and implement their own Turing Machines in MyTuringTable within the course of a week and a half. Results showed that students performed very well, and MyTuringTable was an effective tool in visualizing and realizing the concepts of the paper.
Jaime Urquiza-Fuentes and J. Ángel Velázquez-Iturbide. 2012. Comparing the effectiveness of different educational uses of program animations. In Proceedings of the 17th ACM annual conference on Innovation and technology in computer science education (ITiCSE '12). ACM, New York, NY, USA, 174-179. DOI=10.1145/2325296.2325340 http://doi.acm.org/10.1145/2325296.2325340
This paper describes a study into the effectiveness of visualization tools in education. Two approaches were tested using the WinHIPE visualization tool: an active approach where students were encouraged to create their own visualizations, and a passive approach where students viewed already created animations. These approaches were compared to the traditional method, which does not use the tool at all, and the study was conducted on the second half of a foundations of programming languages course, with a focus on functional programming. The students were split into three groups: one solved problems with the option of using WinHIPE without visualization and with teacher help, one focused on watching teacher-created animations, with little to no interaction, and the last was tasked with creating appropriate animations for given programs. The results of the study showed that, while visualization tools do seem to aid learning, the effectiveness does not necessarily increase with the level of active engagement with the tool. For simple concepts, there was no significant difference in the three methodologies. For mid-level concepts, both viewing and constructing animations showed increased understanding of the material. For difficult and complex concepts, viewing aided learning, but constructing did not. Furthermore, it was found that intructor interactions with the students and explicit explanations of the material could be an important factor in the learning of the concepts. The paper suggests incorporating a mix of the three methodologies and changing the levels of each at different levels of conceptual difficulty.
Clifford A. Shaffer, Matthew L. Cooper, Alexander Joel D. Alon, Monika Akbar, Michael Stewart, Sean Ponce, and Stephen H. Edwards. 2010. Algorithm Visualization: The State of the Field. Trans. Comput. Educ. 10, 3, Article 9 (August 2010), 22 pages. DOI=10.1145/1821996.1821997 http://doi.acm.org/10.1145/1821996.1821997
This paper is a comprehensive description of the state of Algorithm Visualization as a field and the work surrounding the AlgoViz wiki project. The authors describe the history of AV, the effectiveness of its application, and the features of the wiki. The wiki represents an effort to catalogue all of the AV tools available on the Internet, with a focus on accessibility for instructors; there are labels denoting how tools should be used, and whether a particular tool is recommended for use. The wiki has links to more than 500 AV tools, though some may be individual parts of a larger package/program. Unfortunately, the various tools available represent a skewed distribution of computer science topics; for example, a large percentage of AV tools are simple visualization of sorting algorithms, while more complex, important topics such as complexity theory have little to no representation. Furthermore, the vast majority of the programs are written in Java, and in turn may be inaccessible on certain platforms. Since the wiki catalogues AV tools by linking to them, as time goes on, some are lost. However, this is only a small percentage of the repository, and the paper states that AV development is continuing at similar rates as in the past. Suggestions for the future include instituting better organization and cooperation among the AV community, with upgrades to AV repositories to make finding and using AV tools as easy as possible for instructors (for example, with the implementation of user reviews and dedicated catalogues of visualization courseware).
- CITI “History and Ethical Principles” module
- practiced jQuery: http://www.codecademy.com/en/tracks/jquery
- studied JSAV API
- test (test DFA using JSAV graph)
the test has the same functions as James Cho's, but the DFA is created as a JSAV directed graph
- can add states with a button press (the graph automatically redoes its layout afterwards)
- can edit states by clicking on them
- can add nodes with mouseclick
- can add edges with mouseclicks
Adding and editing nodes require changing the editing mode of the graph with the toggle edit button
- final states marked with double circle
- initial states likely unable to have an arrow attached without changing JSAV library
- adding nodes can only be done inside the graph window now
- can remove and move previously created nodes
- can put multiple weights on one edge
- pairs of edges now display as arcs
- changed JSAV.js: Graph, graphproto.addEdge, graph.removeEdge, Edge, edgeproto.layout
- currently cant remove individual edges
The current implementation is mostly done through HTML classes and some (bad) changes to the JSAV edge code, but it seems that the DFA can be represented fairly well as a JSAV graph. From here I should create a proper JSAV extension for automata to flesh out the functionality that is difficult/impossible with my current implementation (for example, marking the initial state with an arrow). The existing layout algorithm is also not one designed for FA's.
- loops added, but currently are fixed to the top of a state; should probably be able to change position depending on the state's other edges.
- took all of my previous changes and moved them into a new JSAV finite automaton extension.
- FA traversal should be added to the structure itself/to the extension
- confirmations now show as jsav messages instead of popping up (now less annoying)
Eric Fouh, Ville Karavirta, Daniel A. Breakiron, Sally Hamouda, Simin Hall, Thomas L. Naps, Clifford A. Shaffer, Design and architecture of an interactive eTextbook – The OpenDSA system, Science of Computer Programming, Volume 88, 1 August 2014, Pages 22-40, ISSN 0167-6423, http://dx.doi.org/10.1016/j.scico.2013.11.040.
This paper details the architecture and design philosophy behind the OpenDSA eTextbook project. OpenDSA was designed to be a highly accessible and customizable way to present educational DSA material. Its integration of algorithm visualization, high-engagement exercises, and easy and immediate self-assessment of student activities make it a better educational resource than a standard paper textbook. In addition, the various components of OpenDSA are highly modular - instructors can use already-constructed eTextbooks, create their own out of the available modules/chapters, or incorporate individual modules or exercises into their own course materials. While OpenDSA uses the JSAV library for its AVs, the library has been designed to be independent, so instructors can use JSAV to build their own visualizations without using any of the eTextbook resources. The focus on accessibility and being opensourced means that all content is open and usable without even needing a log-in account and implemented in HTML5 to be compatible with as many platforms as possible. A client-server architecture taking advantage of HTML5's localstorage feature allows exercises to be scored and provide immediate feedback, and the ability for instructors to gather data on how students perform. Therefore OpenDSA also easily supports pedagogical study. As DSA courses cover a broad range of material, OpenDSA encourages outside developers to add to its content, and work is always being done to incorporate existing AV material and improve the usability of its systems.
- can save and load graphs in the same way as graphEditor (using a modified serializableGraph.js and JSON)
Eric Fouh, Daniel A. Breakiron, Sally Hamouda, Mohammed F. Farghally, Clifford A. Shaffer, Exploring students learning behavior with an interactive etextbook in computer science courses, Computers in Human Behavior, Volume 41, December 2014, Pages 478-485, ISSN 0747-5632, http://dx.doi.org/10.1016/j.chb.2014.09.061.
- This paper describes a study into how the OpenDSA eTextbook is used by students, by analyzing the data gathered by the OpenDSA system. The study was conducted on data from several data structure and algorithms courses at Virginia Tech and Egypt's Alexandria University. Results showed that most students skipped to the OpenDSA proficiency exercises without reading the text, and most waited until the last day to do the homework assigned through the eTextbook; exercise activity spiked on homework due dates and before exams (as students would redo exercises to study). When students were given credit for completeing slideshows, more students viewed slideshows, and more students skipped directly to the end of slideshows without going through slides one by one. Better performance on the profiency exercises was associated with better performance on exams. Despite the fact that OpenDSA is written in HTML5, allowing for use in a wide variety of platforms, less that 1.5% of traffic was from mobile devices. It is possible that this number was so low due to the inconvenience of using a mobile device as a study tool when studying last minute after having procrastinated.
- can edit and remove edges, but this requires clicking directly on the edge, which is a pixel thick by default (can be changed with css). This is done in the 'editing nodes and edges' mode, changed from just 'editing nodes'.
As an aside: cycling through editing modes is annoying.
- displays FA's alphabet
- can label states similarly to JFLAP (labels will appear on mouse hover, can't make them permanently display). This is done through 'editing nodes and edges' mode.
- added NFA to DFA conversion, using underscore.js for set operations. The DFA is generated as a new graph below the current one, and cannot be edited or interacted with in any way.
- the default graph is now an NFA, the same as the one in Figure 2.1 from the JFLAP book
- should turn the conversion into an OpenDSA exercise.
- changed initial state marking from green fill to bold and italicized font. Is now much harder to tell if a node is initial, but it will now be properly highlighted during traversal.
- the way FAs are currently implemented, the values of nodes are not allowed to be changed. If they are changed manually, it will interfere with conversion and minimization. In fact, the graph will reinstate its own values when a node is removed. Either this or the way the converted FA is displayed must be changed if we want the converted FA to be editable.
- need to add custom labels and attaching details to nodes (would fix above problem).
- added option to change what the empty string character is. Can be anything, but by default is λ.
- changed editing interface to multiple buttons
- added giving states labels - done through 'editing nodes and edges' mode, replaces what used to add mouseover text
- converting to DFA now uses the new labels (should be OK for editing now) and is displayed as a slideshow
Conversion exercise test
- making a NFA to DFA exercise similar to JFLAP
- expand on terminals and place states to complete the DFA. The "model answer" button shows what the DFA should look like. If you have finished constructing the DFA, the "model answer" button also tells you if you have correctly done so.
- exercise lacks any editing options
- exercise reset button doesn't work due to a bug
- bug: slideshow controls can work during editing mode (pressing back will take you to the original graph before any edits)
- slideshow controls now only display during traversal
- should change so that mode cannot be changed mid-edit
- editing changed: click the 'edit' button to access the different editing options, click 'done editing' to return to original buttons.
- added 'highlight nondeterminism' and 'highlight lambda transitions' buttons, which toggle the respective highlighting. Editing is disabled while highlights are on.
Conversion exercise test
- can move and remove states
- when asked for the group of NFA states, input can be entered with or without 'q's and separated by commas or whitespace
- the graphs are now side-by-side, fixing the problem where the NFA was usually not visible when the user was prompted for an input.
IFrame test - the above tests modified and placed as iframes into a single page.
- saving a graph in the DFA test will allow you to load the saved graph as the NFA in the Conversion exercise test - reload buttons will reset individual iframes (saved graph is kept saved until the entire page is reloaded)
Conversion exercise test old
- reset button fixed, undo button still doesn't work
- jsav exercise messes up graph layouts: model answer graph is bugged
- started implementing minimization like JFLAP's
- the tree has problems displaying properly (also is a binary tree - change later)
- 'done' button creates a dfa using the leaves of the tree (automatically adds nodes and edges, should change so that edges must be added manually)
- doesn't split nodes yet
Ville Karavirta and Ari Korhonen. 2006. Automatic tutoring question generation during algorithm simulation. In Proceedings of the 6th Baltic Sea conference on Computing education research: Koli Calling 2006 (Baltic Sea '06). ACM, New York, NY, USA, 95-100. DOI=10.1145/1315803.1315820 http://doi.acm.org/10.1145/1315803.1315820
- This paper decribes an implementation of a AV tool that supports interactive questions in a way different from existing algorithm simulation tools. The questions are designed to tutor and guide students through simulating the data structure or algorithm in the exercise and increase the student's knowledge of the topic at hand. To this end, questions are generated dynamically, in response to the state of the visualization, if the student has an error in his/her construction. These questions are non-blocking and voluntary, acting more as hints. The questions can either be answered explicitly by the student, or implicitly, when the student fixes the error in the simulation. The tool was created as an extension to the TRAKLA2 AV system using the AVIntegration package. The authors of the paper conclude by noting that their tool incorporates various levels of the 'engagement hierarchy', and that research into the efficacy of engagement levels can be easily complicated due to how certain activities often blend together different engagement levels without clear boundaries between them.
Minimization test old
- splits nodes (partition is done automatically)
- initial state marked by arrow. Arrow's position updates with state labels.
- 'done' button now only places the nodes automatically; edges must be placed manually
- 'hint' button and 'complete' button added, which add edges to the DFA automatically
- tree positioning fixed
- partitioning now requires user input: add states by clicking on them in the DFA (remove states the same way). Until the selected node has been correctly partitioned, no other node can be split.
- the states in the node are highlighted in the DFA
- 'done' button checks to see if you are actually done
- add children manually, remove children, check if partitions are correct
- minimized DFA now replaces the tree when the tree has been finished
- split nodes with buttons
- auto partition button
- original DFA has a fixed layout and larger edges
- 'done?' button added to DFA - tells you how many transitions remain to be placed
- edge labels are now rotated to go along the edge
- deterministic pushdown automata: can traverse
- using semicolon as a separator is a problem, due to λ (should at some point implement symbols over strings)
- labels now stack and are placed above edge instead of directly on it
Label test /PDA
- in 'editing nodes and edges' mode, edges are made thicker to be easier to click
- can edit labels directly by clicking on them: opens a menu that allows selecting individual transitions
- can delete individual transitions by clicking the label, or delete the entire edge by clicking the edge
- cannot add transitions through the label menu, and editing transitions requires inputting the entire string
- lambda is still entered with the empty string (e.g. '::' would make the transition 'λ:λ:λ')
- label menu properly bound to new edges
- label menu position adjusts to stay inside the graph window
- the λ character causes some problems due to how it is represented: retrieving the text of an HTML element gives the character itself, while retrieving the HTML/innerHTML of the element gives the character code.
- all these changes are a workaround - edges can still only have a single label, with a single value string. The values are separated with line break codes, and this must be parsed to retrieve individual values for the label menu.
- editing labels is done during 'editing nodes and edges' mode. Clicking an edge now only lets you delete it. Alternatively, delete an edge by deleting each of the transitions on it.
- adding transitions on existing edges now places the new transition on the bottom of the stack
- the new edge labels work properly with arcs now
- edge label browser compatibility: works with the newest versions of chrome, opera, firefox, IE
- unfortunately, it seems that edges do not display properly in IE (checked with IE 11). However, the OpenDSA graph exercises have the same problem (but not trees) - I think that JSAV graph edges in general may have compatibility issues with IE.
Label test /PDA old
- highlight nondeterminism and highlight λ transitions work for PDAs
- traverse works for deterministic PDAs
Ville Karavirta. 2009. Seamless Merging of Hypertext and Algorithm Animation. Trans. Comput. Educ. 9, 2, Article 10 (June 2009), 18 pages. DOI=10.1145/1538234.1538237 http://doi.acm.org/10.1145/1538234.1538237
Thomas Naps, Guido Rößling, Peter Brusilovsky, John English, Duane Jarc, Ville Karavirta, Charles Leska, Myles McNally, Andrés Moreno, Rockford J. Ross, and Jaime Urquiza-Fuentes. 2005. Development of XML-based tools to support user interaction with algorithm visualization. SIGCSE Bull. 37, 4 (December 2005), 123-138. DOI=10.1145/1113847.1113891 http://doi.acm.org/10.1145/1113847.1113891
- This paper presents an XML specification of algorithm animations that would allow the creation of flexible visualizations viewable on a number of different platforms. The specification presumes a visualization paradigm where 'interesting events' are done on objects and different parts of a pipeline fill in the details. An 'elaborator' links the interesting event with the object, a 'synchronizer' then adds pedagogical components, from questions for the students to usage metadata, and a 'graphics decorator' adds graphical and layout information. This 'complete visual specification' represents the full algorithm visualization, and this is parsed by an 'adaptor' to be displayed by the end-user's system. The paper has a number of examples of XML specifications for various components of an animation: objects, graphical primitives, transformations, narration, questions, and metadata. Some questions were raised on the level of detail necessary for specification, and the particulars of how the visualization paradigm would function. The hope is that the framework laid out in this paper would serve as a good jumping-off point for future work on general AV systems and research.
- stack alphabet
- nondeterministic traversal: shows configurations in the message box
- default automaton is the same as the one in section 5.2 of the JFLAP book
- fixed some bugs with the initial state arrow
- preliminary tracing
- moved code around
- one-tape Turing machine
- during traversal there's a 'viewport' of the tape, with the current character highlighted
- default animation speed set to max (no animations)
- you can't cancel adding edges
- multiple traversals: separate inputs with commas
- running multiple inputs will show whether each input was rejected or accepted. If accepted, displays the output. Clicking on an array index will provide the trace.
- nondeterministic traversal
- displays output after traversal
MultiTape TM test
- multiple tape TM: select number of tapes before traversal
- configurations shown in jsav message box
MultiTape TM test old
- asks for number of tapes at very start (default is 2)
- multiple traversal works
- editing transitions changed, now has separate input boxes for each symbol (adding edges is similar)
- can no longer delete transitions during editing nodes/edges mode
- separate mode for deleting nodes/edges
- fixed a bug where changing edge labels wouldn't actually change the edge weights
MultiTape TM test old
- since I catch bugs in the latest prototypes I'm working on, the previous prototypes on this blog are still buggy
Purvi Saraiya, Clifford A. Shaffer, D. Scott McCrickard, and Chris North. 2004. Effective features of algorithm visualizations. In Proceedings of the 35th SIGCSE technical symposium on Computer science education (SIGCSE '04). ACM, New York, NY, USA, 382-386. DOI=10.1145/971300.971432 http://doi.acm.org/10.1145/971300.971432
- This paper describes research done on how effective certain features of an algorithm visualization really are for learning. The authors ran two experiments with a heapsort visualization tool, where groups of students worked with different versions of the tool which contained various optional features turned on and off. Features tested for were: the ability by users to enter their own data sets, example test data, a display highlighting a psudocode representation of the algorithm, the ability to step backwards in the simulation, and a series of tutoring questions meant to help guide users through the concepts of the algorithm. The results of the experiments showed that giving the user the ability to manually step through the algorithm, and providing example test data sets were the most important features out of the ones tested for learning efficacy. Meanwhile, the guide questions and pseudocode display, while increasing the time spent on the simulation, did not seem to significantly increase pedagogical value. The results concerning the guide questions came as a surprise, as previous research had indicated that learning increases with engagement; the questions had been designed to force the user to understand and engage with the algorithm.
Jaime Urquiza-Fuentes, Francisco Manso, Jesús Ángel Velázquez-Iturbide, and Manuel Rubio-Sánchez. 2011. Improving compilers education through symbol tables animations. In Proceedings of the 16th annual joint conference on Innovation and technology in computer science education (ITiCSE '11). ACM, New York, NY, USA, 203-207. DOI=10.1145/1999747.1999805 http://doi.acm.org/10.1145/1999747.1999805
- This paper describes a study done on the effectiveness of a symbol table animation/visualization tool (SOTA - SymbOl Table Animation) in learning compilers and language processing. The tool takes code and provides a tree structure to visualize state and scope. The graphical representation is also used to show how search operations go through scopes. Two experiments were performed using this tool. In the first, two groups of students, one taught traditionally and one taught using the tool, were tested before and after a learning period (including lectures, labs, and practice exercises). They were tested on their ability to produce a symbol table structure for given source code. The results showed that there was not a significant difference in performance between the two groups, but there was a significant difference in efficiency: the group that had been taught with the visualization tool completed the test questions in significantly less time. The second experiment was similar to the first, but the tests included questions on building parser specifications and providing the source code that would result in a given symbol table. As in the first experiment, there was no significant difference in performance between the two groups with regard to the first type of question. However, the group taught with the tool outperformed the group taught with traditional methods by 22% for the parser specification questions. The authors note that building parser specifications is a core component of compiler courses, illustrating SOTA's pedagogical value.
DFA test (on local)
- separated HTML files
- added reset button through OpenDSA (buggy)
- reset returns the graph to before traversal (uses the old serializablegraph.js, so probably buggy)
- started grammars
Jaime Urquiza-Fuentes and J. Ángel Velázquez-Iturbide. 2009. A Survey of Successful Evaluations of Program Visualization and Algorithm Animation Systems. Trans. Comput. Educ. 9, 2, Article 9 (June 2009), 21 pages. DOI=10.1145/1538234.1538236 http://doi.acm.org/10.1145/1538234.1538236
- This paper describes a survey conducted over evaluations on the effectiveness of program/algorithm visualization tools. The evaluations were split into those testing usability and those testing educational impact, with both script-based and compiler-based systems. Of the tools evaluated, about half were subject solely to usability evaluations. Furthermore, a large fraction of usability evaluations were informal (consisting of simple student feedback), and many of the system developers did not fully utilize the usability tests in the development cycle. Educational evaluations were surveyed with the engagement level taxonomy in mind: script-based systems were found to be more suited for lower levels of engagement (viewing or responding) - the high degree of complexity (often with a steep learning curve) in these tools results in lowered educational value in the construction of animations, despite their flexibility and expressiveness. Compiler-based systems, on the other hand, are better suited for the higher engagement levels due to how they free the user from the intricate details of dealing with the script directly. Of course, the two systems are not mutually exclusive, and there are script-based systems with, for example, some graphical functionality to incorporate the benefits of a compiler-based system, and vice versa. Furthermore, as the tools continue to be developed, more features are likely to be added to increase both usability and pedagogical value. Since this paper focused on successful experiments, the authors remark that future work remains to be done to study visualization tools and evaluations not covered in this survey.
Right-linear grammar test
- right-linear grammar
- edit productions by clicking on rows in the table
- delete lines in deleting mode
- brute force parsing: enter an input string and it will tell you whether the string was accepted or rejected
- derivation table shown with the brute parser
- noninverted tree shown with the brute parser
- productions highlighted in the table during brute parser
- can step through derivation table/tree
- can parse repeatedly, with different inputs (cannot do multiple inputs at once, however)
- table doesn't scale with contents
- fixed some bugs with infinite loops
- though I call it a right-linear grammar test, it should have no problems with context-free grammars
Right-linear grammar test old
- back button added: takes you out of the parser
- tree now properly created for context-free grammars
- lots of debugging
- CFG tree is correct but ordering does not match the table
- convert right-linear grammmar to FA option (opens in new window)
- the FA is completed automatically; cannot edit the FA
- traversal doesn't work
- string transitions should be added to previous tests
- convert context-free grammar to NPDA option (opens in new window)
- traversal doesn't work
- need to look at exttest.js and npdaTest.js (their traversal functions are incomplete)
- should implement pruning during parsing
- now prunes sentential forms with more terminals than the input
Right-linear grammar test old
- traversal for the converted FA works (can take multiple input transitions)
- traversal shows configurations instead of the array from before
- traversal for converted NPDA works (fixed the issue with the original NPDA test where lambda inputs were not being read correctly)
- at this point my original DFA/NFA test is outdated and buggy
- the NPDA traversal can fail due to running out of memory for the stack
- lots of debugging
- added convert FA to right-linear grammar (done automatically for now)
- the FA editor for the above tests are based on an old version and so lacks some of the features present in the PDA or TM tests
- fixed a bug where the alphabet would not be updated after an edge label was changed
NPDA to CFG
- added convert NPDA to context-free grammar (done automatically for now)
- attempts to export to the grammar test
- if it can't export, it opens the table in a new window
Petri Ihantola, Ville Karavirta, Ari Korhonen, and Jussi Nikander. 2005. Taxonomy of effortless creation of algorithm visualizations. In Proceedings of the first international workshop on Computing education research (ICER '05). ACM, New York, NY, USA, 123-133. DOI=10.1145/1089786.1089798 http://doi.acm.org/10.1145/1089786.1089798
- This paper describes a proposed taxonomy to categorize software visualization systems based on 'effortlessness', as one of the major reasons for instructors' hesitance to incorporate SV tools into their courses is the effort required to build and utilize visualizations. The taxonomy is based on three main points: scope, integrability, and interaction. Effortless SV systems should strive to have broad and deep scope, so that the system is not just limited to a single example problem or even a single field of study. They should be able to be easily integrated for a third party's use, with efforts towards platform independence, ease of installation, and internationalization, among other factors. The system should also have a high degree of interaction between the producer, system, and consumer. The pedagogical value of user interaction is covered in previous studies. The authors apply the taxonomy to four example systems (Animal, JAWAA, Jeliot 3, and MatrixPro). The authors conclude by noting that one of the factors, integrability, is independent of the others, and systems can and should incorporate as many features as possible to increase ease of integration. The other two factors are linked, and the authors would like to see systems become more and more equipped for generic use and on-the-fly customization.
- added removing λ-productions (done automatically for now)
- added removing unit productions (done automatically for now)
- added removing useless productions (done automatically for now)
- each transformation opens the resulting grammar in a new tab
- after the grammar test loads a grammar from local storage, it clears local storage so that other tests do not load the same grammar. This means refreshing the page after having transformed a grammar will load the default grammar.
- bug with the parse tree when there are multiple of the same variable
- when trying to convert a RLG to FA, it should check to see if the grammar is right-linear
- added converting to Chomsky Normal Form
- similar to the NPDA to CFG conversion, exporting the CNF can fail, at which point the table is opened in a new window
- brute force parser now includes variables which derive terminals when pruning based on length
- the brute force parser needs work
- when trying to convert a RLG to FA, it checks to see if the grammar is right-linear
- brute force parser now prunes sentential forms that have terminals which the input string does not have
- brute force parser now prunes sentential forms that have an incorrect sequence of starting terminals
- brute force parser now prunes sentential forms that have an incorrect sequence of ending terminals
- terminal nodes in the parse tree are now colored light green and become colored immediately upon appearing
- fixed a bug where transforming a grammar would change the original grammar as well as creating the transformed grammar in a new window
- parser asks if the user would like to continue if parsing is taking a while
- added LL(1) parsing
- generates FIRST and FOLLOW sets automatically
- creates parse table automatically
- creates parse tree during parsing slideshow
- input remaining and the current stack is displayed as a message
- during parsing, the relevant entry in the parse table and the upcoming symbols to be checked in the input and stack are highlighted
- no derivation table option yet
- should check if grammar is LL
- the default location for new nodes that are added to a graph is the top left corner. This means that initial state arrows (which are to the left of the states) are not visible.
- added SLR(1) parsing
- constructs DFA automatically
- creates parse table automatically
- creates parse tree during slideshow
- displaying a JSAV tree bottom-up is limited, so instead the parse tree is created as a directed graph with a layered layout
- fixed a bug in FIRST for SLR parsing
- missing showing stack and remaining input
- LL parser exits if it finds a conflict in the parse table
- LL(1) parsing now interactable: asks user to fill in FIRST and FOLLOW sets
- filling in the table uses a different interface than editing the grammar (should update how the grammar is edited)
- if there are incorrectly filled sets, the user is told which variables are incorrect
- asks user to fill in parse table
- incorrect cells are highlighted
- option to fill the tables in automatically
- SLR(1) parsing partly interactable
- asks user to build the DFA, with the option to create it automatically
- cannot actually built the DFA yet
- interactable DFA building for SLR(1) parsing
- can move nodes and make nodes final
- asks the user to fill in the item sets through a separate window and create nodes
- there seems to be problems with reading state labels when nodes are hidden (node.stateLabel() doesn't work, but node._stateLabel.element.innerHTML does)
- closing the goto window other than through the 'OK' button causes problems
- SLR parsing shows the remaining input and the stack
- SLR parsing highlights parse table cells
- fixed various bugs with highlighting and editing
- should add an option to automatically complete all steps at once
Grammar test old
- improved grammar editing (there are some bugs that should get fixed as the other proofs are made interactive)
- it would make more sense to have the table values be HTML input elements in the first place(would likely require creating a new jsav structure)
- made removing lambda productions interactive
- asks user to select variables to put in the lambda-deriving set
- asks user to modify the grammar to remove lambdas (and add the necessary productions)
- when the grammar is finished, asks the user whether to export the grammar or not; exporting opens the reformed grammar in a new tab
- should change adding productions to the reformed grammar to be easier
Alexander Repenning, David C. Webb, Kyu Han Koh, Hilarie Nickerson, Susan B. Miller, Catharine Brand, Ian Her Many Horses, Ashok Basawapatna, Fred Gluck, Ryan Grover, Kris Gutierrez, and Nadia Repenning. 2015. Scalable Game Design: A Strategy to Bring Systemic Computer Science Education to Schools through Game Design and Simulation Creation. Trans. Comput. Educ. 15, 2, Article 11 (April 2015), 31 pages. DOI=10.1145/2700517 http://doi.acm.org/10.1145/2700517
- This paper describes 'Scalable Game Design' (SGD), a way to introduce conputer science to schools through game design. It notes that, despite the ubiquity of computers and computational problems in today's society, the US education system is sorely lacking in the field of CS, with the consequence that there is a shortage of workers skilled enough in programming and computation in the country. While educators agree that CS is an important subject, there continues to be a lack of computer courses in the school curriculum, with a major reason being the sentiment that CS education is a zero-sum game: introducing a CS course would require cutting a different course from the curriculum. In addition, since currently, CS is mostly taught (if at all) as an elective course or as an afterschool program, the students learning are those who already had an interest in CS - girls and minority students do not even get the chance to be introduced to CS. To that end, SGD seeks to introduce Computational Thinking (CT), rather than programming, at a high, abstract level capable of being extended and applied to other fields (especially with regard to simulations in STEM courses) to middle school courses. To maximize student engagement, SGD opts for a 'project-first' paradigm, where students are immediately asked to create a project and learn the necessary concepts and tools along the way as they are needed, with a focus on 'guided discovery', where students are encouraged to experiment and discover the concepts on their own, with the teacher providing guiding questions and resources. The authors found that this strategy engaged students so much that students became enthusiastic of the material no matter their gender or background, and students asked to be taught complex concepts far outside a middle school level in order to implement desired features into their games. To allow for and quantify transferability of acquired skills, SGD makes use of computational thinking patterns (CTPs), based on phenomenological concepts, rather than the typical programming structures (like loops and if statements). These CTPs are directly applicable to the creation of science simulations, after the students have learned them during game design. The authors were able to create a system for the extracting and quantifying of CTPs from student-created programs, to track the transfer of skills and the learning process of the students. In this way, SGD was designed to be incorporated into already existing courses, not necessarily having to be a standalone CS course. It was found to be successful in broadening student participation, as well as motivating students and teachers alike in computer education (the teachers participating in the SGD workshops came from a variety of backgrounds and fields).
Grammar test old
- everything assumes the left hand side is a single variable
- made removing unit productions interactive
- asks user to complete the variable dependency graph (nodes added automatically)
- asks user to remove unit productions and add the necessary productions to the reformed grammar
- interactive grammar transformation skips steps that are unnecessary (e.g. if there are no lambda productions)
- made removing useless productions interactive
- asks user to select variables that derive terminals
- asks user to complete the VDG (nodes added automatically)
- asks user to remove unreachable productions
- VDGs use the layered dagre layout (for lack of a better one)
- started making converting to CNF interactive
- JFLAP's SLR parser seems to create DFA nodes in a different order than mine, resulting in slightly different parse tables
Grammar test old
- made converting to CNF interactive
- click on a production to convert it
- when all productions have been completed, asks if user wants to export the grammar
- exporting can fail if there are too many variables
- debugging interactive transformations
- there are problems with the display when the jsavcanvas has been scrolled and a new element is created
- fixed the scrolling problem, but now the layout of the elements is not very good
- window no longer goes back to the top after an edit
- should highlight productions as they are added to the lambda/terminal sets
- should make tables more flexible in size
Grammar test old
- productions are highlighted as they are selected while building the lambda/terminal sets
- adding the initial node in the SLR DFA is now done by clicking on the graph instead of clicking a button
- fixed a problem with removing lambda productions (not all of the necessary productions were being added)
- since I have been learning all of the proofs/algorithms as I go, it's possible some of them have been incorrectly implemented or have problems with edge cases
- can now load JFLAP grammar files
- can now save and download the grammar as an XML file (which can be opened in JFLAP)
Grammar test old
- should probably create a new JSAV structure for grammar tables, in order to improve the way user input works, how the table is laid out, and how table cells scale in size
- pressing the save button now immediately downloads the file
- placed example grammars into separate files
- bug fixes with parsing and the layout of elements during parsing
- layout during parsing needs work
- fixed bugs with having an empty grammar
- adding a new LHS automatically makes the RHS a lambda
- enforces single variable LHS
TM test, adder, Multitape test (TM tests)
- fixed a bug with removing duplicate configurations
- can save and download the FA as an XML file (which can be opened in JFLAP)
Grammar test old
- fixed a bug where lambdas could be placed in a RHS with other symbols
- enforces that productions be unique
- the DFA created from converting a RLG is slightly different from JFLAP's (the ordering of the nodes is different)
- made converting RLG to FA interactive
- first checks if grammar is right-linear, then automatically creates the FA states
- add transitions manually or by clicking on the productions in the grammar table
- when the FA has been completed, the user can export it (download as JSON file)
- the exported file can be opened in FA editor
- made converting CFG to NPDA interactive
- automatically creates nodes and adds transitions for terminals
- click productions in the grammar table to add them to the PDA
NFA to DFA conversion test
- minor bug fixes and commenting
DFA minimization test
- minor bug fixes and commenting
NPDA to CFG
- slrGoTo.js commented
- should make FA/PDA to grammar interactive
- CFG to PDA now scales the graph window appropriately when the size of the edge label gets too large
NPDA to CFG
- removed all features except converting to CFG (they are in npdaTest.js)
- can load JFLAP FA files
NFA to DFA conversion, DFA minimization
- should be able to load different inputs (can't really do any testing until this is done)
- grammar columns now scale their width properly
- FIRST/FOLLOW table and parse table columns also scale their widths properly
- 'transform grammar' will only work in Chrome and Firefox, due to lack of generator support in other browsers
- exporting converted FA now exports as XML
- exporting converted PDA does nothing
NPDA to CFG test
- click edges to add the corresponding productions to the grammar (added edges are colored red)
- edges are made large to be easier to click
- clicking edge labels does nothing
- when the grammar is finished, asks if the user wants to export (export can fail)
Dierk Johannes, Raimund Seidel, and Reinhard Wilhelm. 2005. Algorithm animation using shape analysis: visualising abstract executions. In Proceedings of the 2005 ACM symposium on Software visualization (SoftVis '05). ACM, New York, NY, USA, 17-26. DOI=10.1145/1056018.1056021 http://doi.acm.org/10.1145/1056018.1056021
- This paper describes a different way of providing algorithm visualization. Most AV tools provide an animated simulation of an instance of an algorithm, with a single data set (which may be given or inputted by the user). However, when instructors teach algorithms in a lecture setting, they often do so by providing a abstracted diagram highlighting the important, variable information. Moreover, truly understanding an algorithm requires understanding what is invariable and independent of the dataset. To this end, the authors of this paper suggest a way to show the abstract execution of an algorithm, using the TVLA (three-valued logic analyser) system for shape analysis of pointer-based algorithms to provide abstract shape graphs of an execution. Shape analysis for large or complex data sets can result in a large number of shape graphs, so the authors provide a way to separate shape graphs into different classes with distinct features. Leveraging the level of similarity between shape graphs also allows grouping by adjustable levels of detail, a educationally useful feature. The authors do not provide suggestions on how to actually display shape graphs - visualization and layout is in itself an important and complex problem.
Grammar test old
- writing guide/documentation
- can export converted PDA as XML file
NPDA to CFG test, NPDA test
- can save/load PDAs as XML files
- possible problem with importing PDAs that are too large
- todo: save/load TM
TM test, Multitape TM test
- can save/load TMs as XML files
- writing guide/documentation
- bug fixes with save/load
- guide mostly completed for all tests except the TM tests
- documentation of code still remains to be done
- writing guide/documentation
- guide mostly completed
- commented FA.js
- added numbering to SLR grammar productions
- finished documentation
- added information to PDA traversal and grammar transformations