Week 8

In Wednesday's lecture, we wrote a proof of the upper bound on the worst-case performance of a sorting algorithm. It is often impossible to determine the exact worst-case, but we can approximate it by finding upper and lower bounds on the value.

I finished assignment 2 today. I had already completed most of the proofs but there was one that I couldn't solve until today. It seemed like the more obvious a claim was, the harder it was to prove. Next I need to prepare for the test next week. I feel confident about all the material covered so far but I need to make sure I haven't forgotten any information.

Week 7

Yesterday in class Professor Heap introduced the topic of the efficiency of sorting algorithms. Different algorithms may take vastly different amounts of time when sorting large amounts of data. The most significant factor is the number of steps involved in the sorting process. When we compare two algorithms, it is the most helpful to compare the number of steps involved in sorting the worst arrangement of items for that algorithm to sort, that is, the one that will take the longest. The worst arrangement is different for each algorithm, as they sort in different ways.

Week 6

I don't have much to talk about this week since there were no classes on Monday and no tutorial on Tuesday. Yesterday's class was on disproving claims using the proof format we learned in the last two weeks. To do this, one simply has to write a proof of the negation of the claim. Obviously, if the negation can be proven true, then the claim is false.

I checked the test solutions on the course website, and I believe my answers were all or mostly all correct, though my explanations were more detailed than required.

Week 5

I wrote my midterm test yesterday. I was given extra time thanks to accessibility services, which was good since I used almost all of it. Most of my time was spent explaining my answers, so I will need to be more concise next time. Nevertheless, I was able to finish the whole test and I think I did very well. There were no questions which I did not know the answer to. Completing Assignment 1 was excellent practise.

We began learning the structure of a proof last Friday and continued on Monday, and this week's tutorial exercises and quiz were on this topic. These were much simpler than the exercises from previous weeks since we were merely asked to write an outline for a proof, not to actually prove anything.

Week 4

Monday's lecture was on transitivity, that is, if P implies Q and Q implies, R, then we know that P implies R. As part of this discussion, we walked through simplifying a statement by turning implications into disjunctions. I'm glad we did this because I had been struggling to understand the relationship between implication and conjunction and disjunction. I learned that "P implies Q" has the same meaning as "not P, or Q". I compared these statements with a truth table and they are both true under the same conditions and false under the same conditions.

Understanding this relationship made my tutorial exercises and assignment much easier, since I had found it hard to understand the exact relationship between an antecedent and its consequent. Now, I can express complicated implication statements in a more familiar mathematical form.