Matching Items (19)
Filtering by
Description
This thesis discusses three recent optimization problems that seek to reduce disease spread on arbitrary graphs by deleting edges, and it discusses three approximation algorithms developed for these problems. Important definitions are presented including the Linear Threshold and Triggering Set models and the set function properties of submodularity and monotonicity. Also, important results regarding the Linear Threshold model and computation of the influence function are presented along with proof sketches. The three main problems are formally presented, and NP-hardness results along with proof sketches are presented where applicable. The first problem seeks to reduce spread of infection over the Linear Threshold process by making use of an efficient tree data structure. The second problem seeks to reduce the spread of infection over the Linear Threshold process while preserving the PageRank distribution of the input graph. The third problem seeks to minimize the spectral radius of the input graph. The algorithms designed for these problems are described in writing and with pseudocode, and their approximation bounds are stated along with time complexities. Discussion of these algorithms considers how these algorithms could see real-world use. Challenges and the ways in which these algorithms do or do not overcome them are noted. Two related works, one which presents an edge-deletion disease spread reduction problem over a deterministic threshold process and the other which considers a graph modification problem aimed at minimizing worst-case disease spread, are compared with the three main works to provide interesting perspectives. Furthermore, a new problem is proposed that could avoid some issues faced by the three main problems described, and directions for future work are suggested.
ContributorsStanton, Andrew Warren (Author) / Richa, Andrea (Thesis director) / Czygrinow, Andrzej (Committee member) / Computer Science and Engineering Program (Contributor) / Barrett, The Honors College (Contributor)
Created2018-05
Description
This paper examines creative process and performance as a method of research for understanding self-in-context through the lens of my own artistic research for “Dress in Something Plain and Dark,” a project exploring my relationship as a woman to Mennonite religious and cultural identity, spirituality, and dance. Situating my artistic work in relationship to the fields of creative autoethnography, queer and transborder performance art, and somatic dance practice, I discuss the distinctions and commonalities of approach, methods, and practice of artists working in these fields, and the shared challenges of marginalization, translation, and contextualization. In response to these challenges, and the inadequacy of linear, Western, individualistic and mechanistic frameworks to address them, I draw from the ethnographic work of de la Garza, (formerly González, 2000) to seek a “creation-centered” ontological framework that the artist-researcher-performer may use to understand and contextualize their work. I offer the tree as an ontology to understand the organic, emergent nature of creative process, the stages of growth and seasonal cycles, and the structural parts that make up the creative and performative processes, and illustrate this model through a discussion of the growth of “Dress in Something Plain and Dark,” as it has emerged over two cyclical “seasons” of maturation.
Note: This work of creative scholarship is rooted in collaboration between three female artist-scholars: Carly Bates, Raji Ganesan, and Allyson Yoder. Working from a common intersectional, feminist framework, we served as artistic co-directors of each other’s solo pieces and co-producers of Negotiations, in which we share these pieces alongside each other. Negotiations is not a showcase of three individual works, but a conversation among three voices. As collaborators, we have been uncompromising in the pursuit of our own unique inquiries and voices and each of our works of creative scholarship stand alone. However, we believe that all of the parts are best understood in relationship to each other and to the whole. For this reason, we have chosen to cross-reference our thesis documents here, and we encourage readers to view the performance of Negotiations in its entirety.
Thesis documents cross-referenced:
French Vanilla: An Exploration of Biracial Identity Through Narrative Performance, by Carly Bates
Bhairavi: A Performance-Investigation of Belonging and Dis-Belonging in Diaspora Communities, by Raji Ganesan
Deep roots, shared fruits: Emergent creative process and the ecology of solo performance through “Dress in Something Plain and Dark,” by Allyson Yoder
Note: This work of creative scholarship is rooted in collaboration between three female artist-scholars: Carly Bates, Raji Ganesan, and Allyson Yoder. Working from a common intersectional, feminist framework, we served as artistic co-directors of each other’s solo pieces and co-producers of Negotiations, in which we share these pieces alongside each other. Negotiations is not a showcase of three individual works, but a conversation among three voices. As collaborators, we have been uncompromising in the pursuit of our own unique inquiries and voices and each of our works of creative scholarship stand alone. However, we believe that all of the parts are best understood in relationship to each other and to the whole. For this reason, we have chosen to cross-reference our thesis documents here, and we encourage readers to view the performance of Negotiations in its entirety.
Thesis documents cross-referenced:
French Vanilla: An Exploration of Biracial Identity Through Narrative Performance, by Carly Bates
Bhairavi: A Performance-Investigation of Belonging and Dis-Belonging in Diaspora Communities, by Raji Ganesan
Deep roots, shared fruits: Emergent creative process and the ecology of solo performance through “Dress in Something Plain and Dark,” by Allyson Yoder
ContributorsYoder, Allyson Joy (Author) / de la Garza, Sarah Amira (Thesis director) / Ellsworth, Angela (Committee member) / DeWitt, Inertia Q. E. D. (Committee member) / School of Film, Dance and Theatre (Contributor) / Herberger Institute for Design and the Arts (Contributor) / Barrett, The Honors College (Contributor) / Hugh Downs School of Human Communication (Contributor)
Created2016-05
Description
A primary goal in computer science is to develop autonomous systems. Usually, we provide computers with tasks and rules for completing those tasks, but what if we could extend this type of system to physical technology as well? In the field of programmable matter, researchers are tasked with developing synthetic materials that can change their physical properties \u2014 such as color, density, and even shape \u2014 based on predefined rules or continuous, autonomous collection of input. In this research, we are most interested in particles that can perform computations, bond with other particles, and move. In this paper, we provide a theoretical particle model that can be used to simulate the performance of such physical particle systems, as well as an algorithm to perform expansion, wherein these particles can be used to enclose spaces or even objects.
ContributorsLaff, Miles (Author) / Richa, Andrea (Thesis director) / Bazzi, Rida (Committee member) / Computer Science and Engineering Program (Contributor) / Barrett, The Honors College (Contributor) / School of Mathematical and Statistical Sciences (Contributor)
Created2015-05
Description
Language is powerful. The words we use define our perceptions. They label what we see and paint a picture for those with whom we are communicating. Words serve as heuristic when assigning value to an object, experience, or person. My thesis, Eye of the BeholdHer, focuses on the language used in American pop-culture to describe women. I comment on the dehumanization of women through the use of animal names used to describe personality, appearance, and genitalia, as well as the way the English language implies domestication and inferiority of women through the use of the certain words. Examples include, but are not limited to: bitch , chick, pussy, beaver, cougar, catty, heifer, old bat, mousy, foxy, and vixen. Eye of the Behold(her) reflects upon my observations and calls for social change. Eye of the BeholdHer is a call for action. It is time to make conscious word choices and realize the impact words have on shaping our society. It is time for us to empowHer through words.
ContributorsGibly, Sophia (Author) / Maxwell, Kathryn (Thesis director) / Ellsworth, Angela (Committee member) / Barrett, The Honors College (Contributor) / Department of Psychology (Contributor) / School of Art (Contributor)
Created2014-05
Description
You Are Here is a mixed-media installation, featuring the thesis work of BFA: Intermedia senior, Carissa Kalia Heinrichs. The installation consists of a hanging fabric structure, in which gallery visitors may interact with by both circumambulating and entering the form, walking alongside ever transforming horizons. The exhibition addresses the re-contextualization of "here", challenging its containment, and inviting viewers to study diverse definitions of home encompassed in a single shared space. The exhibition will encompass the conceptual and technical growth fostered by the artist's academic career at both the Herberger Institute for Design and the Arts, as well as the Barrett Honors College at Arizona State University.
ContributorsHeinrichs, Carissa Kalia (Author) / Ellsworth, Angela (Thesis director) / Gutierrez, Rogelio (Committee member) / Danh, Binh (Committee member) / Barrett, The Honors College (Contributor) / School of Art (Contributor)
Created2014-05
Description
As technologies advance, so does the curiosity and exploration of humankind. There are many domains across this planet that are unexplored \u2014 the depths of Earth's ocean being one of the most predominant. While the ocean covers seventy percent of Earth's surface, a vast ninety-five percent of this realm remains untouched and unseen by the human eye. The biggest causality of this can be identified in the limitations of current technologies and the large expense associated with delving into these dangerous and uncharted areas. Underwater communication between unmanned devices is the solution to this problem. With the oceanic deployment of wirelessly connected unmanned underwater vehicles (UUVs), researchers can limit risk to human safely and retrieve invaluable oceanographic data from unimaginable depths. However, before this system can be physically deployed, the network topology and environmental interactions must be simulated. More specific to the application, how does attenuation of optical propagation degrade between transmissions? A widely used open source network simulator is the ns series: ns-1, ns-2, and ns-3. Ns-3 is the most recent version, and is a valuable tool for modeling network interactions. However, underwater simulation proposes a limitation \u2014 a three-dimensional consideration for pressure. To properly model this interaction, it is vital that an extension to ns-3 be provided in order to account for the affects pressure has on the propagation of a signal at varying depths.
ContributorsSowa, Ryan John (Author) / Richa, Andrea (Thesis director) / Saripalli, Srikanth (Committee member) / Zhou, Chenyang (Committee member) / Barrett, The Honors College (Contributor) / Computer Science and Engineering Program (Contributor)
Created2013-05
Description
Many systems in the world \u2014 such as cellular networks, the post service, or transportation pathways \u2014 can be modeled as networks or graphs. The practical applications of graph algorithms generally seek to achieve some goal while minimizing some cost such as money or distance. While the minimum linear arrangement (MLA) problem has been widely-studied amongst graph ordering and embedding problems, there have been no developments into versions of the problem involving degree higher than 2. An application of our problem can be seen in overlay networks in telecommunications. An overlay network is a virtual network that is built on top of another network. It is a logical network where the links between nodes represent the physical paths connecting the nodes in the underlying infrastructure. The underlying physical network may be incomplete, but as long as it is connected, we can build a complete overlay network on top of it. Since some nodes may be overloaded by traffic, we can reduce the strain on the overlay network by limiting the communication between nodes. Some edges, however, may have more importance than others so we must be careful about our selection of which nodes are allowed to communicate with each other. The balance of reducing the degree of the network while maximizing communication forms the basis of our d-degree minimum arrangement problem. In this thesis we will look at several approaches to solving the generalized d-degree minimum arrangement d-MA problem where we embed a graph onto a subgraph of a given degree. We first look into the requirements and challenges of solving the d-MA problem. We will then present a polynomial-time heuristic and compare its performance with the optimal solution derived from integer linear programming. We will show that a simple (d-1)-ary tree construction provides the optimal structure for uniform graphs with large requests sets. Finally, we will present experimental data gathered from running simulations on a variety of graphs to evaluate the efficiency of our heuristic and tree construction.
ContributorsWang, Xiao (Author) / Richa, Andrea (Thesis director) / Nakamura, Mutsumi (Committee member) / School of Mathematical and Statistical Sciences (Contributor) / Computer Science and Engineering Program (Contributor) / Barrett, The Honors College (Contributor)
Created2016-05
Description
This paper is a supplement to our interactive algorithmic art generator project which can be found at weiverlyroe.github.io/waverlyplace. For this thesis, we demonstrate how with certain input we can algorithmically generate art, specifically a playable random maze with exactly one solution. We explore interactive and algorithmic art and how our mazes are a form of both. Through examining several maze generation algorithms, we show that an ideal representation of a single-solution maze, called a perfect maze, is a spanning tree of a planar graph. The final algorithm is a re-imagining of Kruskal's Minimum Spanning Tree Algorithm with these adjustments: (1) potential edges are ordered randomly rather than sorted and (2) certain edges are forced in the maze in order for the wall structure to display the player's text input. Lastly, we discuss improvements which could be made and features which we plan to add to the project in the future.
ContributorsRoeger, Waverly Wu (Author) / Richa, Andrea (Thesis director) / Ellsworth, Angela (Committee member) / Computer Science and Engineering Program (Contributor) / Barrett, The Honors College (Contributor)
Created2016-12
Description
Although frequently undetected or ignored, counterculture groups commonly face misrepresentation in popular media and, in turn, society. These subcultures are often depicted as undesirable or dangerous, creating a negative stereotype that follows the individuals who choose to express themselves in the aesthetics and lifestyles of non-normative communities. This creative project celebrates the beauty and sense of rebellion that can be seen in counterculture groups, and provides viewers with a window for viewing them in a new perspective. Considering the vastness of this topic, this project approaches it from three different directions: a series of photographic staged portraits, a series of digitally illustrated character portraits, and a written analysis to begin a discussion around the types of misrepresentation of countercultures and the potential impacts of that phenomenon. The process of planning was difficult yet rewarding, as it was important to ensure that the work would not contribute to the cycle of misinformation, but rather bring visibility to countercultures in the formal art realm. The photographed body of work recreates the composition of famous genre paintings by Judith Leyster and Johannes Vermeer, but substitutes the subjects for a model dressed in the conventional aesthetic of a particular counterculture. There are four portraits in this series, depicting Punk, Goth, Metal, and Emo cultures, using costuming as well as clues in the surrounding environments. By adopting the genre practice of depicting scenes of everyday life, the counterculture communities become normalized for the viewer as people living similar lives to their own. This portion of the thesis is largely inspired by Cindy Sherman, a visual artist who stages portraits of herself as various characters to comment on ideals of beauty and the female form. Continuing to examine the idea of personality in counterculture, the digitally illustrated body of work pulls from four other countercultures to create portraits of fictional characters. Although imaginative, their designs reflect genuine aesthetics of the communities they represent, and are combined with photographic imagery to suggest their connection to real world peoples. The images represent Grunge, Glam-Rock, Non-Binary, and Scene cultures, with each character receiving a name, location, and occupation to challenge first impressions and demonstrate their roles in society. The characters are drawn in a cartoon-like style with the intent to design them as something one might see in popular media (such as in graphic novels). Lastly, these bodies of work are complemented by a brief analytical introduction into the issues of misrepresentation of countercultures in popular media. Intended to be a catalyst for future discussions, the piece discusses the importance of representation and the harmful effects of misinformation in media, and explores contemporary examples of such issues in depictions of Punk and Goth communities in television. In combination with the two series, this analysis will guide viewers as they proceed to interpret and internalize their own meaning from the project.
ContributorsFinger, Kourtney Rose (Author) / Drum, Meredith (Thesis director) / Ellsworth, Angela (Committee member) / School of Art (Contributor) / Barrett, The Honors College (Contributor)
Created2018-12
Description
Implementing a distributed algorithm is more complicated than implementing a non-distributed algorithm. This is because distributed systems involve coordination of different processes each of which has a partial view of the global system state. The only way to share information in a distributed system is by message passing. Task that are straightforward in a non-distributed system, like deciding on the value of a global system state, can be quite complicated to achieve in a distributed system [1]. On top of the difficulties caused by the distributed nature of the computations, distributed systems typically need to be able to operate normally even if some of the nodes in the system are faulty which further adds to the uncertainty that processes have about the global state. Many factors make the implementation of a distributed algorithms difficult. Design patterns [2] are useful in simplifying the development of general algorithms. A design pattern describes a high level solution to a common, abstract problem that many systems may face. Common structural, creational, and behavioral problems are identified and elegantly solved by design patterns. By identifying features that an algorithm uses, and framing each feature as one of the common problems that a specific design pattern solves, designing a robust implementation of an algorithm becomes more manageable. In this way, design patterns can aid the implementation of algorithms. Unfortunately, design patterns are typically not discussed when developing distributed algorithms. Because correctly developing a distributed algorithm is difficult, many papers (eg. [1], [3], [4]) focus on verifying the correctness of the developed algorithm. Papers that are more practical ([5], [6]) establish the correctness of their algorithm and that their algorithm is efficient enough to be practical. However, papers on distributed algorithms usually make little mention of design patterns. The goal of this work was to gain experience implementing distributed systems including learning the application of design patterns and the application of related technical topics. This was achieved by implementing a currently unpublished algorithm that is tentatively called Bakery Consensus. Bakery Consensus is a replicated state-machine protocol that can tolerate servers with Byzantine faults, but assumes non-faulty clients. The algorithm also establishes non-skipping timestamps for each operation completed by the replicated state-machine. The design of the structure, communication, and creation of the different system parts depended heavily upon the book Design Patterns [2]. After implementing the system, the success of the in implementing its various parts was based upon their ability to satisfy the SOLID [7] principles as well as their ability to establish low coupling and high cohesion [8]. The rest of this paper is organized as follows. We begin by providing background information about distributed algorithms, including replicated state-machine protocols and the Bakery Consensus algorithm. Section 3 gives a background on several design patterns and software engineering principles that were used in the development process. Section 4 discusses the well designed parts of the system that used design patterns, and how these design patterns were chosen. Section 5 discusses well designed system parts that relied upon other technical topics. Section 6 discusses system parts that need redesign. The conclusion summarizes what was accomplished by the implementation process and the lessons learned about design patterns for distributed algorithms.
ContributorsStoutenburg, Tristan Kaleb (Author) / Bazzi, Rida (Thesis director) / Richa, Andrea (Committee member) / Computer Science and Engineering Program (Contributor) / Barrett, The Honors College (Contributor)
Created2017-05