October, Week 7

This week's emphasis was on program correctness. To prove that a program works, precondition=>post-condition must be proved, but in order to prove it one has to consider every possible case, and every possible branch that a program can follow. I think that a formal proof of program correctness is not very practical in the real world, for the very same reason described above. If a program is simple recursive function, then it is easy to prove its correctness using formal proof. However, because of its simplicity, I don't see a need of proving it correct, because
it is easy to say whether a simple function works or not just by looking at the code. It would take less time to write a program, proofread the code 5 times, think of every possible scenario (it is possible, because the function is really simple), and test it on some value, rather then take a pencil and prove it. If a function is big, however, the proof will be too complex anyways. Even something as simple as recursive binary search took 2 whole slides to prove during the lecture (and only 1st part of the proof).

October, Week 6

This week we used the unwinding technique along with other tools to solve more problems. One of such problems was to find the time complexity of mergeSort() python function. This problem served as a good example of how different tools can be mixed together to prove something. At the lecture, Danny Heap first found T(n) with unwinding, but only for powers of 2. He then showed the monotonicity of T(n), which would allow us to make conclusions for all n \in N, and not just powers of 2. Danny Heap also introduced the "master theorem for divide-and-conquer", the principle that was used to solve T(n) of mergeSort().

October, Week 5

This week we have been introduced to structural induction, which is a useful tool to deal with data structures such as trees. Structural induction uses the fact that from the definition of a simplest element we can go on to more complex elements. That is, simplest elements serve as bulding blocks for more complex data structures. In case of a tree, it is enough to define a node and how a new tree is constructed.

The Problem

There was a question on Assignment 2 about finding a total number of unique ternary trees that can be constructed with n nodes. And since I have to write up at least one solution to a mathematically-related problem I decided to solve the following problem, which is similar to the problem above, but instead of dealing with a specific case like ternary tree, I will solve the same problem for M-ary tree, the generalized case (so instead of three branches that a ternary tree can have, the M-ary tree can have m number of branches).

Problem: Find the number of unique M-ary trees that can be constructed with n nodes.

Solution:

First, lets consider a specific case, the ternary tree. Here are all possible binary trees with 1 node:

o

There is only one possible tree, the root itself. Now consider trees with 2 nodes:

_tree____tree 2____tree 3

__o______o________o

o________o__________o

Makes sence, because the tree has 3 possible directions, so there are three different way to

connect a root and its child. Now lets think about all the possible places where we can add

an extra node to make it a 3-node tree. Forming a random tree with 3 nodes will probably

not do any good. So we have to keep organized, and add an extra node in a fixed manner.

This will be the way: given a tree, count all the possible places where it is possible to add

an extra node, but only do it for anything that is right of the leaf node of tree we are currently working with, or add it directly to the leaf. So:

o
__o

There is nothing to the right, and the only place to add an extra node is to the leaf itself, as

such:

o_________o__________o

o____OR___o____ OR___o

__o_______o____________o

Total: 3 ways (call it Total1)

Now work with the next tree:

o

o

In this case, it is possible to add 1 extra node to the right part, or the root itself (so that the added node is the root's right child), as such:

o

o o

And, of course, it is also possible to add three extra nodes to the leaf:

__o____o___o

__o____o___o

o______o_____o

Total: 1+3 = 4 ways (call it Total2)

Now, only one tree left to examine:

__o

o

In this case, we can add an extra node to the right of the root, and to the middle of the root:

__o_____________o

o___o_________o__o

And again, it is possible to add 3 extra nodes to the leaf:

____o_____o_____o

__o____o_____o

o______o_______o

Total: 3+2 = 5 (call it Total3)

Now the overall total = Total1+Total2+Total3 = 3+4+5 = 12

We are not really interested in the final answer, '12'. The key is '3+4+5'. Every number is strictly

increasing by one. Coincidence? I think not. :)) In fact it makes sense, because taking into

account the way we add extra nodes, this is exactly what should happen. When we considered

the first tree, it has a rightmost node, so the only way to add something to the tree, was to add it

to that right-most node. And since we are dealing with a ternary tree, which only has 3 possible

directions, there are 3 ways to add an extra node. If it was an M-ary tree, then there would

be M possible ways to add an extra node to a similar tree (looking like a diagonal line from left

to right). The second tree is essentially the first tree, but with a node shifted to the right, which

opens up an extra space for that extra node. So now there are 3+1 possible spaces for an extra node. So for M-ary it would be M+1 then. And the third tree is, again, the first tree, with root's child shifted to the right two times. So noew there are 3+2 possible spcaces for an extra node.

And again, it would be M+2 for M-ary tree (if M>2). Now, since M-ary tree can have any number of directions, it might keep going, as M+3, and M+4, and so on, depending what M is.

Every time we add an extra node to the tree, we increase the number of potential spaces by

3, or M in case of M-ary tree. So, if we could add 3 nodes to a tree with n possible nodes,

then for each of those 3 nodes, we could add 3, 4, and 5 nodes for a tree with n+1 possible nodes.

For n+2, we would expand every number further, so it would be 3,4,5, 3,4,5,6, 3,4,5,6,7.

So we expand each number i as a sum from 3 to i+2 (for ternary tree)

So expanding 3 we would get 3+4+5

4: 3+4+5+6

etc.

The same works for M-ary tree, but we expand each number i as a sum from M to (i+(M-1)).

Knowing how to go from n to n+1, I coded a python function, first for the ternary tree (n>=2),

and then it is easy to generalize for the M-ary tree (n,M>=2):

(This blog formats the lines in a very annoying manner, and doesn't display my python functions properly,
so I included this picture below instead. The "_" instead of spaces in the tree diagrams were for the same reason)

October, Week 4

This week Danny Heap did a lot of examples of unwinding recursive functions. I find the whole
concept of unwinding very interesting, and I think it is a very useful tool for finding (if possible) a closed-form formula and estimating the time complexity of a given function. I found the example of unwinding the zpf(n) function especially interesting. T(n) of zpf(n) had connections to the Fibonacci
sequence, and the whole process of deriving T(n)=2F(n+1)-1 was very captivating.