FSA---a machine to determine a language

I find it's interesting to use FSA (Finite State Automata) to determine whether an expression belongs to the language. There are five important elements for each FSA: the set of all states,
a finite alphabet, transition functions, initial state and the set of accepting states. When I have an expression, I begins with the initial state and then, I look over the first character in the expression and go to the next state according to the transition function. After that, I look over the next character in the expression and go one state further. By the time that I have checked all characters in the expression, if I am in an accepting state, the expression belongs to the language and if it is not, the expression does not belong to the language denoted by the FSA.

Problem solving episode---WalkTilings(3)

I have shown that f(1) = 1, f(2) = 2, f(n) = f(n-1) + f(n-2) for n >= 3. So it seems that the solution is a sequence of Fabonacci numbers with f(n) = F(n+1), where F is Fabonacci numbers. Now I will prove this using complete induction.

Case1: When n = 1, f(1) = 1 = F(2).
Case2: When n = 2, f(2) = 2 = F(3).
Case3: When n >=3, suppose f(n-1) and f(n-2) and ... and f(1) is true. f(n) = f(n-1) + f(n-2) = F(n) + F(n-1) = F(n+1). So f(n) is true.

Conclude: for any natural number n >=1, f(n) = F(n+1).

Problem solving episode---WalkTilings(2)

I have shown the solution for the problem when n is small(from 1 to 5). Now I will find out the relationship between n and n + 1, beginning from small n. Suppose the solution for n is f(n).

How to get the solution for n = 3 from n = 2? My idea is that first put a tile in the leftmost 2*1 rectangle, then for the left 2*2 rectangle, I have 2 choices to put tiles, which is the solution for n = 2. Then I expand the leftmost 2*1 rectangle to the leftmost 2*2 rectangle. I have two choices to put tiles in this rectangle, but to avoid duplicates, I can only tile this one with two horizontal 2*1 tiles. So in total, there are 3 choices, 3 = 2 + 1 = f(2) + f(1).

Now consider n = 4. First, put a tile in the leftmost 2*1 rectangle, then for the left 2*3 rectangle, I have f(3) choices. Expand the leftmost 2*1 rectangle to the leftmost 2*2 rectangle. Still, to avoid duplicates, the 2*2 rectangle can only be tiled with two horizontal 2*1 tiles. For the left 2*2 rectangle, I have f(2) choices. Expand again the 2*2 rectangle to 2*3 rectangle. Though I have f(3) choices to tile this rectangle, each of them is identical to a way I put tiles before. So in total, f(4) = f(3) + f(2).

For n = 5, I still need to consider only two situations: when the leftmost rectangle is 2*1 and when the leftmost rectangle is 2*2. Then I get f(5) = f(4) + f(3).

But why is it true? I find out that when the leftmost rectangle is 2*2, the way I put two vertical tiles in it has occured in the previous step when the leftmost rectangle is 2*1. So I can only put two horizontal tiles in the 2*2 rectangle. When the leftmost rectangle is 2*3, all choices that I arrange tiles in it have occured in previous two steps. For rectangles of 2*4, 2*5,.., 2*(n-1), all choices that I arrange tiles in them have occured in the first two steps. So for any natural number n >=3, I just need to consider two situations: when the leftmost rectangle is 2*1, in which case the choices are f(n-1) and when the leftmost rectangle is 2*2, in which case the choices are f(n-2). So in total, f(n) = f(n-1) + f(n-2).

Problem solving episode---WalkTilings(1)

Here is the problem I am going to solve. It's called WalkTilings Problem.

Suppose you have tiles that are 1x2 rectangles, and you have to tile a walk that is 2x3 units long. You've got three choices: 3 vertical tiles, 1 vertical tile followed by two horizontal tiles, or two horizontal tiles followed by one vertical tiles.
How many choices do you have in tiling a 2x4 walk? How about a 2xn walk, where n is some natural number? Do you have a procedure that works for any n?

Here is the plan I want to work on.
Since it is hard to find out the solution when n is an abstract natural number at first, I will begin with the simplest condition(n = 1) and check several cases when n is small. I will investigate how the condition of n is related to the condition of n-1.

First, when n = 1, there is only one way to tile the walk.
When n = 2, there are two choices to tile the walk: 2 vertical tiles or 2 horizonal tiles.
When n = 3, there are three choices and they are presented in the problem.
When n = 4, there are 5 choices: 2 vertical tiles followed by 2 horizontal tiles, 4 vertical tiles, 1 vertical tile followed by 2 horizontal tiles and then followed by 1 vertical tile, 2 horizontal tiles followed by 2 vertical tiles, or 4 horizontal tiles.
When n = 5, there are 8 choices.

Proving the correctness of iteration and recursion

