November, Week 11

Another week has passed... And it is also almost the second last week before the exams. Which are pretty much the end of this semester. Which means that the end of this whole school year is also almost over, only one more semester to go. And from there graduation is not so far away. In terms of CSC236, this week was about different applications and techniques of FSA's. I found the cartesian product of two DFSA technique quite interesting. For some reason I thought that,

despite the fact that there always exists a union of two regular expressions (and therefore two DFSA's), the way to find this union is more or less trivial. And summing up what we have learned this week, it turns out that there exists an actual technique. By building DFSA's of both regexes, then using cartesian product to get a union DFSA, and finally decomposing it to get the final regex, you can pretty much find any union. And this means it is easy to find any possible regex. Just divide it into smaller parts and use the technique to find intersections. Very nice.

November, Week 10

The main theme of this week was the finite-state automatas and deterministic finite-state automatas (I wrote full names on purpose, so that this slog entry appears bigger. This remark is written for the same reason). Finite state machines are a very interesting topic, and I actually find it pretty amazing that a machine that performs a single transition based on a finite state it is in, and the data it sees, can do some pretty amazing stuff (like determining if a string is a multiple of 3 in base 2 or not). Consider a Turing machine. Although it is not exactly what we studied in class, it has many similarities with a DFSA. A 5-tuple Turing has instructions in the form of (q, ss, sp, dir, q'), where q and q' are states, ss and sp are symbols (e.g. '1' or '0'), and dir is direction to move the tape (left or right). This 5-tuple basically translates as


if (current state == q)
{
if (see symbol ss)
{
erase ss and print symbol sp in its place;
move tape in direction dir;
current state = q';
}
}

As simple as this machine is, it is actually able to simulate the logic of any computer algorithm.
First I couldn't believe it, but it turns out that it is actually true. I started researching and I wanted to find an RSA encryption algorithm written on a Turing machine (most likely a 1000+ page text file of state invariants), but I was not able to find one.

November, Week 9

This week we have been introduced to the concept of formal languages and regular expressions. Although I am quite familiar with regular expressions, as I have used them a lot with various programming languages, my knowledge was not relevant, because csc236 tends to look at everything from a different perspective, a more in-depth, "theoretical" approach. For example, I never thought of multiplying or adding, or dividing regular expressions when I used them :) I even found out that there is such thing as "Kleene algebra". The concepts were still pretty straight-forward, so this is pretty much everything I can force myself to write.

October/November, Week 8

This week we continued on the topic of program correctness, but the emphasis was on loops. I found the concepts straight-forward, except for the double loop that Danny Heaps proved on Friday. The proof turned out to be rather long, 4 (!) full slides.

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.

September

Today is the last day of September, the first month of school is over. I enjoyed csc165 last year. I found csc236 somewhat refreshing and I am glad that after a long careless summer of working in construction, I can now resume working with my mind on induction problems rather than with my hands mixing plaster all day and installing drywalls.
Danny Heap introduced some of the new tools such as strong induction and well-ordering principle.
I found it interesting how simple and strong induction can be applied to prove facts that have long been thought of something not requiring to proved. So far, I found the concepts pretty straight-forward, but I guess this is just the beginning.