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.

Rough week gone by, so many assignments due in this one week. Finishing problem set #5 was straight forward, but going into the weekend A2 would give me and my partner quite a bit of trouble. Questions 2, 3 and 4 were fairly straight forward and didn't take too much time to tackle them.

Question 1 was another story, we spent most of our time on the ternary tree question as we couldn't find a suitable pattern or closed form to describe the relationship between the number of nodes and the number of non equivalent ternary trees. We had gone through many ways of counting the number of ternary trees including the grueling task of drawing out all of the possible ternary trees for nodes 1 to 4 and still to no avail, we couldn't pin down a closed form. Many of our findings hinted to a possible closed form where some numbers were repeated from the previous number of nodes, but there always seemed to be some constant that would hang around and we couldn't find a pattern that would derive these.

To solve this seemingly impossible question we took advantage of Danny's office hours and we asked him how we should go about finding the closed form. After showing him our pages of rough work he worked with us and helped us find a way to count the trees by grouping all the ternary trees the right side of the tree could make with the left side having 0 nodes, then having 1 node, and so on. This was really helpful and we returned home to take another crack at the question. We had it pretty much figured out but the deadline drew near and we were not able to piece together a full solution before handing it in. We managed to summarize how we would go about proving the formula but hopefully next time we won't get such a tough question.

Test #2 is next, lets hope for the best, good luck.

The midterm was returned to us last week and I was surprised to see I did a lot better than I thought. This was a relief but there are still two more term tests and assignments that can potentially bring my mark down. Hopefully the material doesn't get too hard as the course goes on.

I've began working on Assignment 2, the first two questions look pretty straight forward and I should be able to finish them before the weekend. Problem Set 4 came out a little late but the due date was extended. I am still going to try to finish it by Thursday night because I can't get to school in time for the early class and I would have to ask someone to hand it in for me. I still think people in the Thursday class get a disadvantage because they do not get a lecture that usually explains the concepts that are used to solve the week's problem set until after it is due. I think that we should be able to at least hand in the problem set after the first hour of class because in some cases that hour of lecture really helps with the problem set and some people just can't make it to the earlier class the next day. Maybe even let us electronically send the problem sets like the assignments to you as long as it is before the 10am deadline on Friday. I guess i could also search for the early class lecture slides and look them over to get a better of idea of how to tackle the problem sets, but it would be nice to have the same benefits of the earlier class.


This next week is going to be very busy for many of us with a bunch of assignments due next week and ongoing midterms. Hopefully after this next week things will die down a bit and we can have a relaxing weekend after A2 is done.

Edit: Just checked the boards and Prof. Heap will be taking problem sets on Monday from 11-3pm. Thanks!

I managed to finish A1 and Problem set #2 over the weekend. Feels good to have them off my back. Problem set #2 was pretty straight forward, Prof Heap gave an example in one of the lectures that helped a lot. I had more trouble with A1 especially Q2 with the lunch menus. I couldn't find a pattern between the lunch menus, or i didn't try hard enough. Either way I spent most of my time staring at this question and trying to make a menu for n>3 items. I looked to a friend for help and he pointed me in the right direction, giving me insight on how he found the pattern. After that it took a few minutes to devise and prove a technique and then I was done. Now to study for the midterm and hope for the best, good luck everyone.

Midterm is over and it didn't seem too difficult. After I finished the first question(the easiest one in my opinion), I realized i had spent too much time on it and had to try and quickly solve the next two questions which proved to be more difficult.
Problem Set #2 came out but I haven't had time to start it yet because of other assignments that need my attention. My friends found it to be a strange question, so I better start on it soon. Assignment 2 also came out at possibly the worst timing possible. It also due two days before i have two midterms on the same day -.-;. I just hope it doesn't prove to be too difficult.