Sorting Algorithms

Sadly, I was unable to post last week due to an incredible amount of studying i had to attend to.  Nonetheless, heres a quick refresher of the material we covered last week.  We wrapped up our study of proofs and basic mathematical structure for proof arguments.  We went over proof problems involving added complexity, such as epsilon delta proofs.  In addition, we covered ways not to do proofs such as proof by intimation or proof by puns.

Just as a side note: in the lecture slides it was shown that the statement "trivial" is an example of proof by intimidation, and should generally be avoided.  However, it seems authors of physics and mathematics textbooks use the term "trivial" on a regular basis.

The next topic of discussion and most of the focus of the past week was sorting algorithms. We began discussing the basic sorting algorithms including merge sort and bubble sort.  Heres a quick overview of the two sorting techniques.

Bubble sort: Its a sorting algorithm that compares the adjacent items in a list, and interchanges them if the are in the wrong order. The python implementation of bubble sort is shown below.

 def bubble_sort(l): 
 """ Algorithm for bubble sort""" 
 for i in range(len(l)):
     for j in range(len(l)-1-i): 
         if l[j] > l[j+1]:  
             l[j], l[j+1] = l[j+1], l[j]

Merge sort: Its a recursive sorting algorithm that use a "divide and conquer approach".  Namely, it divides the unsorted list into smaller sublists, and sorts each of the smaller sublists, and combines everything together to obtain the sorted list.  The implementation is not included here but can be found at http://www.geekviewpoint.com/python/sorting/mergesort.

Proofs!

With our first midterm in the books, I can finally commence my study of proofs.  Immediately following the midterm test, we began our study of proof techniques.  These techniques range from direct proof, proof by contradiction and proof by contrapositive.

The structure of these proof methods is as follows:

Consider some arbitrary statement P -> Q.  To prove this, we can do the following:

1. Proof by Contradiction:

Proof: Assume P ∧ ∼ Q.  Show some sort of contradiction.

2. Proof by Contrapositive:

Proof: Assume ∼ Q.  Show ∼ Q  ->  ∼ P.

3. Direct Proof:

Proof: Assume P.  Show  P  ->  Q.

I am confident that I understood the majority of content covered in lecture.  However, as with most academic topics, there are aspects that are incredibly easy, and others that are laborious and demanding.  The same applies to proofs.  While there may be ridiculously simple proofs such as showing that for all n∈ℕ, n is odd → n^2 is odd, there are also ridiculously difficult proofs such as 
Euclid's Theorem, which states there are infinitely many primes or something almost near
 impossible (even for the mathematicians), Fermat's Last Theorem.  For those interested, 
heres a nice and simple explanation of Fermat's Last Theorem: 
http://mathforum.org/library/drmath/view/52464.html 

Although, it should be mentioned that the proof is not included, as 
its far to advanced for non-mathematicians.

.

Already Midterm Season

With only a few more days until our CSC165 midterm, I've been steadily studying away.  I thoroughly reviewed all the tutorial problems and lecture notes, yet I am still in search for more practice questions.  Thus, I have turned to my trusty sidekick the Google Search Engine.

In lecture this week, we finished our study of basic equivalence rules and began the joyful art of proof writing.  Over the duration of my lifetime, I've seen and wrote many proofs, and never have there been formal guidelines on indention.  The structure for these proofs seems incredibly pointless.  Apparently, in CSC236, this particular format for writing proofs gets abandoned, although I can't verify this claim, as its only hearsay.  Nonetheless, even if its only temporary, this format for writing proofs is definitely something I'll have to gain familiarity with.  Otherwise, I look forward to diving deeper into proofs.

On a personal note, discrete mathematics or more precisely logic has always been a field I've lacked substantial confidence in.  In the past, I've studied elements of logic here and there, but never a complete study of the subject.  That is, until now.  In only a matter of three weeks, I have acquired a solid foundation in fundamental mathematical logic.  I look forward to applying this knowledge in the realm of digital design, namely FPGA's in CSC258.