Assignment 2

Well yet another assignment done and one more to go! I must say that this assignment was a bigger challenge than the first (as expected). I am glad that question one from assignment 1 was pushed back. My partner and I had figured out the number of nodes a while back (in the time of assignment 1 before Danny announced the extension) but we had struggled for a while on how to prove it. I think the first challenge for most after looking at the responses on the bulletin board, the struggle people had to get a formula that is suitable for the nodes. But the tough part of this question would definitely be the proving. When I had a formula, I wasn't sure how I can put into words in a proof so I decided to do something I was a bit more comfortable for me. I wrote a python code for a ternary tree of n nodes. It made me visualize and assess the problem much easier. For any n, I was able to trace my code going through it recursively and making sure that it made sense for proving purposes. We used the proving of the "precondition implies postcondition" method that we learnt recently in class. In doing this, it gave us a better understanding of how to prove preconditions. Although we had a good format down since we had done writing out question 4 first.

For question 2, we had thought we got the proof easy but then we had a discussion about what the constant should be for the time complexity. We were looking at the course slides for week 4 (I think) for the recursive functions on time complexity. On the day slides, the time complexity had 4 + T(ceiling(n/2)) but then for the exact same question in the evening lecture slide they had 3 + T(ceiling(n/2)). This made my partner and I confused. Until we realized that the constant didn't really matter after reading a post done on the bulletin board. The only condition was the constant be not zero because the algorithm would fail. Other than that part, we found the rest of the problem easy.

Now as for question 3, We basically wrote a bunch of scratch work until we saw an algorithm but could'nt figure it out until we unwound it and found the connection. Then it was finally easy to put into words (well sort of).

I can't complain about the assignment, it was tough but with enough time, you can pull it off with no problems.