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.

Course Content for This Week

    This week's course content has been somewhat fascinating, however, some aspects are still quite tedious to me. My applied study strategies from last week have been quite effective in allowing me to see the fun in each logic problem. Questions involving switching from English to symbolic form and back are certainly some of my favorites. In addition, I have been completing the answers for Assignment 1 with much ease. The tedium occurs in my slight difficulty with the logic laws such as communicative, associative, and distributive laws. This is not due to my inability to see each pattern and why each rule works, it is simply because of the way I look at each statement. I believe that I could figure out each identity on the go without needing to memorize the patterns. I am far more interested in knowing why things work than memorizing patterns and types of questions. However, it may be the unfortunate case that I must memorize these in order to save time and brain power on tests and exams. Only future quizzes and tests will be indicators of this.

Streetcar Drama Solution Attempt

Streetcar Drama (from lecture slides) Solution Attempt

I approached this problem by first assuming that person B has 3 children, all older than 1, with each age a positive integer and one eldest, so I need to find 3 integers. The product of all ages is equal to 36 and I set the sum of all ages equal to the variable y. I then set the age of Child 1 to the variable a, the age of Child 2 to the variable b, and the age of Child 3 to the variable c. Initially, my instincts told me to look for clues while attempting to use 3 variable substitution.

I started thinking about possible situations, perhaps person B has twins or even triplets. Person B must have either one eldest and two younger twins, or children all of different ages. I ruled out triplets because the children's ages could not be equal to a cube root of 36 while remaining an integer. I also disregarded the addition of the eldest child playing piano because I felt that it was unnecessary.

I then thought about possible ways that person A might not be able to figure out the ages based on 2 equations, which are:

In the case of all different ages:

a × b × c = 36
a + b + c = y

In the case of one eldest and two younger twins:

In this case a = c, so we can write a in place of c
a × a × b = 36
a + a + b =y


Because of person A's response to the sum of the ages ("That still doesn't tell me how old they are."), it seems clear that this wasn't enough information for person A to use algebra and solve. In the case of twins and one older child, person B should have been able to use substitution to solve (2 unknowns in each of the 2 equations). But she or he did not, which leads me to believe that there must have been 3 unknowns in each of the 2 equations (one can not use algebra to solve this).

This completely stumped me until I began writing factors of 36.

2 × 18
4 × 9
4 × 3 × 3
2 × 2 × 9
2 × 2 × 3 × 3
3 × 12
3 × 2 × 6

I then realized that 3, 2, and 9 are the only set of 3 factors of 36 with all different values. I concluded that these must be the ages of each child.

This being said, I believe my solution is flawed, because if I assume that Person A could potentially do 2 variable substitution using mental math, it would also be reasonable to assume that he or she could figure out 3 different factors that multiply to 36.

Overcoming Frustration with Logic Questions

    Spending the past two weeks on basic logic in CSC165 has been incredibly tedious and somewhat annoying to me. Although I fully understand the necessity for these core ideas, I still find myself more thrilled by challenging problems such as, "Streetcar Drama" (presented several lectures ago). I'm working to appreciate these concepts, completing all given questions as fast as possible and reading ahead in the course notes, in an attempt to find pleasure in the completion of each new question. I felt that this week's tutorial as well as the quiz were exceptionally easy partially due to my study habits. I'm quite sure that with continued commitment to the course material, the level of difficulty will remain manageable for me.