MACM 201, February 13 and February 15

Based on these excellent lecture recordings by Jamie Mulholland

Warning: the cells in each section may be linked!

Divide and Conquer Algorithms

Pause at 5'59'': Bubblesort vs Mergesort
Pause at 12'13'': the merge function
Pause at 20'45'': the Mergesort algorithms
Pause at 43'46'': adding an array of numbers
A comment from Nils Bruin:

The instructions A[:n] and A[n:] actually construct sublists, so their cost is $O(n)$. So the run time of this algorithm will actually be worse, because the overhead in constructing extra data structures overwhelms the addition operations.

Balanced adding, as basically proposed, is actually difficult to justify: the cost of these additions hardly changes. For floats there is something to be managed, of course, but that's of an entirely different nature.

For a big product of integers there is actually a very good argument to be made for this, because assuming you start with a list of integers of approximately equal size, balanced products will lead to way more small (and hence cheaper) multiplications. But this isn't taken into account in the analysis here, of course :-).

The balanced adder in Python should look more like:

Solving Recurrences Using Python's (SymPy) rsolve command

The Fibonacci recurrence
The towers of Hanoi recurrence
A second order recurrence

Examples of Generating Functions

Pause at 11'00'': $a_1+a_2+a_3=7$ is equivalent to $x^{(a_1+a_2+a_3)}=x^7$, or, $x^{a_1} x^{a_2} x^{a_3} = x^7$. This translates a sum into a product.

Pause at 34'36'': Actually, if all we want is the coefficient $[x^9]$, the first sum need not stop at $x_9$, and the second sum need not stop at $x_8$. Can you see why \[ [x^9](x+x^3+x^5+x^7+x^9+\cdots+x^{2k+1}+\cdots)(1+x^2+x^4+x^6+x^8+\cdots+x^{2k}+\cdots)(1+x^3+x^6)=[x^9](x_1+x_3+x_5+x_7+x_9)(1+x^2+x^4+x^6+x^8)(1+x^3+x^6)? \]

Pause at 40'50'': $Q(x)$ is a formal power series here, and we ignore questions on convergence. (If we thought of $Q(x)$ as a power series, we would insist that $|x|<1$.)

Stop at 47'18''. I will continue when I am back.