tinyurl.com/AIA-projects

---

Algorithms in Action Projects

Here we describe possible projects for extending the Algorithms in Action algorithm animation system in semester 2, 2025, with the clients Lee Naish and Linda Stern. AIA was developed for the purposes of teaching computer science algorithms. It features textual explanations, animation and pseudocode, run in coordinated fashion. A key feature of AIA, not found in other algorithm animations, is that users can view an algorithm at varying levels of detail. Starting with a high level pseudocode description of the algorithm, with accompanying high level animation and textual explanations, students can expand sections of the pseudocode to expose more detail. Animation and explanations are controlled in coordinate fashion, becoming correspondingly more detailed as the pseudocode is expanded.

The current implementation is primarily written in JavaScript, using the popular Node.js/React framework. Most of the code been written by students over several years and more recently Lee Naish has done some coding also. It is open-source with the code in a github repository. The following projects aim to enhance and extend AIA. All are open-ended: depending on progress through the semester they may be extended. Students participating in these projects will be contributing to a good open-source teaching and learning tool while getting valuable software engineering experience. We have had excellent feedback from previous groups who have made contributions to AIA. As clients, we expect to have good communication with all groups. In developing algorithm animations we don't always have a precise idea of what will work best at the outset - it often works best for the team to develop a prototype that we can give feedback on, before proceeding on to further development. There are also some aspects we want control over, such as the details of the pseudocode, so some changes must only be done with our explicit consent. All the team projects will need to be merged into a single AIA version before the end of the semester, so the way things are coordinated in the AIA github repository throughout the semester is important.

Project 1: Global Issues (more details/updates)

This project addresses several desirable enhancements to AIA that affect multiple algorithms. Some are related to making future development of the code easier, for example, adding new algorithms modules. Others concern the function of AIA. As well as writing the code for these enhancements, they must be documented in the AIA Wiki for the benefit of other programmers (including other teams this semester).

Simplifying addition of new algorithms

This is the first task to tackle. The aim is to get at least a simple version of this working quickly and committed to the repository to help the teams that are adding new algorithms. Later it can be refined further if needed, preferably in a way that does not impact the other teams. There are two main components to this. This first is to rationalise the multiple lists of algorithms that appear in the code. The second is to complete some simple code that helps with some tedious aspects.

Lists of algorithms in the code

Once in AIA there was a single master list of algorithms that had all the required information. Sadly, some modifications to the system resulted in four separate lists, each with slightly different information etc, and each of which needs to be edited for each new algorithm. The single list design is what we want; the other lists should be generated from the master list.

Reducing tedium in adding new algorithms

To add a new algorithm, several new files must be created (eg, for the animation code, the pseudocode and extra information) and entries must be added to numerous lists. We have prototype JavaScript code that inputs the algorithm name and a unique identifier to be used in code and outputs unix commands to create files, append to files and instructions about what code to add to other files, allowing lots of copy and paste rather than tedious typing. This prototype should be completed.

Main page algorithm menus

The main AIA page has a list of algorithms, divided into categories, but depending on the window size and font size, some may not be visible. This must be fixed. Also, due to the way the formatting is done, adding new algorithms can be a nightmare. Finally, there is a search function that relies on algorithm names but ideally it should support keywords associated with each algorithm.

Colors

The way colors have been implemented in AIA has changed over time to improve flexibility (eg, color choice) and consistency (eg, between colors of array elements, graph/tree nodes and edges). Some primitives have been added for flexible coloring of arrays and similar primitives should be implemented for graphs. Retro-fitting the more flexible primitives to existing animation code and deleting some legacy code is also desirable.

A second issue is the choice of different color palettes supported in AIA. The intention is for AIA to be accessible to those with different color perception. Some of the more recent color choices should be re-visited with this in mind. Also, there are some uses of color in AIA that don't vary when different color palettes are selected; ideally this should not be the case.

Specialised URLs

AIA supports specialised URLS to allowing links to a particular algorithm with particular input. However, not all options etc can be specified with URLS, similarly for the step of the algorithm execution and expansion of pseudocode. It would be desirable to extend the URL mechanism to specify more information.

Project 2: Binary search tree variants (more details/updates)

Currently AIA has an animation of an iterative coding of binary search trees and a recursive coding of AVL trees (a form of self-balancing binary search tree). We would like to extend the coverage of BSTs in AIA.

Improving the AVL tree animation

The current AVL tree animation is good (it was devloped by a student team in 2024 and has been refined somewhat since) but could be improved further. Specifically, we think the way certain components of the tree are highlighted is worth revisiting and the way the animation helps users understand the recursion could be improved. It is likely some prototyping will be required in order to get the best outcomes.

