Looking back now that classes are over, I feel like though the term seemed short, a lot was learned. As I begin to start preparing for exams, I fear that I will not be able to remember everything we have gone over seeing how it is the last exam of the week for me, after a series of 2 others, two days before it. As I can now compare this course to CSC165, I definitely enjoy this one more due to the structure of the proofs. It made things more understandable and less abstract. Though the feedback on the assignments were not as clear as I would have hoped, the posted solutions made more sense. I really enjoyed the course up to and including regular expressions where I slipped a little behind. Hopefully, I will be able to learn it all and achieve a better understanding of it all before the exam.
My plan to cover the material taught will be to work backwards from the most recent to the initial induction topics. Though many of the latter topics rely heavily on the earlier material, it will serve as a review for those topics as well. The most confusing sections for me remain to be DFSAs, Pushdown Automata and the Pumping Lemma. I'm still not quite sure exactly what it is that they do. What would be really helpful would be to see example problems on the later sections that weren't tested on, along with its solutions. It would help in exam preparations.
Overall, this course was very enjoyable! =) I hope that I will get the chance to be in Danny's class again for another course. Great teaching methods! Thanks!!
Friday, December 5, 2008
Monday, December 1, 2008
Problem-Solving Episode
By the polya method of problem solving.
Understanding the problem:
We want to find all of the possible routes to get from point A to point B, given an NxN grid (where N is any natural number) as shown below, by moving in some combination of right and upward steps.
1x1 grid........2x2 grid...............................3x3 grid
._ B ............... _ _ B ................................. _ _ _ B
|_| ...............|_|_| ................................|_|_|_|
A .................|_|_| ................................|_|_|_|
....................A .....................................|_|_|_|
............................................................A
Case 1: Grid 1x
By tracing all possible paths, we find that for a 1x1 grid, there are only 2 possible routes to get from A to B. (we need to keep in mind that order matters)
-> 1 step right then 1 step up
-> 1 step up then 1 step right
Case 2: Grid 2x2
By tracing all possible paths, we find that for a 2x2 grid, there are 6 possible routes to get from A to B.
-> 2 steps right, then 2 steps up
-> 2 steps up, then 2 steps right
-> 1 step right, 1 step up, 1 step right and then 1 step up
-> 1 step up, 1 step right, 1 step up and then 1 step right
-> 1 step right, 2 steps up and 1 step right
-> 1 step up, 2 steps right and then 1 step up
Since a grid consists of squares of equal length, a path can be devised by moving any multiple of right and upward steps. As shown above, we know that these conditions can be satisified given our data.
Devising a plan:
The connection between the data and the unknown includes the fact that the unknown is the combination of all allowable moves (right and upward steps). Since we are working with NxN grids, a technique of counting the number of paths can be as follows:
For NxN grids greater than 1.
We can generalize an idea of how to solve this problem by finding a pattern in the problem
and using it to create a generalized equation.
Two paths can be immediately determined.
-> Moving right N steps then upwards N steps.
-> Moving upwards N steps then right N steps.
For each column, we need to determine the number of paths to B. Starting with the right-most column (we would move N-1 steps right to get to that column), then proceed with the following pseudo-code procedure.
for (int i=1; i<=N; i++){
if (N = i){
move upwards N, then move right 1 step to B.
}
else {
move up i steps, right 1 step, then up N-i steps.
}
}
The same procedure follows for the other remaining columns in the grid, however, since we will be dealing with an increasing number of columns up to N, we will be required to move through each column which has already been approached from other starting points. This results in an N! (factorial) ways of getting to B from a certain column.
Another way to look at the problem is to determine the number of ways to get from A to B by counting the total of ways using all possible right moves and adding them to all possible upward moves, which results in 2N! ways of arranging all possible paths from A to B. However, we can only move right and upwards, which limits us to the factorial of all possible right moves and the factorial of all possible upward moves. We can use the multinomial theorem to construct a solution to this problem as it considers all possible moves while grouping all similar moves together.
Carrying out the plan:
P(n): For an n by n grid, there are exactly 2n!/(n!n!) paths from A (lower left corner of the grid) to B (upper right corner of the grid)
Claim: For all natural numbers n, P(n) holds.
Base Case: For n = 1
We know from counting the number of paths from above, that there are 2 paths.
P(1) = [2(1)]!/(1!*1!)
= 2/1
= 2
Therefore, for n = 1, P(n) is true.
Simple Induction:
Assume that for any arbitrary natural number n, P(n) holds. We will now prove that this is true for grids of size (n+1) by (n+1).
P(n+1) = 2n!/(n!*n!) + 2n!/(n!*n!) by IH
= (2n!*n!)/(n!*n!*n!*n!)
= (2(n+1)!)/((n+1)!(n+1)!)
Therefore, true for P(n+1).
Conclusion: For all natural numbers n, P(n) holds true.
Looking Back:
The result from this proof can be validated by tracing and counting the number of paths from point A to B by drawing the grid. Now that we understand the logic behind the solution, we can verify that this is indeed one solution to the problem. There are many ways of obtaining the solution to this problem. At a glance, we can use the multinomial theorem as we did in this proof or we can use combinations. Combinations are used to determine an unordered arrangement of r items selected from n distinct items.
Its equation is n!/(r!*(n-r)!) This equation is identical to ours since we are seeking paths for perfect squared grids, our values for r and (n-r) will be the same. This results in our obtained equation. The n would be the maximum number of steps it can make to the right plus the maximum number of steps it can make upwards on one row. (ie: the n in the n by n grid itself). The r can be the number of steps it can make to the right or upwards. In our case, both numbers are equal.
This method can be applied wherever the multinomial or combinations are used. Combinations are very commonly used to make unordered arrangements. We can also group similar items together while keeping its uniqueness individually. The result from this can be applied to many strategic games and problem solving activities.
Understanding the problem:
We want to find all of the possible routes to get from point A to point B, given an NxN grid (where N is any natural number) as shown below, by moving in some combination of right and upward steps.
1x1 grid........2x2 grid...............................3x3 grid
._ B ............... _ _ B ................................. _ _ _ B
|_| ...............|_|_| ................................|_|_|_|
A .................|_|_| ................................|_|_|_|
....................A .....................................|_|_|_|
............................................................A
Case 1: Grid 1x
By tracing all possible paths, we find that for a 1x1 grid, there are only 2 possible routes to get from A to B. (we need to keep in mind that order matters)
-> 1 step right then 1 step up
-> 1 step up then 1 step right
Case 2: Grid 2x2
By tracing all possible paths, we find that for a 2x2 grid, there are 6 possible routes to get from A to B.
-> 2 steps right, then 2 steps up
-> 2 steps up, then 2 steps right
-> 1 step right, 1 step up, 1 step right and then 1 step up
-> 1 step up, 1 step right, 1 step up and then 1 step right
-> 1 step right, 2 steps up and 1 step right
-> 1 step up, 2 steps right and then 1 step up
Since a grid consists of squares of equal length, a path can be devised by moving any multiple of right and upward steps. As shown above, we know that these conditions can be satisified given our data.
Devising a plan:
The connection between the data and the unknown includes the fact that the unknown is the combination of all allowable moves (right and upward steps). Since we are working with NxN grids, a technique of counting the number of paths can be as follows:
For NxN grids greater than 1.
We can generalize an idea of how to solve this problem by finding a pattern in the problem
and using it to create a generalized equation.
Two paths can be immediately determined.
-> Moving right N steps then upwards N steps.
-> Moving upwards N steps then right N steps.
For each column, we need to determine the number of paths to B. Starting with the right-most column (we would move N-1 steps right to get to that column), then proceed with the following pseudo-code procedure.
for (int i=1; i<=N; i++){
if (N = i){
move upwards N, then move right 1 step to B.
}
else {
move up i steps, right 1 step, then up N-i steps.
}
}
The same procedure follows for the other remaining columns in the grid, however, since we will be dealing with an increasing number of columns up to N, we will be required to move through each column which has already been approached from other starting points. This results in an N! (factorial) ways of getting to B from a certain column.
Another way to look at the problem is to determine the number of ways to get from A to B by counting the total of ways using all possible right moves and adding them to all possible upward moves, which results in 2N! ways of arranging all possible paths from A to B. However, we can only move right and upwards, which limits us to the factorial of all possible right moves and the factorial of all possible upward moves. We can use the multinomial theorem to construct a solution to this problem as it considers all possible moves while grouping all similar moves together.
Carrying out the plan:
P(n): For an n by n grid, there are exactly 2n!/(n!n!) paths from A (lower left corner of the grid) to B (upper right corner of the grid)
Claim: For all natural numbers n, P(n) holds.
Base Case: For n = 1
We know from counting the number of paths from above, that there are 2 paths.
P(1) = [2(1)]!/(1!*1!)
= 2/1
= 2
Therefore, for n = 1, P(n) is true.
Simple Induction:
Assume that for any arbitrary natural number n, P(n) holds. We will now prove that this is true for grids of size (n+1) by (n+1).
P(n+1) = 2n!/(n!*n!) + 2n!/(n!*n!) by IH
= (2n!*n!)/(n!*n!*n!*n!)
= (2(n+1)!)/((n+1)!(n+1)!)
Therefore, true for P(n+1).
Conclusion: For all natural numbers n, P(n) holds true.
Looking Back:
The result from this proof can be validated by tracing and counting the number of paths from point A to B by drawing the grid. Now that we understand the logic behind the solution, we can verify that this is indeed one solution to the problem. There are many ways of obtaining the solution to this problem. At a glance, we can use the multinomial theorem as we did in this proof or we can use combinations. Combinations are used to determine an unordered arrangement of r items selected from n distinct items.
Its equation is n!/(r!*(n-r)!) This equation is identical to ours since we are seeking paths for perfect squared grids, our values for r and (n-r) will be the same. This results in our obtained equation. The n would be the maximum number of steps it can make to the right plus the maximum number of steps it can make upwards on one row. (ie: the n in the n by n grid itself). The r can be the number of steps it can make to the right or upwards. In our case, both numbers are equal.
This method can be applied wherever the multinomial or combinations are used. Combinations are very commonly used to make unordered arrangements. We can also group similar items together while keeping its uniqueness individually. The result from this can be applied to many strategic games and problem solving activities.
Subscribe to:
Posts (Atom)