Problem You are given degree sequence \(A\), determine the number of possible caterpillars. We say that the graphs are different if they are not isomorphic. Solution Let us prove first prove the following fact: the degree sequence \(A = (a_1,\ldots, a_n)\) can form a tree if and only if the sum of degree sequence is equal to \(2\cdot (n - 1)\) and that \(\forall i:\, a_i > 0\). The only if direction is true by the definition of tree....
LeetCode’s Sort an Array problem was a push for me to really understand different sorting algorithms. So I decided to implement few sorting algorithms. Bubble sort Bubble sort is considered as the simplest sorting algorithm out there. The idea is to scan through an array and swap consecutive elements if they are in word ordered until the array gets sorted. In Java, we have int[] bubbleSort(int[] a){ int n = a....
Suppose we want to generate image of spiral by printing line by line. You are given natural number \(n\), where \(n\) denotes sidelength of spiral (number of lines). For example, for \(n = 11\), program must display following figure on the console: # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # Interestingly enough, this is not as simple as it might seem, especially, when you can only use string concatenation (and not use any arrays, lists, etc)....