2-2 Correctness of bubblesort
The subject of binary trees provides a lot of variation, mainly in the number of ways in which they can be classified. This, in turn, provides an array of inductive proofs that can be applied differently dependending on your input data. This post is intended to cover some of the variations of binary trees and neat proofs relating to their number of nodes ($N$), number of internal nodes ($I$), number of leaves ($L$), and height ($H$).
2.1 Insertion sort on small arrays in merge sort
I got this problem from The Algorithm Design Manual by Steven Skiena. It’s a fairly simple exercise in Chapter 2 that I felt had a neat symmetry, so I’ve decided to write a bit about it.