Department of Computer Science

Permanent URI for this community

https://scholar.sun.ac.za/handle/10019.1/96336

Browse

Browsing Department of Computer Science by browse.metadata.advisor "Geldenhuys, Jaco"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    The generation of longest optimal box repetition-free words
    (Stellenbosch : Stellenbosch University, 2022-04) Habeck, Manfred; Grobler, Trienko; Van Zijl, Lynette; Geldenhuys, Jaco; Stellenbosch University. Faculty of Science. Dept. of Computer Science.
    ENGLISH ABSTRACT: This thesis focuses on a specific problem within the field of combinatorial generation, namely, the generation of box repetition-free words. A box is a word over a given alphabet, where the first symbol in the word is the same as the last symbol. For example, the word abaca is a box. A box can contain other boxes. The box abaca contains boxes aba and aca. Boxes can overlap, such as aba and aca in abaca. This work investigates the generation of the longest possible sequence of symbols, over a given alphabet, which does not contain any repeating boxes. We show that an exhaustive enumeration based on a brute force approach with backtracking is not feasible. That is, we checked if adding a symbol to a word would create a repeating box; if not, recursively add another symbol. This method will eventually find all valid words, but takes an unreasonable amount of time for larger alphabets. As a non-enumerative attempt to find individual valid words, the Monte Carlo tree search is used. The search is based on the assumption that prefixes with good past results will also give good results in the future. Based on an analysis of the properties of box repetition-free words, a new search is devised. Factors of words are mapped onto a graph, and all non-optimal edges removed. It is then shown that any Hamiltonian path on this graph will result in a longest optimal word. The results of this work show that backtracking fails to generate longest optimal words within a reasonable time for any alphabet with more than three symbols. The Monte Carlo tree search performs better than backtracking, finding optimal words for an alphabet size of four, but failing for larger alphabets. The new method outperforms both, and with a small optimization, is shown to generate longest optimal words up to an alphabet size of six.
  • Thumbnail Image
    Item
    Impendulo: A Tool for Analysing Programmer Behaviour
    (Stellenbosch : Stellenbosch University, 2015-03) Jordaan, Pieter; Visser, Willem; Geldenhuys, Jaco; Stellenbosch University. Faculty of Science. Department of Mathematical Sciences (Computer Science)
    ENGLISH ABSTRACT : Automated submission systems for Computer Science courses are common- place today, however, these systems are typically solely focused on grading submissions and their ability to provide analysis and feedback is vastly under- utilised. This thesis seeks to address this by presenting Impendulo, a platform for analysing programmer behaviour. Impendulo allows one to study student per- formance at both a group and an individual level. This is achieved through the use of a customisable set of software analysis tools which Impendulo runs on user submissions. The results produced by the tools are parsed by Impendulo to produce rich feedback in the form of interactive charts, annotated code and detailed reports. In order to ascertain whether Impendulo's approach is viable, experimental trials were conducted with it throughout its development process. These trials consisted of a group of students using the Impendulo system while solving a set of programming problems. After each trial, the results were studied and used to determine which aspects of the system needed to be improved. At the end of Impendulo's development, all of the experiments were studied again to gain insight into the tested students' programming.
  • Thumbnail Image
    Item
    Optimised constraint solving for real-world problems
    (Stellenbosch : Stellenbosch University, 2019-12) Taljaard, Johannes Hendrik; Visser, Willem; Geldenhuys, Jaco; Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Division Computer Science.
    ENGLISH ABSTRACT: Although significant advances in constraint solving technologies have been made during the past decade, Satisfiability Modulo Theories (SMT) solvers are still a significant bottleneck in verifying program properties. To overcome the performance issue, different caching strategies have been developed for constraint solution reuse. One of the first general frameworks for doing such caching was implemented in a tool called Green. Green allows extensive customisation, but in its basic form it splits a constraint to be checked into its independent parts (called factorisation), performs a canonisation step (including renaming and reordering of variables) and looks up results in a cache. More recently an alternative approach was suggested: rather than looking up sat or unsat results in a cache, it stores models (in the satisfiable case) and unsatisfiable cores (in the unsatisfiable case), and re uses these objects to establish the result of new constraints. This model reuse approach is re-implemented in Green and investigated further with an extensive evaluation against various Green configurations as well as incremental sat solving. The core findings highlight that the factorisation step is the crux of the different aching strategies.The results shed new light on the true benefits and weaknesses of the respective approaches.