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.
Sunday, November 23, 2008
Regular Expressions and D(/N)FSAs
Over the past several weeks as we started learning about regular expressions, what seemed vague and unfamiliar quickly became the opposite. The assignments and examples presented in class was very helpful in allowing me to fully understand how regular expressions are formed and how to prove various statements with them.
So, DFSAs is when the input specifically determines the next state of automation. NFSAs, however, may have more than one state in which it can go to next. It also includes the empty-state-transitions. Input symbols are not necessarily read in this case. I still feel a little unsure about this topic because the examples in both the course notes and in lecture seem to be specific to certain cases. I"ll have to study it in more detail before exams. I just recently realized that there were problems at the end of each chapter in the coursebook. This would be helpful in studying for all the topics taught so far. I think I'll try that out!
As the end of the term is fast approaching, I have been looking into the mathematical problem we need to have completed here. I'll be looking into the sites suggested for structure and ideas.
So, DFSAs is when the input specifically determines the next state of automation. NFSAs, however, may have more than one state in which it can go to next. It also includes the empty-state-transitions. Input symbols are not necessarily read in this case. I still feel a little unsure about this topic because the examples in both the course notes and in lecture seem to be specific to certain cases. I"ll have to study it in more detail before exams. I just recently realized that there were problems at the end of each chapter in the coursebook. This would be helpful in studying for all the topics taught so far. I think I'll try that out!
As the end of the term is fast approaching, I have been looking into the mathematical problem we need to have completed here. I'll be looking into the sites suggested for structure and ideas.
Thursday, November 13, 2008
Regular Expressions
Learning about regular expressions is a nice change of pace from the proofs we were doing earlier on. I find it easier to think about and be able to manipulate in my head versus induction proofs where there are times i'm not entirely sure where the proof is going until the very end.
As the lectures run on, it is getting slightly more complicated as aspects of proofs are being introduced. I'm not fully understanding the DFSA diagrams, particularly accepting states but will look into it in the coursebook. I'm assuming that accepting states are when after an input string is being processed, it ends at a state with two circles. Then that leads me to the question, isn't it always possible to create a diagram given the string you want to process in mind? I suppose the diagram is always created before experimenting with the strings.
We've skipped a lot of material in the coursebook, though a lot of which have been covered in CSC165. I'm wondering if we'll be going back to it at some point, despite only having a few weeks left before exams begin. Our final assignment has been released and these upcoming weeks are going to be a little hectic, so I hope it isn't too bad.
As the lectures run on, it is getting slightly more complicated as aspects of proofs are being introduced. I'm not fully understanding the DFSA diagrams, particularly accepting states but will look into it in the coursebook. I'm assuming that accepting states are when after an input string is being processed, it ends at a state with two circles. Then that leads me to the question, isn't it always possible to create a diagram given the string you want to process in mind? I suppose the diagram is always created before experimenting with the strings.
We've skipped a lot of material in the coursebook, though a lot of which have been covered in CSC165. I'm wondering if we'll be going back to it at some point, despite only having a few weeks left before exams begin. Our final assignment has been released and these upcoming weeks are going to be a little hectic, so I hope it isn't too bad.
Tuesday, November 4, 2008
Getting ready for test #2!
The second term test is a few days away and I think that it might be a good idea to start doing some practice problems. I believe that the test will cover all the material from Week 6 onwards, though everything seems to be cumulative so that probably means everything in the course up to what we're learning now.
The main topics I need to focus on are on proving recursive functions with induction, structural induction and iterative correctness. There has been a tremendous amount of other work over the past week, so I haven't been able to spend as much time on this material but over the next few days, hopefully, I'll have nailed the concepts down.
The main topics I need to focus on are on proving recursive functions with induction, structural induction and iterative correctness. There has been a tremendous amount of other work over the past week, so I haven't been able to spend as much time on this material but over the next few days, hopefully, I'll have nailed the concepts down.
Tuesday, October 28, 2008
Assignment Two
Assignment two took a lot longer than I had anticipated. Thinking that the assignment was due at 10am Monday morning, one of my group partners and I spent most of the weekend going over the questions, breaking it down, analyzing it and then finally coming to a conclusion and selecting an appropriate type of proof method to use. From the first assignment, I've learned that though we are no longer required to write up a formal proof, it is still necessary to include most of the proof structure and details which is where we lost the most marks.
In my opinion, the first and last questions where the most difficult. The ternary tree required some time to determing a recursive pattern which did not end up being as complex as it seemed at first. After realizing the pattern, it was still difficult to explain it in a clear and concise manner. This is when my partner and I went through it step by step to seek the best way to approach the proof. We decicded structural induction fit the problem the best. The last question required code tracing in python. The square-root function threw me off a little at first as I didn't see what its purpose was which made me conclude that the program was not correct. Upon a closer analysis and the hints provided on the bulletin board, it then became clear that the program seemed correct.
Hopefully we did better on this assignment than we had done in the last!
In my opinion, the first and last questions where the most difficult. The ternary tree required some time to determing a recursive pattern which did not end up being as complex as it seemed at first. After realizing the pattern, it was still difficult to explain it in a clear and concise manner. This is when my partner and I went through it step by step to seek the best way to approach the proof. We decicded structural induction fit the problem the best. The last question required code tracing in python. The square-root function threw me off a little at first as I didn't see what its purpose was which made me conclude that the program was not correct. Upon a closer analysis and the hints provided on the bulletin board, it then became clear that the program seemed correct.
Hopefully we did better on this assignment than we had done in the last!
Monday, October 20, 2008
Guest Lecturer and Python
Today's lecture was particularly interesting and enjoyful, especially after a long night of assignments and studying. The guest lecturer, Nick, was quite entertaining to say the least. Though I would have liked more material to be covered over the course of the lecture, it was fun, overall. The concepts from today's lecture was easily grasped since many of us have programmed prior to taking the course and so learning about preconditions and postconditions wasn't something new though I never really knew that there was such thing as indicating a postcondition. Is this written in the code? Or is it just to give the programmer a way of assessing whether what they were trying to program was actually successful as accomplishing its task. Nick briefly spoke about crashing programs and how we would perhaps, get the chance to learn that at some point in our undergraduate years. That should be interesting! =)
On another note, Python. When I took CSC148, we were still learning Java so the conversion to Python in most of the lecture material is a lot more difficult. I just took a look at the newest problem set that's due on Monday, and it's all in Python! One of the questions in the assignment is also in Python. I'm going to have to spend a lot of time trying to understand what each command does. =( Hopefully, it won't be much too difficult but I really should get on those assignments. I can't believe there are so many assignments due at the same time from nearly every class!
On another note, Python. When I took CSC148, we were still learning Java so the conversion to Python in most of the lecture material is a lot more difficult. I just took a look at the newest problem set that's due on Monday, and it's all in Python! One of the questions in the assignment is also in Python. I'm going to have to spend a lot of time trying to understand what each command does. =( Hopefully, it won't be much too difficult but I really should get on those assignments. I can't believe there are so many assignments due at the same time from nearly every class!
Subscribe to:
Posts (Atom)