Repository logo

Browsing by Author "Bohm, Wim, advisor"

Now showing 1 - 2 of 2
  • Thumbnail Image
    ItemOpen Access
    Garbage elimination in SA-C host code
    (Colorado State University. Libraries, 2001) Segreto, Steve, author; Bohm, Wim, advisor; Draper, Bruce, committee member
    Single-assignment C (SA-C) is a functional programming language with a rich instruction set designed to create and manipulate arrays using array slices and window generators. It is well-suited for the fields of graphics, AI and image processing within reconfigurable computing environments. Garbage is defined as any SA-C array data which is unused or unreferenced in the host code program heap at any time. Garbage must not be created and it must be freed as soon as possible. In this paper it will be shown that the single-assignment properties of the language create garbage when single-assignment occurs in loops. This behavior is studied and a static solution is presented called pointer reuse. The non-circular aliases resulting from strict single-assignment alias creation coupled with the side-effect free nature of statement blocks lead to a dynamic reference counting technique which can provide immediate elimination of garbage. Aliases and special loop-carried variable dependencies complicate matters further and are examined in this paper.
  • Thumbnail Image
    ItemOpen Access
    Space efficient string search algorithms and data structures
    (Colorado State University. Libraries, 2015) Deoghare, Pratik, author; McConnell, Ross, advisor; Bohm, Wim, advisor; Hulpke, Alexander, committee member
    We address the problem of finding all the occurrences of a pattern of length m in a text of length n. We introduce two new data structures, called the Sloppy Suffix Array and the Super Sloppy Suffix Array. These data structures are space efficient, easy to understand and implement. Sloppy suffix arrays can be built faster than suffix arrays with just one array of n integers; the search algorithms for both have the same time complexity of O(m log n). We also give a space efficient representation for positional de Bruijn graphs using suffix arrays.