Basically, iteration and recursion are both loops. The difference is that recursion continues to call the function itself until it gets to a base case, while iteration has variables which change after each iteration.
Considering proofs of the correctness of iteration or recursion , I find out that it is easier to prove recursion by using complete induction. I assume P(1) and P(2) and ... and P(n-1) is true where n is a parameter about the function. Then I check that when the function calls itself, the parameter about the just called function is within the domain of (1, n-1) so that by assumption, the just called function returns the correct result.
As far as iteration is concerned, I need to have loop invariants which are true after each iteration. Loop invariants depends on the i-th iteration (i = 0, 1, 2,...), so the expression for loop invariants has parameter i. I need to prove the expression holds for every i using simple induction. Also, it's necessary to prove the iteration terminates. To prove that, I need to find an expression composed of loop invariants and prove it is a decreasing sequence so that the iteration terminates at last.

master theorem for divide and conquer

Mergesort is an example of divide-and-conquer strategy. Divide a problem into subproblems until getting to the smallest one (when there is one element in the array for mergesort) and then combine solutions of subproblems together.

The time complexity for divide-and-conquer problems is a little complicated and so is the proof of it. For example, in mergesort, T(n) = 1 if n = 1, and T(n) = T(ceiling of n/2) + T(floor of n/2) + dn if n > 1. Though the expression is long, it's based on the algorithm of mergesort and I find it easy to remember if understanding the algorithm.

To prove the time complexity of mergesort which is upper bounded by n*lgn, it is more difficult than proofs before in the course. Here, I need three steps. First, I need to find out the expression for T(n) when n = 2^k (k is a natural number) and using induction to prove it. Then I need to show that T(n) is monotonic (non-decreasing actually) also using induction. At last, I use the previous result to prove that T(n) < Xn*lgn. But at this point, another difficulty comes out. I have to figure out what X is. So I can make T(n) bigger to the expression in the form n *lgn times another coefficient, which is the X I want. After all that, I can say T(n) is upper bounded by n *lgn.

For time complexity of other divide-and-conquer problems, the steps are similar. The difference is that they are not necessarily divided into two parts, instead, to pieces of size n/b parts. There's really a lot of work, but generally, I need to remember three things:
1. Find out the expression for T(n) when n = b^k (k is a natural number)
2. Prove T(n) is monotonic.
3. Prove the time complexity using previous results.

unwind recursion formula

Though recursion formulas are defined based on previous ones, like Fibonacci numbers, F(n) = F(n-1) + F(n-2), for natural numbers n > 2, the formula can be expressed only depending on current variables, which is the closed form for F(n).
To get the closed form, we need to unwind the formula given recursively. What we do is use the formula continuously until we hit the base case, whose value is given explicitly. For example, in time complexity for binary search, T(n) = 3 for n = 1, and T(n) = 3 + T(n/2) for other natural numbers. We unwind T(n) until we get to T(1). So T(n) = 3 + T(n/2) = 3 + 3 + T(n/4) = ... = 3lgn + T(1) = 3lgn + 3. Thus, we get the closed form for time complexity of binary search.
A special case occurs in Fibonacci numbers. Each element of Fibonacci numbers seems like r^n. Because F(n) = F(n-1) + F(n-2), so r^2 = r^1 + r^0. we can get two roots r1, r2 from the equation and for any a, b, ar1 + br2 also satifies the equation. As F(n) = n for n < 2, ar1 + br2 = 0 and ar1 + br2 = 1. Then we get a and b. Thus, we get the closed form for F(n).

recursion at a glance

Recursion is something like you have established a foundation and other situations are built from it. For example, in Fibonacci numbers, F(n) = n for natural numbers n < 2, which serves as a foundation and for other natural numbers, F(n) = F(n-1) + F(n-2).
Recursion can be used to break large and complex problems step by step to the smallest ones. As in binary search in a sorted array, the problem is broken down by half each time until you only have two elements to compare at last. And in mergesort, the idea is to divide the array into two parts from the middle, and then again divide each part from the middle. You keep dividing parts into two until you get an array of size one, which you don't need to sort further, but instead, you just return the element. Then you combine the sorted left and right parts into one sorted part and at last, you end up having the whole array sorted.

two weeks gone and still in induction

The big part of induction has been taught and by now, I can use the three principles to prove problems. This week, we look more carefully at the induction. We noticed that the base case can be larger than zero and we found out pitfals in induction proofs written by others. So I become more careful and consider various conditions when I write proofs.

at the beginning of csc236

I've been dealing with well-ording, simple induction and complete induction for about two weeks and studying to prove statements with these principles. It seems not hard in lectures and problem sets, but for assignments... it does take some time and efforts.
Some problems are hard to prove, such as the one about postage using unlimited 4-cents and 5-cents stamps. It uses complete induction with cases to consider. Most problems are practical, but not mathematical. I'm not quite good at practical issues, but I'm trying to think them in an abstract way.
So for now, everything's fine and I'll keep going.