Encoding Recursion with the Y Combinator

In this post I’ll go through some exercises and encode some recursive functions with the Y combinator. Encoding with rec Continuing on from my last post, Professor Hutton gave us two exercises in the Y combinator video: Encode loop (the function that just calls itself) with rec.  I.e., loop = rec…

Merge Sort and the Divide and Conquer Approach

Algorithm Design Techniques In earlier posts, I went through the insertion sort and the selection sort algorithms.  They both use the incremental approach.  Each step of the algorithms sorts one element, and thus the algorithms solve the problem incrementally. The divide-and-conquer is another approach.  It includes 3 steps that are…