Worst Case Proofs for Bounding a Sort

    This week's classes have been primarily focused on bounding worst case scenarios of a sort function. The concept of this comes quite easily to me, however the initial stages of upper and lower bound proofs have only proven my need for practice with these sorts of problems (no pun intended). This being said, after visiting Prof. Heap's rather busy office hours, my understanding of how the initial expressions seen in each proof relate to the code we were shown (slide "bounding a sort") was greatly strengthened. From the aforementioned step onward, the proofs make quite a lot of sense and are exceptionally easy for me. I believe I simply need to review my notes once more in order to grasp this fully. I am also reading other student's SLOG's but I have yet to find one that seems to express similar feelings as mine toward this concept or help to assist my learning. It seems that many student's SLOG's are incomplete.

    The tutorial this week was also enjoyable and my quiz went exceptionally well (I think). I feel quite rewarded by my studying to make up for my beyond poor performance on last week's quiz. I must say, however, that the tutorial this week was almost identical to last week's. Not that this is a bad thing, I certainly needed the review, but I feel that I could definitely benefit from a tutorial on bounding a sort. Perhaps this is next week's tutorial topic.

    I have also completed Assignment #2, correcting some of my mistakes that I made last week on which to prove or disprove. The epsilon delta style proofs of the floor functions were honestly the high point of my week (academically), much fun was had with these and I may post more details on my proof style once past the due date.

More on Proofs and Intro to the Big O

    This week in class we wrapped up our discussions on proofs, finishing with a slide on allowed inferences. Nothing too challenging, this covered some of the more obvious inferences we may make in our proofs, however it was certainly worth going over.  On Wednesday, Prof. Heap introduced the somewhat perplexing concept of sorting and the big O. The idea of counting steps and comparing functions based on their rates of change is not exceptionally difficult for me, though I do fear this will become much harder.

    Unfortunately, I believe that I performed quite poorly on this week's quiz in tutorial. The proof we were asked to do was not that difficult but I erased my first answer thinking I got it wrong. At this point I realized that I was initially correct but did not have enough time to re-write my original solution. This was incredibly disappointing to me but I will try not to worry too much about a quiz worth only around 1% of my final mark.

    This week I have also began work on Assignment #2. So far, I have only decided which statements I will need to prove and disprove and brainstormed some ideas on how to go about doing this. Claims 1.2 and 1.3, being close to the form of the epsilon-delta definition of a limit, were quite interesting for me to think about. As I mentioned in an earlier post, my newly acquired knowledge from MAT137 on this type of proof has helped me approach these claims with much confidence, allowing me to see the fun in proving or disproving. I predict that I will have minimal difficulty with the creative aspects of these proofs, being only annoyed with the tedium of their structures.

Week 6

    This week's course content was less than normal due to Thanksgiving on Monday, but the two lectures I did attend were not incredibly challenging for me. This being said, confidence with proofs is somewhat lacking, I infrequently get to that "lightbulb" moment I desperately crave. So, my goal for the coming weeks is to practice writing proofs with the correct structure, and to read over the course notes in order to become more confident with proofs. Today we continued our discussion on basic proofs and Prof. Heap presented a simple epsilon delta proof. This was especially easy for me as I am taking MAT137 and we have already covered epsilon delta proofs.

    On Wednesday I received my marked term test and found that I did quite well. The only question I lost marks on was the last, asking us to give examples of sets that satisfied one condition and not the other. I think I could have completed this correctly had I had more time, but I'm not overly concerned about these lost marks. I think my study strategies have been successful and I'm quite pleased with the results.

Unit Test and Proofs

    This week's course content hasn't been exceptionally challenging for me. The continuation of our learning about proofs seems to make sense, and I look forward to working on the proof by contradiction shown in lecture on Friday (For all elements of the natural numbers n, a prime number exists which is greater than n). Although, the most challenging and important event to me this week was the unit test on Wednesday. I feel like it was exceptionally fair, full of types of questions we have seen in lectures and in tutorials before and it certainly helped to ease some of my worries of exceptionally hard tests and exams with this course. This is not to say that the test was incredibly easy, both question 1 part b and the final question were quite challenging. This being said, I feel like any questions that I did not receive full marks on were completely due to silly mistakes or slight mix-ups on my end, especially with question 1. Overall, I am fairly confident that I did reasonably well.

Week 4

    The course content for this week was not exceptionally challenging for me, though I find the form of proofs slightly annoying. It seems that just as I became sick of proofs in MAT137, we started on them in CSC165, however I am fully aware of the necessity of my understanding of this. I am currently only really annoyed with the tutorial exercises that have been posted, for both exercises everything seems to make sense until the middle.

Example: The proof structure is required for the following statement.

    For all X in the set of integers, for all Y in the set of integers. If X >= Y, then there exists Z in the set of integers where X <= Z <= Y.

(Ignoring most comments in this structure for now.)

    Assume X is a typical integer
        Assume Y is a typical integer
            Assume X <= Y
                Then R
                    .
                    .
                    .
                 Assume there exists Z in the set of integers                                 # This step and
                 Then there exists Z in the set of integers where X <= Z <= Y          # this step are
                                                                                                                  # confusing me
            Then X <= Y implies that there exists Z in the set of integers where X <= Z <= Y
        Then for all Y, If X <= Y, then there exists Z in the set of integers where X <= Z <= Y
    Then for all X, for all Y, If X <= Y, then there exists Z in the set of integers where X <= Z <= Y


    I plan to ask many questions in tutorial on Tuesday as I must prioritize with my studying. I'm getting the impression that the majority of Wednesday's test will be on logical notation so this is will be my primary focus.