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.
Thursday, November 27, 2008
Monday, November 10, 2008
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).
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).
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.
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.
Sunday, November 9, 2008
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.
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.
Monday, October 20, 2008
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.
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.
Saturday, October 18, 2008
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).
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).
Subscribe to:
Posts (Atom)