On halting and computabaility!

    I owe you dear followers of this blog(I know no one's reading these but anyways:D) an apology for being late on the slogs in the past two weeks! I know you all have been busy with your last assignments of this term and the midterms.
 

    So let us get to what we are here for. the last thing we worked on in the course was the halting problem. there were a lot of students who got confused on how the proof is and the whole idea of the problem! I was one of those students and I read through the course notes, websites, other slogs and ... to try and get a better understanding of this. As helpful as they were none of them explained it to me better than this short video! I encourage you to take a few minutes out of your busy schedule and take a look at it! I promise it will worth it.https://www.youtube.com/watch?v=92WHN-pAFCs

Problem solving session

    I like to tackle the handshake at a dinner party problem for this week!
    what we know: 5 couples in the room! couples don't shake hand with each other and two people handshake at most one time.
reading up to here reminds me of a simple graph that with 10 nodes of 5 colors if we say that couples have the same color. There can't be an edge between two same colors and there is at most one edge between two different colors.
    I don't know about you but this made a really clear picture of the problem in my head! Turning all our data into something that we can imagine or even simply draw on a paper.

    In the following the problem says after a while we no that no two individuals have the same number of handshakes in the room.

   we know that one can at most shake hands with 8 people! (10 - partner - him/her self).
   if I for eg shake someones hand, this counts for both of us.
   at this point there are 9 people with different number of handshakes so we should have 0 to 8 handshakes between them! Since there is someone with 0 handshakes then the person with 8 handshakes has definitely shaken hands with Hilary!
........
next step is to analyze the data in a helpful way

Run time of algorithms

The past few weeks lectures have been about run time of functions and different algorithms.

You can check out this website for different famous algorithms run times!

http://bigocheatsheet.com/

For anyone who is interested In knowing more about algorithms, data structure, graphs and ... I suggest this book which I think If you are going to major in computer science will have it in one of the courses. The book is CLRS and I will post the link for AMAZON here:http://www.amazon.ca/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844