Search Content

Compression in Self-Organizing Particle Systems

Description

Many programmable matter systems have been proposed and realized recently, each often tailored toward a particular task or physical setting. In our work on self-organizing particle systems, we abstract away from specific settings and instead describe programmable matter as a collection of simple computational elements (to be referred to as…

Many programmable matter systems have been proposed and realized recently, each often tailored toward a particular task or physical setting. In our work on self-organizing particle systems, we abstract away from specific settings and instead describe programmable matter as a collection of simple computational elements (to be referred to as particles) with limited computational power that each perform fully distributed, local, asynchronous algorithms to solve system-wide problems of movement, configuration, and coordination. In this thesis, we focus on the compression problem, in which the particle system gathers as tightly together as possible, as in a sphere or its equivalent in the presence of some underlying geometry. While there are many ways to formalize what it means for a particle system to be compressed, we address three different notions of compression: (1) local compression, in which each individual particle utilizes local rules to create an overall convex structure containing no holes, (2) hole elimination, in which the particle system seeks to detect and eliminate any holes it contains, and (3) alpha-compression, in which the particle system seeks to shrink its perimeter to be within a constant factor of the minimum possible value. We analyze the behavior of each of these algorithms, examining correctness and convergence where appropriate. In the case of the Markov Chain Algorithm for Compression, we provide improvements to the original bounds for the bias parameter lambda which influences the system to either compress or expand. Lastly, we briefly discuss contributions to the problem of leader election--in which a particle system elects a single leader--since it acts as an important prerequisite for compression algorithms that use a predetermined seed particle.

ContributorsDaymude, Joshua Jungwoo (Author) / Richa, Andrea (Thesis director) / Kierstead, Henry (Committee member) / Computer Science and Engineering Program (Contributor) / School of Mathematical and Statistical Sciences (Contributor) / Barrett, The Honors College (Contributor)

Created2016-05

A Web Applet for Finite-State Automata Visualization

Description

Among classes in the Computer Science curriculum at Arizona State University, Automata Theory is widely considered to be one of the most difficult. Many Computer Science concepts have strong visual components that make them easier to understand. Binary trees, Dijkstra's algorithm, pointers, and even more basic concepts such as arrays…

Among classes in the Computer Science curriculum at Arizona State University, Automata Theory is widely considered to be one of the most difficult. Many Computer Science concepts have strong visual components that make them easier to understand. Binary trees, Dijkstra's algorithm, pointers, and even more basic concepts such as arrays all have very strong visual components. Not only that, but resources for them are abundantly available online. Automata Theory, on the other hand, is the first Computer Science course students encounter that has a significant focus on deep theory. Many of the concepts can be difficult to visualize, or at least take a lot of effort to do so. Furthermore, visualizers for finite state machines are hard to come by. Because I thoroughly enjoyed learning about Automata Theory and parsers, I wanted to create a program that involved the two. Additionally, I thought creating a program for visualizing automata would help students who struggle with Automata Theory develop a stronger understanding of it.

ContributorsSmith, Andrew (Author) / Burger, Kevin (Thesis director) / Meuth, Ryan (Committee member) / Barrett, The Honors College (Contributor) / School of Mathematical and Statistical Sciences (Contributor) / Computer Science and Engineering Program (Contributor)

Created2021-12

Smith Thesis Project

Description

Among classes in the Computer Science curriculum at Arizona State University, Automata Theory is widely considered to be one of the most difficult. Many Computer Science concepts have strong visual components that make them easier to understand. Binary trees, Dijkstra's algorithm, pointers, and even more basic concepts such as arrays…

Among classes in the Computer Science curriculum at Arizona State University, Automata Theory is widely considered to be one of the most difficult. Many Computer Science concepts have strong visual components that make them easier to understand. Binary trees, Dijkstra's algorithm, pointers, and even more basic concepts such as arrays all have very strong visual components. Not only that, but resources for them are abundantly available online. Automata Theory, on the other hand, is the first Computer Science course students encounter that has a significant focus on deep theory. Many
of the concepts can be difficult to visualize, or at least take a lot of effort to do so. Furthermore, visualizers for finite state machines are hard to come by. Because I thoroughly enjoyed learning about Automata Theory and parsers, I wanted to create a program that involved the two. Additionally, I thought creating a program for visualizing automata would help students who struggle with Automata Theory develop a stronger understanding of it.

ContributorsSmith, Andrew (Author) / Burger, Kevin (Thesis director) / Meuth, Ryan (Committee member) / Barrett, The Honors College (Contributor) / School of Mathematical and Statistical Sciences (Contributor)

Created2021-12

Website Example DFA

Description

Among classes in the Computer Science curriculum at Arizona State University, Automata Theory is widely considered to be one of the most difficult. Many Computer Science concepts have strong visual components that make them easier to understand. Binary trees, Dijkstra's algorithm, pointers, and even more basic concepts such as arrays…

Among classes in the Computer Science curriculum at Arizona State University, Automata Theory is widely considered to be one of the most difficult. Many Computer Science concepts have strong visual components that make them easier to understand. Binary trees, Dijkstra's algorithm, pointers, and even more basic concepts such as arrays all have very strong visual components. Not only that, but resources for them are abundantly available online. Automata Theory, on the other hand, is the first Computer Science course students encounter that has a significant focus on deep theory. Many
of the concepts can be difficult to visualize, or at least take a lot of effort to do so. Furthermore, visualizers for finite state machines are hard to come by. Because I thoroughly enjoyed learning about Automata Theory and parsers, I wanted to create a program that involved the two. Additionally, I thought creating a program for visualizing automata would help students who struggle with Automata Theory develop a stronger understanding of it.

ContributorsSmith, Andrew (Author) / Burger, Kevin (Thesis director) / Meuth, Ryan (Committee member) / Barrett, The Honors College (Contributor) / School of Mathematical and Statistical Sciences (Contributor)

Created2021-12

Website Example NFA

Description

Among classes in the Computer Science curriculum at Arizona State University, Automata Theory is widely considered to be one of the most difficult. Many Computer Science concepts have strong visual components that make them easier to understand. Binary trees, Dijkstra's algorithm, pointers, and even more basic concepts such as arrays…

Among classes in the Computer Science curriculum at Arizona State University, Automata Theory is widely considered to be one of the most difficult. Many Computer Science concepts have strong visual components that make them easier to understand. Binary trees, Dijkstra's algorithm, pointers, and even more basic concepts such as arrays all have very strong visual components. Not only that, but resources for them are abundantly available online. Automata Theory, on the other hand, is the first Computer Science course students encounter that has a significant focus on deep theory. Many
of the concepts can be difficult to visualize, or at least take a lot of effort to do so. Furthermore, visualizers for finite state machines are hard to come by. Because I thoroughly enjoyed learning about Automata Theory and parsers, I wanted to create a program that involved the two. Additionally, I thought creating a program for visualizing automata would help students who struggle with Automata Theory develop a stronger understanding of it.

ContributorsSmith, Andrew (Author) / Burger, Kevin (Thesis director) / Meuth, Ryan (Committee member) / Barrett, The Honors College (Contributor) / School of Mathematical and Statistical Sciences (Contributor)

Created2021-12

Sizing-Up in the Cyber Space - Large Scale Cyber Exercises in the 21st Century

Description

This thesis explores how large scale cyber exercises work in the 21st century, going in-depth on Exercise Cyber Shield, the Department of Defense’s largest unclassified cyber defense exercise run by the Army National Guard. It highlights why these cyber exercises are so relevant, going over several large scale cyber attacks…

This thesis explores how large scale cyber exercises work in the 21st century, going in-depth on Exercise Cyber Shield, the Department of Defense’s largest unclassified cyber defense exercise run by the Army National Guard. It highlights why these cyber exercises are so relevant, going over several large scale cyber attacks that have occurred in the past year and the impact they caused. This research aims to illuminate the intricacies around cyber exercise assessment involving manual vs automated scoring systems; this is brought back to work on creating an automated scoring engine for Exercise Cyber Shield. This thesis provides an inside look behind the scenes of the operations of the largest unclassified cyber defense exercise in the United States, including conversations with the Exercise Officer-In-Charge of Cyber Shield as well as a cyber exercise expert working on assessment of Exercise Cyber Shield, and the research also includes information from past final reports for Cyber Shield. Issues that these large scale cyber exercises have faced over the years are brought to light, and attempts at solutions are discussed.

ContributorsZhao, Henry (Author) / Chavez Echeagaray, Maria Elena (Thesis director) / Rhodes, Brad (Committee member) / Barrett, The Honors College (Contributor) / Computer Science and Engineering Program (Contributor) / School of Mathematical and Statistical Sciences (Contributor)

Created2021-12

Enumeration Methods and Series Analysis of Self-Avoiding Polygons on the Hexagonal Lattice, with Applications to Self-organizing Particle Systems

Description

We consider programmable matter as a collection of simple computational elements (or particles) that self-organize to solve system-wide problems of movement, configuration, and coordination. Here, we focus on the compression problem, in which the particle system gathers as tightly together as possible, as in a sphere or its equivalent in…

We consider programmable matter as a collection of simple computational elements (or particles) that self-organize to solve system-wide problems of movement, configuration, and coordination. Here, we focus on the compression problem, in which the particle system gathers as tightly together as possible, as in a sphere or its equivalent in the presence of some underlying geometry. Within this model a configuration of particles can be represented as a unique closed self-avoiding walk on the triangular lattice. In this paper we will examine the bias parameter of a Markov chain based algorithm that solves the compression problem under the geometric amoebot model, for particle systems that begin in a connected configuration with no holes. This bias parameter, $\lambda$, determines the behavior of the algorithm. It has been shown that for $\lambda > 2+\sqrt{2}$, with all but exponentially small probability, the algorithm achieves compression. Additionally the same algorithm can be used for expansion for small values of $\lambda$; in particular, for all $0 < \lambda < \sqrt{\tau}$, where $\lim_{n\to\infty} {(p_n)^{1
}}=\tau$. This research will focus on improving approximations on the lower bound of $\tau$. Toward this end we will examine algorithmic enumeration, and series analysis for self-avoiding polygons.

ContributorsLough, Kevin James (Author) / Richa, Andrea (Thesis director) / Fishel, Susanna (Committee member) / School of Mathematical and Statistical Sciences (Contributor, Contributor) / Computer Science and Engineering Program (Contributor) / Barrett, The Honors College (Contributor)

Created2019-05

Moving Target Defense: Defending against Adversarial Defense

Description

A defense-by-randomization framework is proposed as an effective defense mechanism against different types of adversarial attacks on neural networks. Experiments were conducted by selecting a combination of differently constructed image classification neural networks to observe which combinations applied to this framework were most effective in maximizing classification accuracy. Furthermore, the…

A defense-by-randomization framework is proposed as an effective defense mechanism against different types of adversarial attacks on neural networks. Experiments were conducted by selecting a combination of differently constructed image classification neural networks to observe which combinations applied to this framework were most effective in maximizing classification accuracy. Furthermore, the reasons why particular combinations were more effective than others is explored.

ContributorsMazboudi, Yassine Ahmad (Author) / Yang, Yezhou (Thesis director) / Ren, Yi (Committee member) / School of Mathematical and Statistical Sciences (Contributor) / Economics Program in CLAS (Contributor) / Barrett, The Honors College (Contributor)

Created2019-05

A Two-Way Pushdown Automaton for the Lua Language

DescriptionA two-way deterministic finite pushdown automaton ("2PDA") is developed for the Lua language. This 2PDA is evaluated against both a purpose-built Lua syntax test suite and the test suite used by the reference implementation of Lua, and fully passes both.

ContributorsStevens, Kevin A (Author) / Shoshitaishvili, Yan (Thesis director) / Wang, Ruoyu (Committee member) / School of Mathematical and Statistical Sciences (Contributor) / Computer Science and Engineering Program (Contributor, Contributor) / Barrett, The Honors College (Contributor)

Created2020-05

Development of a Python-Based Software for Calculating the Jones Polynomial: Insights into the Behavior of Polymers and Biopolymers

Description

This thesis details a Python-based software designed to calculate the Jones polynomial, a vital mathematical tool from Knot Theory used for characterizing the topological and geometrical complexity of curves in 3-space, which is essential in understanding physical systems of filaments, including the behavior of polymers and biopolymers. The Jones polynomial serves as a topological…

This thesis details a Python-based software designed to calculate the Jones polynomial, a vital mathematical tool from Knot Theory used for characterizing the topological and geometrical complexity of curves in 3-space, which is essential in understanding physical systems of filaments, including the behavior of polymers and biopolymers. The Jones polynomial serves as a topological invariant capable of distinguishing between different knot structures. This capability is fundamental to characterizing the architecture of molecular chains, such as proteins and DNA. Traditional computational methods for deriving the Jones polynomial have been limited by closure-schemes and high execu- tion costs, which can be impractical for complex structures like those that appear in real life. This software implements methods that significantly reduce calculation times, allowing for more efficient and practical applications in the study of biological poly- mers. It utilizes a divide-and-conquer approach combined with parallel computing and applies recursive Reidemeister moves to optimize the computation, transitioning from an exponential to a near-linear runtime for specific configurations. This thesis provides an overview of the software’s functions, detailed performance evaluations using protein structures as test cases, and a discussion of the implications for future research and potential algorithmic improvements.

ContributorsMusfeldt, Caleb (Author) / Panagiotou, Eleni (Thesis director) / Richa, Andrea (Committee member) / Barrett, The Honors College (Contributor) / School of Mathematical and Statistical Sciences (Contributor) / Historical, Philosophical & Religious Studies, Sch (Contributor)

Created2024-05

Filtering by