Adding Same Functions

 I have identified what caused me to be off by 1 in my answer for the third question on the first test, though I do not know how to remedy it. I'm confused about how to add two of the same function together.

I'm doing the second assignment right now and I'm trying to finalize my closed form for question one. I'm using the third tutorial #3 solution as a guide.

The final line of the solution states -

[F(n + 1) - 1] + F(n)G(1) + F(n - 1)G(n - n)

As I understand, according to the recurrence, this will be -

[F(n + 1) - 1] + F(n)(1) + F(n - 1)G(0)

= [F(n + 1) - 1] + F(n)(1) + F(n - 1)(1) 

= F(n + 1) - 1 + F(n) + F(n - 1)

The final closed form provided is -

2F(n + 1) - 1

I'm not sure how this happens? I previously thought that you just added the elements within the brackets for every F() together (like in this case, n +1 + n + n -1), but that obviously isn't right because I struggled with this very issue on test 1 and forgot to ask about it in office hours. I'm having a hard time finding answers to this online, as well. Most searches for adding functions either give me results for adding heterogeneous functions (ie (f + g)(x) variety), or they apply to functions in specific programming languages.

I'm going to try to look back on old slides and the course notes to see what I'm doing wrong. The logic is probably very simple and I feel foolish for not being able to figure it out right now.


Edit: I have found the closed form for question one of the assignment, just be looking at different results for values of n, but I still don't understand how adding the two functions together resulted in that answer. :(

Edit 2: I know the answer now! It had to do with the induction hypothesis!

100% on Assignment 1 - I'm thrilled. :)

This week is going to be interesting - I haven't started the assignment yet (though I have read it over and understand what is expected of us, and have a general idea of how to accomplish that), and I had a very hard time concentrating during last week's lecture (I had barely slept Wednesday night, thanks CSC207!) and as a result I barely absorbed anything about the closest point pairs problem, so I'll have to go to office hours to clarify points regarding both of those things.

For the closest point pairs problem, I have read the section on divide-and-conquer algorithms in the course notes, and I understand how it applies in the other instances where we have used it, but once we start getting into the dividing lines and the fact that the "rectangle can contain at most six points with pairwise distances at most d_Rmin" (Wikipedia), I get confused.

I'll write more tomorrow once I've gone to office hours tomorrow - right now, I don't even know how to explain why I'm confused about some of the things I'm confused about.

Thoughts on Test 1

When we got our tests back at the end of Thursday's lecture, I saw a lot of disappointed faces. Many students were expecting a much better mark than the one they received. A common complaint was that although their logic was solid and they understand the question perfectly, they were still docked one or two marks per question - and with a test out of 15, every mark taken off is about a 6% hit.

I got exactly the mark I was expecting - I messed up on the base case and a bit of the mathematical manipulation on the last question so I was expecting a significant loss for that, and I knew I had probably made some minor error in the previous questions. I didn't lose significant marks for structure, however, which was actually where many of my peers had faltered.

I was particularly careful on structuring the proofs properly, which included writing out the base case first, noting when I've used the IH, writing out the predicate, completing the proof with incremental conclusions (writing on one line, P(n) => P(n+1), and then on the next line, P(0) ^ P(n) => P(n+1), etc.), and writing the "Assume.." line out carefully. I pay attention to the form of the proof on tests because it really helps me organize my thoughts to have the logic carefully laid out on the page in a certain way - otherwise I can get confused. I'm really glad I've gotten into the habit of structuring everything carefully because it really saved me this time. I've also had friends who struggled with the course in previous years who mentioned that most of their  marks came from writing out the format properly, even when they weren't sure what the mathematical reasoning of the problem was supposed to be.

I think it would have been very helpful if we had had Assignment 1 returned a few days before the test - I think it is likely we will find that errors made in our assignments echoed in our tests. Because we hadn't been marked on anything prior to the midterm but a few very short quizzes, we couldn't have known what formal mistakes we had been making. For a lot of students, this could mean that they will have poor marks on two major components of the course, which really could have been prevented.

Bounds

I was feeling confident after the evening test. I felt like I understood the questions immediately and knew what methods I needed to avail of to solve them (of course, I have yet to find out whether my intuition was correct, the marks haven't been posted yet). I foolishly stumbled on the base case for the third question and by the time I knew what I had done wrong, it was too late to fix it, but I feel that overall it went well.

It would only be appropriate, then, that my heart would sink immediately as the professor started lecturing - lower bounds were definitely my downfall in CSC165. The reasoning for calculating lower bounds that my TA introduced in that course was completely different from the one that I later learned our professor was expecting from us (once the answers for the exercises were released). The answers involved capital-sigma notation, which I now have some facility with in this course when it comes to the mathematical proofs we did, but I still don't completely understand when to use it when applied to loops.

Now, looking at the binary search slides from last Thursdays lecture, I can honestly say I have no idea what is going on. I like how it says "trouble!" under the first upper bound slide, as if I hadn't been panicking for the entire lecture before that slide. I understand that we're supposed to be counting each step, and then repeating it for whatever number n times the loop goes around, and we incorporate recursion via the 'unwinding' method (which I understand in a general sense), but once I get to the later slides with all the gnarly mathematical proof work, I'm completely lost. I'll have to go to office hours tomorrow because I don't know how to do the tutorial hand-out at all.

Switching Between Simple and Complete Induction

It’s been about a month since the start of CSC236 and I can honestly say it’s gone by a lot more smoothly for me than the first month of CSC165. I struggled with the equivalences portion of the assignments in the previous course, as well as on the test, which I did very poorly on. However, once we began the actual mathematical proofs in CSC165 I greatly improved, and since the material right now in CSC236 is building on that section of the previous course, I’m finding that I understand the concepts more readily and I can apply them with greater ease.

That said - I ran into some trouble this week with complete induction, specifically the stamp combination problem. When Professor Heap asked us in class whether we felt confident in utilizing both simple and complete induction, I raised my hand for both. Later in tutorial I realized I wasn't completely correct. 

I had worked my way through the mathematical induction solution for it the other week and felt that with simple induction, the solution was very intuitive. However, when it came to reorganizing the problem into complete induction on the quiz, I found myself constantly reverting to the simple induction method. When the handout was first posted, I recognized the question and thought that I wouldn't have to write it out with complete induction because I understood the initial solution so well that just listening to the TA's solution would be enough for me to grasp the complete solution. I was very wrong. For questions involving trees, I can very easy visualize the problem and apply complete induction to solve it, but with the stamp problem it was different. My TA had gone over the solution for the stamp problem very briefly and I wasn't sure how detailed my answer on the quiz was supposed to have been (and, of course, as I'm writing this entry, the Tutorial 2 solutions PDF from the course website repeatedly refuse to load). I had no problem establishing the base cases. I understood that the formula for any amount n was the combination for the amount (n - 3), plus another three, but when it came to actually elaborating on the reasoning behind that formula on the quiz, I found myself struggling. My mind kept jumping back to the more intuitive-for-me logic of the simple induction solution. So, even though simple induction and complete are equivalent theoretically, diverting my mind from one to the other proved difficult, at least with this problem. I haven't really had trouble with complete induction on any other questions, so I'm hoping that it was just my having cemented the earlier solution to the stamp problem to memory that caused my confusion.

I'm definitely going to go over some more complete induction examples before the test and try them out on my own - I'm not as confident with it as I thought I was. I might try to go over question 4 from the assignment again, which gave us the option of using either simple or complete induction. I handed in the assignment using simple induction on that question, but I'll give it a try with complete and see if I have any issues.

The SLOGdriver's Waltz

Real thoughts and feelings to come!

But for now!