Sunday 2 November 2014

Hello and welcome! This slog will cover weeks 7-8. In week 7 we mainly focused on proofs by cases, interference and sorting algorithms. In week 8, we mainly focused on worst case, counting steps, and big-Oh.

So in week 7, the material covered was very familiar as it was just going over some of the things we have already been doing. Proofs by cases were nothing too new and was very easy to follow. For these proofs, the idea is that if you’re given a statement to prove, but you have to two or perhaps more parts to the statement, then you would organize the proof into sub proofs or cases. For example, the statement, “For every natural number n, the sum of n2 and n is even”, well natural numbers can be even or odd so we would split the proof into two cases where the first case is assuming n is an even number and the second case would be to assume that n is and odd number.

Next we talked about interference in our proofs like implication, universal, and existential introduction, as well as conjunction and disjunction introduction. These are the things that we already have used in our proofs where we either assume what we’re given or pick something that belongs in the specified domain. These “rules” have already been applied into our proofs that we've been doing so I won’t get into that much detail with them.

Lastly in week 7, we started talking about sorting algorithms. We talked about insertion sort, selection sort, and other sorts just as the Tim sort and merge sort. Basically the idea is which sorting method is the best for sorting out some cards in your hands. Well it actually depends on what cards you have in your hand, for example, numbers, colours, and suits and what how you want to sort them. I myself am not too familiar with each sorting method but it’s basically comparing perhaps one card in your hand with the card on the right or left of it and seeing which one is greater or smaller and then rearrange that card into the order that you want.

Then in week 8, we talked about counting steps with those sorting methods. Really counting the number of steps to sort something is really what we want to know. We talked about a python program where there were while loops, and we basically had to count the number of steps the program operated. For example,


When this function is called,  the first line runs only once, the while loop will run until the parameter is false, but then will run once more to jump out of the loop. The lines of code that are inside the while loop will run as many times as the while loop. Though the return statement will only operate when the If statement is true, which means it only runs once. After the whole while loop executes, the final return statement will run once as well. If the first return statement in the while loop executes, then the bottom return statement will be skipped.

In 165, we mainly focus on the worst case. I’m not too sure what worse case is and I’m still trying to wrap my head around big-Oh. I hope by next week I’ll figure it out through tutorials. We also talked about Upper Bound and Lower Bound where the worst case for the upper bound will be no worse than it and the worst case for the lower bound will be at least as bad as it. I really wish I could explain further into big-Oh but again I still don’t really understand the concept yet so by next slog I will try to talk more about big-Oh and the proofs for upper and lower bound.


Thanks for reading!

No comments:

Post a Comment