Matching Items (3)
Filtering by
- All Subjects: Graph Search
- All Subjects: Hardware
- Genre: Masters Thesis
- Creators: Acuna, Ruben
- Creators: Henderson, Christopher
Description
Graph theory is a critical component of computer science and software engineering, with algorithms concerning graph traversal and comprehension powering much of the largest problems in both industry and research. Engineers and researchers often have an accurate view of their target graph, however they struggle to implement a correct, and efficient, search over that graph.
To facilitate rapid, correct, efficient, and intuitive development of graph based solutions we propose a new programming language construct - the search statement. Given a supra-root node, a procedure which determines the children of a given parent node, and optional definitions of the fail-fast acceptance or rejection of a solution, the search statement can conduct a search over any graph or network. Structurally, this statement is modelled after the common switch statement and is put into a largely imperative/procedural context to allow for immediate and intuitive development by most programmers. The Go programming language has been used as a foundation and proof-of-concept of the search statement. A Go compiler is provided which implements this construct.
To facilitate rapid, correct, efficient, and intuitive development of graph based solutions we propose a new programming language construct - the search statement. Given a supra-root node, a procedure which determines the children of a given parent node, and optional definitions of the fail-fast acceptance or rejection of a solution, the search statement can conduct a search over any graph or network. Structurally, this statement is modelled after the common switch statement and is put into a largely imperative/procedural context to allow for immediate and intuitive development by most programmers. The Go programming language has been used as a foundation and proof-of-concept of the search statement. A Go compiler is provided which implements this construct.
ContributorsHenderson, Christopher (Author) / Bansal, Ajay (Thesis advisor) / Lindquist, Timothy (Committee member) / Acuna, Ruben (Committee member) / Arizona State University (Publisher)
Created2018
Description
Plagiarism is a huge problem in a learning environment. In programming classes especially, plagiarism can be hard to detect as source codes' appearance can be easily modified without changing the intent through simple formatting changes or refactoring. There are a number of plagiarism detection tools that attempt to encode knowledge about the programming languages they support in order to better detect obscured duplicates. Many such tools do not support a large number of languages because doing so requires too much code and therefore too much maintenance. It is also difficult to add support for new languages because each language is vastly different syntactically. Tools that are more extensible often do so by reducing the features of a language that are encoded and end up closer to text comparison tools than structurally-aware program analysis tools.
Kitsune attempts to remedy these issues by tying itself to Antlr, a pre-existing language recognition tool with over 200 currently supported languages. In addition, it provides an interface through which generic manipulations can be applied to the parse tree generated by Antlr. As Kitsune relies on language-agnostic structure modifications, it can be adapted with minimal effort to provide plagiarism detection for new languages. Kitsune has been evaluated for 10 of the languages in the Antlr grammar repository with success and could easily be extended to support all of the grammars currently developed by Antlr or future grammars which are developed as new languages are written.
Kitsune attempts to remedy these issues by tying itself to Antlr, a pre-existing language recognition tool with over 200 currently supported languages. In addition, it provides an interface through which generic manipulations can be applied to the parse tree generated by Antlr. As Kitsune relies on language-agnostic structure modifications, it can be adapted with minimal effort to provide plagiarism detection for new languages. Kitsune has been evaluated for 10 of the languages in the Antlr grammar repository with success and could easily be extended to support all of the grammars currently developed by Antlr or future grammars which are developed as new languages are written.
ContributorsMonroe, Zachary Lynn (Author) / Bansal, Ajay (Thesis advisor) / Lindquist, Timothy (Committee member) / Acuna, Ruben (Committee member) / Arizona State University (Publisher)
Created2020
Description
Embedded software is different in many aspects to traditional software; as such, a software developer may face issues when attempting to transition from traditional to embedded software development. This thesis explores providing feedback and applying optimizations at the source code level of embedded software. The aim is to measure the impact of these optimizations on teaching embedded software design principles, as well as assessing the relative success of each optimization in terms of a variety of metrics. There are many considerations when altering code and is a known limitation imposed by most software optimization schemes. By applying optimizations at the source level, the aim is to demonstrate what the optimizations do and how they provide value to the resulting software. In order to fulfill these goals, the Embedded C Source Optimizer has been developed, which is used to import and export code, select which optimizations are applied, and provide feedback to the end user. This utility abstracts away the lower level operations performed by each optimization, while conveying the resulting changes to the end user. Since embedded systems are generally quite limited compared to modern computers, someone transitioning from traditional software design to embedded software may find it challenging to understand how to overcome these limitations. Clearly conveying means to improve a naive implementation of an embedded program aids through demonstrating what changes need to be made to satisfy embedded design rules. The optimizations which the utility can apply range from simple replacement operations to more complex applications of implicit utilization of built-in hardware peripherals on supported microcontrollers. Each optimization comes with its own set of considerations, risks, and potential level of improvement to the resulting code. These optimization options are evaluated by comparing embedded software before and after each option is applied through a variety of metrics, allowing the relative success of each to be determined as effectively as possible. The end goal for this utility is to aid in crossing the hurdle from traditional software to embedded software in a comprehensive and educational manner, with the provided optimization options acting as an avenue for teaching embedded concepts.
ContributorsLisonbee, Tanner Boyd (Author) / Heinrichs, Robert (Thesis advisor) / Acuna, Ruben (Committee member) / Jordan, Shawn (Committee member) / Arizona State University (Publisher)
Created2021