Recursive BST animation

We would like a new animation BSTs that uses a recursive coding. The relationship with AVL trees should be emphasised - the AVL tree insertion algorithm is essentially recursive BST insertion code with a couple of steps added at the end. The look of the two animations (including the pseudocode) should be as similar as possible. Also, a good visualisation of recursion for a simple algorithm would be beneficial.

Iterative BST animation

The current iterative BST animation may also require some minor modifications to make it look as similar as possible to the other BST/AVL algorithms.

Project 3: Linked list merge sort (more details/updates)

Currently AIA has algorithm animations that visualise arrays, various forms of trees and graphs but none that visualise linked lists. This project will add linked list visualisation to AIA, initially using a version of merge sort. There should also be consideration of how the code could be used or adapted to other linked list algorithms (some of which may also be completed in this project).

Preferred visualisation of linked lists

Linked lists are best represented by either some symbol that represents the empty list or an arrow that points to a box that is divided into two parts (or two boxes that are joined), representing a list cell. The first part/box will contain a list element (the head of the list) and the second will contain the empty list symbol or an arrow pointing to the next list cell (the tail of the list). AIA has a module that implements graphs, including various forms of trees, and this has similar visual elements. Extending it to support lists seems like the best solution.

Visualisation in merge sort

Exactly how the algorithm is visualised will be determined in consultaion with the clients, who have some ideas but these may change as prototypes are developed. For example, a key operation in mergesort is merging two sorted lists L and R to form a new list M. The two input lists could each be displayed horizontally, one above the other. All arrows would point to the right. As the merge operation proceeds, the list cells could remain in the same positions but the arrows and labels such as L and R could change (helping illustrate that the algorithm changes pointers but not the data in list cells). Arrows may then point right, up, down or diagonally. At the end of the merge operation the resulting list M could be re-rendered horizontally for clarity, with all arrows pointing to the right again.

Existing merge sort animation for lists

AIA has a prototype of merge sort for lists implemented (it doesn't appear in the menus but can be found from the main page via the search function). Some steps of the execution are not animated and these need to be filled in. However, the main job is to change the way lists are visualised. In the prototype, lists are represented using two arrays: one for the data (the head of each list) and another for the "next pointers" (the tail of each list). Thus head[i] together with tail[i] represent the two components of a single list cell. Instead of a pointer to a list cell we use the index of the arrays that represents the next list cell (so the integer i represents a pointer to the list cell described above). Empty lists are represented by "Null". The pseudocode is written so it is independent of the way lists are represented and it should remain unchanged in this project. We just want the dual arrays replaced by arrows and boxes representing pointers and list cells, respectively.

Project 4: Convex Hull (more details/updates)

Currently AIA has no geometric algorithm animations. This project will add an animation of a two dimensional convex hull algorithm (or more if time permits), which is particularly amenable to visualisation: the "Jarvis March" or "gift wrapping" algorithm. Given a set of points in two dimensions, the convex hull is the smallest convex polygon that contains all points. If you think of each point being a nail sticking out of a board, the algorithm is analogous to tying a string to the leftmost nail, pulling the string tight and wrapping it around the collection of nails until it touches reaches the leftmost nail again. In three dimensions it is like wrapping paper around the points, hence "gift wrapping". There are optimisations to this algorithm and several other more efficient convex hull algorithms that could be tackled.

Visualisation in AIA

We anticipate the existing AIA modules for visualising graphs will be sufficient for animating conxex hull algorithms with little or no modifications. The points can be depicted by graph nodes and the string can be depicted by graph edges. We may want to adjust the size of nodes and write new code to generate random inputs to the algorithm. Also, AIA animations currently do not do "tweening" for graph edges (smooth movement between two different edge positions). If this could be implemented it would be beneficial and could also be retro-fitted to other algorithms.

Project 5: Other sorting algorithms (more details/updates)

AIA has several sorting algorithm animations. Some of these could be enhanced and animations for some some simpler sorting algorithms could be added.

Top-down merge sort is a doubly recursive algorithm and the current animation has a very simple textual visualisation of the stack. Both quicksort and radix exchange sort have similar recursive structure and the AIA animations have graphical stack visualisations. Having similar graphical visualisations for all three algorithms is desirable.

We would also like to see new animations for other sorting algorithms such as insertion sort and selection sort. We have pseudocode for both these algorithms but would like animations. The look of the animations should be guided by the style used in other AIA sorting animations. Additionally, if there are some ways in which algorithmic complexity could be illustrated better to AIA users, that would be of great benefit.