Problem solving

For this problem solving blog entry I have chosen to look back on how I solved the first question to my term test #2.

---------------------------------------------------------------------------------------------

The question was: Use any techniques you like to guess a closed form for T(n). State your guess, and prove it correct.

VnEN T(n) = { 1, if n = 0
2T(n-1), if n > 0

------------------------------------------------------------------------------------------------

First thing was understanding the problem, I read the instructions and twaht the problem asked me to do and I looked at what I was given and tried to formulate some scrap work to try and make a proof. The important data was where the question stated the T(n) function, and this is mostly what you would work with. We know that n is a natural number so n >= 0, and we know T(n) when n is >= 0. This data is sufficient to solve the problem because the function is defined for all intervals of n.

When first looking at this quesiton I had noticed that I had seen this type of question before. There was a similar example in the lecture notes that Prof. Heap had wrote up for us on the projector. I remembered that the example had to do with finding the closed form of a function and unwinding. So next I started to write down some rough notes and began to unwind the function. After unwinding it 3 times I recognized a pattern and used this to derive or guess a closed form. With a closed form I could show how the function would look after n iterations and using this information i could prove that the closed form is correct.

Unwinding the problem I derive:
T(n) = 2T(n-1) (given)
= 2(2T(n-2)) = 4T(n-2) = 2^2T(n-2) (given, unwinding)
= 4(2T(n-3)) = 8T(n-3) = 2^3T(n-3) (given, unwinding)
= 2^nT(n-n) (derived closed form)
= 2^n

P(n): T(n) = 2^n, VnEN

Base Case: n = 0: 2^n = 2^0 = 1 = T(0)
So P(0) is true.

Induction Step: Assume nEN, and P(n) is true.
Then T(n+1) = 2T((n+1) - 1)
= 2T(n)
= 2(2n)
= 2^n+1
Therefore T(n) => T(n+1), VnEN.

You can chekc this result with the function you are given, and see that since using the give data I can find a value that corresponds with my closed form thus this answer must be correct. I don't see another way to go about solving this problem but it looks to me that using unwinding and finding a close form is a very simple way to solve this problem. Induction will probabaly be used to prove this problem regardless of how you guessed the closed form. The steps taken to prove this problem can be used to solve different problems that are similar. As noted above this problem was similar to an example given in class, so the foresight in solving this problem can be used to help solve other similar problems.

Assignment 3

Assignment 3 is all about regular expressions, and the material does not seem to be too difficult. I have started working on #2 and #3 and have outlined a layout to prove them. Regular expressions are pretty easy to understand, the only thing that was remotely difficult was understanding the kleene star. Once I understood that, most of the material was straight forward. Then we started to learn FSA's which were quite interesting. Every regular expression can be expressed by an FSA, and we learned how to create FSA's that expressed certain regular expressions. The hardest part about this was probably converting an FSA into a DFSA, because there were a lot of new concepts like delta and merging states. My understanding of how to crop out a state and replace it with a regular expression didn't take long though as this was quite straight forward.
The new material was not very difficult and quite easy to understand. I think I will do ok on the assignment 3 and term test 3 and hopefully go into the final exam with some breathing room.

Second term test is done now along with weeks of ongoing assignments. Hopefully the workload will get a bit better for us now that we're nearing the final stretch. The term test was not too difficult and I think i did quite well. The first two questions, finding a closed form and recursion, were pretty straight forward and did not take me long to finish them. The third question we were given a while loop and had to find the invariants and post conditions, and also had to prove termination. I traced the loop out and managed to solve for m when the loop terminated. I spent quite a bit of time thinking about the invariant, but it managed to elude me until near the end of the test, but there was not enough to formulate the full proof by that time.

Getting the test over with, I can see the following weeks being a little less demanding in terms of tests and work load. Maybe we can get some free time in for ourselves and relax a little bit before the final assignments and exams.