More Like this

1. A Universal In-Place Reconfiguration Algorithm for Sliding Cube-Shaped Robots in a Quadratic Number of Moves

   https://doi.org/10.4230/LIPIcs.SoCG.2024.1  

   Abel, Zachary; A_Akitaya, Hugo; Kominers, Scott Duke; Korman, Matias; Stock, Frederick (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Mulzer, Wolfgang; Phillips, Jeff M (Ed.)

   In the modular robot reconfiguration problem, we are given n cube-shaped modules (or robots) as well as two configurations, i.e., placements of the n modules so that their union is face-connected. The goal is to find a sequence of moves that reconfigures the modules from one configuration to the other using "sliding moves," in which a module slides over the face or edge of a neighboring module, maintaining connectivity of the configuration at all times. For many years it has been known that certain module configurations in this model require at least Ω(n²) moves to reconfigure between them. In this paper, we introduce the first universal reconfiguration algorithm - i.e., we show that any n-module configuration can reconfigure itself into any specified n-module configuration using just sliding moves. Our algorithm achieves reconfiguration in O(n²) moves, making it asymptotically tight. We also present a variation that reconfigures in-place, it ensures that throughout the reconfiguration process, all modules, except for one, will be contained in the union of the bounding boxes of the start and end configuration. 

   more » « less
2. Efficient Approximation of Multiparameter Persistence Modules

   David Loiseaux, Mathieu Carrière (June 2022, ArXivorg)

   Topological Data Analysis is a growing area of data science, which aims at computing and characterizing the geometry and topology of data sets, in order to produce useful descriptors for subsequent statistical and machine learning tasks. Its main computational tool is persistent homology, which amounts to track the topological changes in growing families of subsets of the data set itself, called filtrations, and encode them in an algebraic object, called persistence module. Even though algorithms and theoretical properties of modules are now well-known in the single-parameter case, that is, when there is only one filtration to study, much less is known in the multi-parameter case, where several filtrations are given at once. Though more complicated, the resulting persistence modules are usually richer and encode more information, making them better descriptors for data science. In this article, we present the first approximation scheme, which is based on fibered barcodes and exact matchings, two constructions that stem from the theory of single-parameter persistence, for computing and decomposing general multi-parameter persistence modules. Our algorithm has controlled complexity and running time, and works in arbitrary dimension, i.e., with an arbitrary number of filtrations. Moreover, when restricting to specific classes of multi-parameter persistence modules, namely the ones that can be decomposed into intervals, we establish theoretical results about the approximation error between our estimate and the true module in terms of interleaving distance. Finally, we present empirical evidence validating output quality and speed-up on several data sets. 

   more » « less
3. DNA Origami Words and Rewriting Systems

   https://doi.org/doi.org/10.1007978-3-030-19311-9_9  

   Garrett, James; Jonoska, Natasa; Kim, Hwee; Saito, Masahico (January 2019, Unconventional Computation and Natural Computation)

   McQuillan, I.; Seki, S. (Ed.)

   We classify rectangular DNA origami structures according to their scaffold and staples organization by associating a graphical representation to each scaffold folding. Inspired by well studied Temperley-Lieb algebra, we identify basic modules that form the structures. The graphical description is obtained by ‘gluing’ basic modules one on top of the other. To each module we associate a symbol such that gluing of molecules corresponds to concatenating the associated symbols. Every word corresponds to a graphical representation of a DNA origami structure. A set of rewriting rules defines equivalent words that correspond to the same graphical structure. We propose two different types of basic module structures and corresponding rewriting rules. For each type, we provide the number of all possible structures through the number of equivalence classes of words. We also give a polynomial time algorithm that computes the shortest word for each equivalence class. 

   more » « less
4. Engaging 6th-Grade Students in Ecosystem Education: Exploring Roles and Relationships in Ecology With an Interactive Gamified Module

   https://doi.org/10.1177/00220574241310877  

   Bosch, Emery; Sun, Jonathan; Wang, Andrew; Montclare, Jin_Kim (January 2025, Journal of Education)

   Gamified simulations, integrating gameplay into education, cater to younger learners’ digital preferences and align with Next Generation Science Standards. Current virtual modules focus on advanced high school classes, leaving a gap for middle school students. This study investigated the impact of substituting recitations in a 6th-grade ecology class with Feed the Dingo, a gamified module. Through quizzes evaluating academic performance and free-response surveys to gauge students’ attitudes, the module appeared to enhance intuitive understanding of core ecological concepts (e.g., ecosystems, food webs, biodiversity, etc.), resulting in commendable academic achievement and positive feedback. Such simulations serve as valuable supplements for K-12 lesson planning. 

   more » « less
5. INTEGRATING COMPUTATIONAL THINKING IN HIGH SCHOOL BIOLOGY AND CHEMISTRY CLASSES

   https://doi.org/10.21125/inted.2020.1970  

   Gotwals, R. (January 2020, INTED proceedings)

   Computational thinking is identified as one of the “essential skills for 21st-Century students.” [1] Studies of CT in school programs are being funded by many organizations, including the United States National Science Foundation. In this paper, we describe “lessons learned” over the first two years of a research program (PREDICTS: Principles and Resources for Educators to Infuse Computational Thinking in the Sciences) with the goal of developing knowledge of how to integrate CT into introductory high school biology and chemistry classes for all students. Using curricular modules developed by program staff, two in biology and two in chemistry, teachers piloting the program engaged students in CT with computational evidence from authentic tools in order to develop understanding of science concepts. Each module, representing about a week of instruction, addresses science ideas in the prescribed course of study for high school programs. Project researchers have collected survey data on teachers’: (1) beliefs about effective science teaching; (2) beliefs about their effectiveness as a science teacher and their students’ ability to learn science, and; (3) content preparedness. In addition, we observed module implementation, collected and analyzed student artifacts, and interviewed teachers at the conclusion of module implementation. Preliminary results indicated some challenges (access to technology, varying levels of experience among students) and cause for optimism (student and teacher engagement in CT and the computational tools used in the modules). Continuing research efforts are described in this paper, along with descriptions of the curricular modules and the use of observations and “CT check-ins” to assess student engagement in, application of, and learning of CT. 

   more » « less