a2 and t2

So since my last post I've finished gone through two things.. T1 and A2.. now that I've got them marked, I'll talk my experience with them a bit.

Assignment #2

     First off I want to say that A2 was much easier than A1 for me. Maybe it's because there were examples to reference to for basically every problem on it. I manged to work out the Fibonacci sequence that showed up in the binary string pattern only Odd Maximal Contiguous Ones Free Strings. OMCOFS are basically binary strings that when seperated using 0 as delimiter, had even number of 1s in each section. What I did struggle with was explaining why the Fibbonacci was correct. I had the same problem in A1 in finding the one to one ration between two and three subsets. I wrote that given OMCOFS of length n, the number of them ending in 0, added to the number of OMCOFSs ending in 1 is equal to OMCOFSs of length n-1 and n-2. This was clearly true but did not support it for all OMCOFs of length n. I had to use this fact given in the solution... "An OMCOFS of length n that ends in 1 certainly can't end in 01, so these must end in 11. Thus, the OMCOFSs of length n that end in 1 are in 1-1 correspondence with the OMCOFSs of length n-2 (by appending or removing 11)."

Term Test # 2

     I was completely unsure of what parts I should be studying for during this test. I ended up working on unwinding, master theorem, and recurrences. Those weren't too difficult to study for as we have been doing exercises on those topics including assignment 2 as well. I didn't really have time to study proof of correctness, so I simply focused on the other topics. If last test was anything to go by, then the later topics such as proof of correctness, wouldn't be on the second term test... I was wrong, and I guess it was to be fair to the morning section who had later sections (structural induction) in T1. We we're asked to prove  that a given piece of code could take x and y and would return x^y. Having little understanding of how to prove things correct I blanked out skipped to the next section and finished the master theorem questions instead. After getting through the second easier question on T2 I finally went back to calm down and take some time to read over the code on question 1. I used complete induction, as the question told me to, and followed my instincts. I took everything that I knew the code would return as a fact I could use. Now this may seem obvious to anyone keeping up in class, but this was such a relief for me to figure out during the last 5 minuets of the test. I ended up doing pretty well, just loosing marks in forgetting to prove termination and quantifying the x value in the IH.

Assingment #3
    
       I'm looking forward to getting more practice with proofs of correctness with assignment 3. So far our intro to Formal Languages is looking very interesting. DFSAs(deterministic final state automata) look pretty enjoyable to figure out as well from our last tutorial.

Week #6

     So I got back two things today, my tutorial #2 quiz and midterm test.  I did decent on both except I'm disappointed that I'm still making errors when making my P(n): statement.. I keep saying for all or for any for some reason. I'm actually relieved I was given part marks for doing the outline of the proof on the last question of the midterm. It kept me from complaining about my small P(n): error.

     Anyways, turns out we're not doing a bunch of upper and lower bounding yet.  Tutorial had a few questions about just the lower bound and some mathematical induction on a recurrence. I actually spent a lot of time reading through the text pages to only answer the tutorial questions. The readings will probably help this week when we get into divide and conquer. It seems that this week we only just broke some larger proof about time complexity into parts in an attempt to practice different concepts individually.

My First Entry

     So I'm finally getting around to writing my first entry. I think my impression of the course so far has been great. Nearing the end of CSC165 as things got more and more difficult I've dreaded coming into 236. I'm honestly not a big fan of proving things. I can enjoy and appreciate a good proof but I usually take forever to get through them. My method was usually looking through as many examples as possible until nothing would surprise me. Maybe taking more time to prove things without answers may be more effective.

A1:
    My first major difficulty was on  number 3 in assignment 1. I saw the relationship between between the number of 3-subsets for n-elements then for n+1 elements but I couldn't make the jump to relating it to the formula for the number of 2-subsets in n + 2 elements. I even drew out samples for my self to examine. Finally finishing your proof but finding out your obstacle was so small can be so bitter sweet.

Midterm:
    When the midterm neared I was a bit worried due to the few examples we had to work with regarding well-ordering and structural induction. I was surprised to see that we were given only 3 proofs that involved neither. The first questions regarding sums practically wrote itself and the second was similar enough to the ternary tree question on assignment 1. Unfortunately I ran out of time to finish the last question which was about Fibonacci numbers, I'll have to mess around with those some more to be quicker.

What now:
     Well right after our midterm we had an hour of lecture on time complexity, big O, etc. I'd  say it's been our most confusing lecture yet. It's been about a year since I last did time complexity so I'll have to do some serious reviewing the 165 notes this week.