For this assignment, I felt that question 1 and 2 were the challenging one. It may also be because I didn't start the assignment early enough, so I didn't grasp many ideas.
Question 1 was more difficult because I was struggled to find such formula. After I went to the office hour, I found my way of thinking is quite inefficient espeacially if n > 4. Danny told me the quicker way, which somehow I didn't catch on it while reading the bulletin board. This way he told me makes sense and less headache. But when I have to translate it to the formula, I was struck once again. It took me awhile to recognize the patterns. So, I think I got the idea (and the formula) but because the time is running out I didn't complete this question.
To add to that, I asked my brother to help me find the formula. And he gave me the formula (3n)!/(n!)(2n+1)! which outputs the correct value! (He got it from this page.) It was useful for checking whether I was getting the right number. It's also short and simple.
Question 2 was not as hard as question 1 in a sense that we just need to prove that closed form we got. Some suggested using the monoticity argument which the length of work is a lot. (But I did it this way since I can't come up with another way.) There is a shorter way which deal with property of integer and stuffs like that but I have no clue of how to do that. I would say that the hard part was to prove that T(n) = clog7n.
Question 3 and 4 weren't as time consuming as the first two questions. Question 3 was straightforward in what it wanted us to do. It was interesting to think that grasshopper can make either 1 step or 3 steps. Question 4 was similar to the example we did in class, so it was not too difficult to do. I didn't do the bonus part which the question itself reminds me of csc165's material.
Overall, the assignment was challenging for the first two questions but it also had the other two questions to make it enjoyable.
No comments:
Post a Comment