Comparative analysis of the Metropolis-Hastings algorithm as applied to the domain of program synthesis

In this research the Metropolis-Hastings algorithmis implemented for the problem of program synthesis and compared with Brute, a best-first search, together with multiple other different search algorithms. The implementation and choices of the Metrolpolis-Hastings algorithm are discussed in detail. The algorithms are tested for three different domains, each with their own associated DSL. Finally, comparisons are drawn between the search algorithms by analyzing the results of these experiments. It is found that the performance of any search algorithm depends very heavily on the specific domain and cost function used and the Metropolis-Hastings algorithm falls short in terms of performance when compared with other conventional methods.CSE3000 Research ProjectComputer Science and Engineerin