Much Ado About.....Pirates - Week 13

While I have written some problem solving blogs usually it was directly related to a specific problem encountered in lecture or in tutorial. I decided I wanted to try and use this knowledge on other problems. I was really inspired by Albert Xie’s approach to solving the penny pile problem. He actually went home and wrote a python function that calculated all possible penny piles transferring from left to right and right to left.

The link for his entry is here:

http://99bugsbutaglitchaintone.blogspot.ca/2014/10/week-7-penny-piles-recursive-solution.html

Given all the extra work he did, I decided to work with Lebo Radebe on a common google interview question for fun. We found the problem online and took some time to try and work out a process to solve it. She also wrote up her experiences with solving the problem. Her slog can be found at the following link:

http://slog165lr.blogspot.ca/

THE PROBLEM:

Five pirates of five ages have 100 gold coins to split. The pirates are both greedy and democratic. The oldest one gets to propose how to split the gold coins and everyone gets to vote on it. If 50% or more agree with it, that is how they will divide the coins. If not, the oldest pirate gets thrown overboard and they repeat the process.

THE PROCESS & SOLUTION:

1) Understanding the problem:

Taken from Danny, I asked myself what the possible inputs would be and what would the outputs be?

In this respect, I thought about if I was building a function in python, I would need to know the number of pirates and need to know how many gold coins are being divided. The output would be the number of coins each pirate would receive .

What would they like me to achieve in this problem?

The goal of this problem is to devise a division of coins that would be acceptable for enough of the five pirates to vote for it. Right away I know that I don’t have to appease all the pirates, which I think will be an important consideration later on.

2) Devise a plan:

Given that I have now thought about my inputs and outputs, I can also think about the extra information that we are given. Since I know the pirates are greedy and democratic, I would assume they would try and maximize their potential earnings while still keeping in mind that they could be outvoted by others.

I also realize that this can be a complex problem to start with. I think I will start with a smaller number of pirates, work out how that can be achieved and then move on to a larger group. I will also want to look at even or odd numbers

The strategy that works for me:

As mentioned above, I know that I like to work with smaller numbers, consider many different cases and I would also like to visualize the problem in some sort of diagram or chart.

3)  Carry out the plan

The first thing I did was figure out what would happen with the smallest group possible. Given if there was only two pirates, I would know that the leader could take as many gold coins as he wanted and the first pirate would end up with nothing.

Now I add one more pirate to the scenario. As we are dealing with an odd number of pirates, there has to be at least one other pirate (other than the leader) who is appeased by the arrangement in order for the deal to work. As the 2^nd oldest pirate knows that if he doesn’t vote for the arrangement he would be the leader, only by giving him all of the coins could the leader get his deal passed. In contrast, by only giving one gold coin to the youngest pirate, it is guaranteed his deal is going to go through. The youngest pirate would take one coin over nothing and so he will vote in favour of the third pirate’s proposal.

When adding four pirates it becomes more complicated. There are two things that should be taken into consideration. We are told that if a pirate would receive a similar deal if he gets rid of the leader, he will vote against the leader. Also, we need to remember the deal that would have been made given three pirates. Thus for four pirates, he cannot give one to the youngest to get his 50% of the votes, as we know that the youngest will vote against him given the deal. Furthermore, the 3^rd oldest will vote against him because he knows that if he gets rid of the older pirate he will get 99 gold coins. Thus, the best solution is to give one gold coin to the second youngest and keep 99 for himself.

Finally with the fifth pirate, all previous cases need to be taken into consideration. She knows that she needs to win over at least two other votes in order to make her deal pass. The second oldest pirate will never take the deal as he knows by voting her out he can have 99 coins. Additionally, we know that the 2^nd youngest pirate will not take 1 coin as payment because he would get the same deal if the 2^nd oldest was in charge. Thus you would have to give him at least two but you would still have to buy off someone else to get 50% of the votes. This means giving away at least three coins. Alternatively, if the oldest pirate gave one gold coin to the youngest pirate and one gold coin to the third pirate, she would only lose two gold coins. The two younger pirates would take the deal as if the 2^nd oldest pirate was in charge they would get nothing.

While I wrote out this problem in words, I used the same logic but Lebo and I worked it out in a table. Here is an image of the table that we used to figure out the configuration for each number of pirates.

4)  Looking Back

I was really happy to have Lebo here to discuss the problem with me. She questioned why I made the decisions I did and made me look at the problem in a different light. While having only two or three pirates was simple, once we got to four, we had to discuss why we thought certain pirates had to have extra coins. Working through it with Lebo made it more fun but it also made it more challenging (in a good way!)

Overall it was a fun process. I figured out by creating tables, using smaller cases and by discussing with someone your process (or by writing it down), you don’t skip over steps. I think in the future, I will try and write out my process as it helps me catch my own inconsistencies.

FINAL THOUGHTS:

I just want to end this slog saying how much I enjoyed this course. Coming in I was not so sure how well I would do and I really didn’t think I would enjoy the material. I was really pleasantly surprised. I also am very fortunate to have great lecturers, Danny and Larry, who both care a lot about their students. I also had an awesome TA who took time after class to continuously help me. That is a rare thing. Finally, my classmates have been really insightful and they are an incredible resource. Learning how other people think through problems has made me evaluate how I look at problems. I honestly can say that this class has made me a better student and a more critical thinker.

The Course Towards a True Proof Never Did Run Smooth - Week 12

This week my focus has been mainly on the third and final assignment. As the course is coming to an end, I have been giving a lot of thought to all the different things I have learned. While overall, I feel like I have made a lot of progress, there are certain types of proofs that I continuously get caught up in. Any problem dealing with limits has proved to be quite a challenge. The first encounter with the epsilon delta proofs was quite overwhelming and while I made some progress in handling those type of proofs, I still feel that there is a lot more work that needs to be done. Furthermore, we have now been introduced to some calculus rules while dealing with limits. I do not have a lot of experience with calculus so now dealing with calculus in proofs feels like a very difficult challenge.

In general, developing an intuition about what a limit actually is can be quite difficult. I had a general idea, but it was still difficult to wrap my head around what a limit really is. I went to office hours this week to try and get a better grasp at what is going on.  Danny helped me out and gave me a written English sentence to try and understand what it means when a limit is approaching 0. He told me that the ratio you are using gets as close as we want to 0 provided we choose an “n” big enough.

Using the formal definition of a limit, we get:

"c e Â⁺, $n_c e À, "n e À, n ³ n_c Þ (ratio that has a limit that approaches 0) < c.

This fits the loose definition that Danny gave me and brings more understanding to the more formal way of putting it.

This assignment has allowed me to practice these types of questions and forced me to try and gain a better understanding of what a limit is. I don’t think by the end of the course, I will have a full grasp but I will definitely know a lot more than when I first came in. That in itself makes it worth the effort.

An infinite deal of nothing...or something? - Week 11

This week we have been discussing uncomputable functions. Specifically in lecture today we began to discuss the problem of cardinality. In turn, this came down to the question of how do you count infinite sets? In counting, we have come up with two key methods to ensure that we are not over or under-counting. These methods work for finite sets but it becomes more problematic when dealing with infinite sets.

The two rules of counting are as follows:

1) You have one-to-one matching

2) You map only once something from your domain to your range

For infinite sets it is much harder to apply these principles. When we are trying to compare the size of two infinite sets we can determine if one is actually larger than the other. If they are the same size, we can match them up in such a way that they have a one to one ratio. However, some infinite sets are not countable. The definition for being countable is having a one to one match up with the natural numbers. While the set of irrational numbers are countable, the set of real numbers are not.  Due to this fact, we can say that infinity of the real numbers is larger than the irrational numbers.

I find these concepts to be incredibly interesting but it is taking some time to wrap my head around the details. I think it is a good way to finish up this class as it is opening the doors to interesting future topics without overwhelming us with an overload of information. I look forward to hearing more about infinite loops…I just hope that my future code is not responsible for them!

Proving NOT (n3 \in O(3n^2): We Know What n^3 Is But Not What It May Be - Week 10

In this week’s first lecture we were going over how to prove or disprove that a polynomial is in Big O. While last week the focus was primarily on proving that a polynomial had a growth rate no faster than the polynomial inside the Big O, the start of this week has been focusing on disproving this. Proving something in Big O seems more straight-forward than disproving for these cases. While neither is particularly hard, it feels as if there are more considerations for the negation.  To prove this type of question, you must subtract values that are decreasing the value of the polynomial and multiply terms by n to increase it for comparison. For the polynomial in big O, you can do the same type of modifications to decrease it until the two formulas are easily comparable. Then it is fairly simple to pick B and c.

Disproving it takes a few more steps and I believe a little more thinking. Here is one example of this type of question.

We were asked to disprove n³ e O(3n²):

$c e Â⁺, $B e À, "n e À, n ³ B Þ n³ £ c*3n²

The negation of this is as follows:

"c e Â⁺, "B e À, $n e À, n ³ B Ù n³ > c*3n²

Assume c e Â⁺ and B e À       # generic c, B to introduce "

                Pick n = B + é3cù + 1. Then n e À.

                Then n ³ B        # added some non-negatives to B

                Then n³ = n * n²

                Then n³ > 3cn²     # since n > 3c

                Then n ³ B Ù n³  > 3cn²

Conclude "c e Â⁺, "B e À, $n e À, n ³ B Ù n³ > c*3n²

While this question is a very simple example of the much harder proofs we will be doing, it does show that when choosing n, many things must be considered. The value of n must be greater than or equal to B and the formula itself must take into account the other polynomial and c. Furthermore, as n must be a natural number and c does not have to be, flooring or taking the ceiling is also necessary. In the end, we know that n³ is a polynomial to the third degree, but we don’t know (until we prove it) that n³ is not in the Big O of 3n².

Runtime is the Most Beautiful of Dreams and the Worst of Nightmares - Week 9

This week we continued on with runtime proofs and while I realize the importance of understanding runtime, I continuously struggle with it. While working through the basics of polynomials seems more straight-forward, actually creating the equation based on the code is very difficult for me. While we have had a couple examples in class, it is still hard to see the relationships between multiple while loops in a single function. Some of them seem fairly simple with a run-time of n to the power of however many while loops exist, others are not that simple with a j based on an i and a k that do not behave as expected. In those cases I am not even sure how to begin to understand the relationships between the while loops.

In this week’s tutorial, we had to come up with a formula for a function. I tried to emulate the formula we had done in the previous week. I worked with a couple other people in tutorial and we had all assumed that the middle loop ran for 3n + 1, while the outer loop ran another n amount of times. We tried to multiply them together but the relationship between the two was more complicated. It needed a summation between the two. In the end, the answer was 3n(n-1)/2 + 4(n-1) + 2. While our TA did a good job of explaining why this was the case for this particular example, I believe I would have trouble recreating something similar in the future.  Thus, runtime can be both wonderful and horrible in practice but it can also be this way when trying to calculate the runtime.

  

Taming of the Proof - Week 8

While the topic of the course has switched to theory of computation, and more specifically algorithm analysis, I have been more focused on the regular math proofs we have been doing. This is largely due to the assignment that is due on Monday and the midterm that is on Tuesday. While it is surprising that my ability to solve proofs is getting better very quickly, I am noticing some common trends in where I am stuck with solving proofs. I seem to be able to find a conclusion and then show how I came to that conclusion but I struggle with identifying the entry point of where to start in that proof. This is especially true when trying to prove a statement with a format such as p Ù q. You cannot assume p and so where do you begin in your proof to prove p? There must be some base assumption of p that is legitimate to start with. My problem seems to be identifying what is the correct base assumption. I have had to rewrite numerous proofs as I realized I was starting with the consequent and deriving the antecedent.

One of the most useful (but perhaps obvious) lessons I have learned this week related to base assumptions is that proofs cannot start with a tautology. When trying to show that two different things are equal, I tried to show how you can start with p = p, which could be derived to show that p = q.  However, as the proof started with a tautology it is invalid. I had to go back and find an attribute of p that would later link it to q. In the end it was successful but it was not the most intuitive step to take.

Overall, while I am getting better at writing proofs, the ordering of steps and the entry point of a proof is still something I need to work on. Hopefully with some more practice, it will become more natural. 

Logic Looks Not with the Eyes, But with the Mind - Week 7

The last few weeks I have been writing about developing both intuition and structure for proofs.  As time is passing, I feel like I am making some progress but it continues to be a very trying experience at times. It can feel like there are moments when I am going through the motions of how to understand something rather than recognizing things that my brain already knows to be true. In this week’s tutorial, I encountered a problem of this sort. We were given the following:

Definition:  ëxû = max {z e Z, z  £  x}

And here is the question that we had to disprove:

"x, y e Â, (x ³ 1 Ù y ³ 1) Þ  ëx/yû =  ëëxû/ ëyû û

The first step I simply negated the statement.

$x, y e Â, (x ³ 1 Ù y ³ 1) Ù  ëx/yû ¹  ëëxû/ ëyû û

The universal became an existential and the implication transformed into a conjunction with the form P Ù ØQ.

Next, I established the basic layout of the proof I wanted to do:

Pick x = ___. Then x e Â

Pick y = ___. Then x e Â

Then x ³ 1 Ù y ³ 1

Then ëx/yû =   _____ #algebra

Then ëëxû/ ëyû û =  _____#algebra

Then ëx/yû ¹  ëëxû/ ëyû û

Conclude $x, y e Â, (x ³ 1 Ù y ³ 1) Ù  ëx/yû ¹  ëëxû/ ëyû û

Once I had established that layout, I became stuck choosing values. While I had set up the majority of the proof, I could not think through the problem logically as I was becoming caught up in the definition of what the floor of a number is rather than just trying to think of two concrete numbers. It took some thinking before I realized that if I chose two numbers that when divided created a whole number, it would provide the example I was looking for. I ended up choosing 8.4 and 2.8. Thus, the final proof was:

Pick x = _8.4_. Then x e Â

Pick y = _2.8_. Then x e Â

Then x ³ 1 Ù y ³ 1

Then ëx/yû =   _3_ #algebra

Then ëëxû/ ëyû û =  _4_#algebra

Then ëx/yû ¹  ëëxû/ ëyû û  #as 3 ¹ 4

Conclude $x, y e Â, (x ³ 1 Ù y ³ 1) Ù  ëx/yû ¹  ëëxû/ ëyû û

In the end, I am trying to get over the fact that I am actually writing proofs and instead treat each component like a small puzzle to solve. If I spend too much time getting caught up in the symbols, I forget that I may already know the answer. Going forward, I will try to think more with my mind rather than simply reading it only with my eyes.

Be Not Afraid Of Proofs: For Those Who Have Proofs Thrust Upon Them. - Week 6

This week we went over the epsilon-delta proof once again. While we have covered the material before, this time, it was more formal and the example was more complex. I also had an interesting conversation with the Professor after class talking about the difference approaching something from a rigorous perspective and approaching it from an intuitive perspective. Both elements are required to write the proof but both require practice. In my own experience, I know that I have trouble translating my conceptual understanding of what are epsilon and delta into mathematical notation.

Currently, this is my understanding of the overall approach to these kinds of proofs:

 You are up against a challenge of an opponent who is trying to “screw you over”. However, you have the advantage of being able to make your move after he/she has made theirs. In other words, if someone gives you an epsilon range you can always pick a delta that fits that range. You can do it for any range that you are given and the epsilon and delta have always been restricted to positive real numbers. This has been the foundation for any epsilon/delta proof that we have encountered.

The difficulties come with solving the specific problem that comes with solving epsilon/delta proofs.

For example, having the requirements that |x – 3| < d Þ |x² – 3²| < e, requires techniques such as factoring, telescoping and the use of the triangle inequality. Furthermore, it requires choosing a delta that makes your overall problem simpler when you have to do addition at the end. While in hindsight this problem seems straight-forward, I had difficulties at the beginning of how to move forward.

I am going to spend the next week, trying to develop further intuition of how to approach the problems, as well as review some basic mathematical rules and techniques that my brain has forgotten. Hopefully with these tools, the next time I encounter an epsilon/delta proof, I will be able to approach it without feeling overwhelmed. 

What's in a Proof? - Week 5

This week has been mostly about the structure of proofs. It is a bit strange for me to think about proof structure without delving into the details of the proof itself. In order to figure out the structure, I believe there has to be some insight concerning where you should be starting from and where you are trying to go. In that case, there has to be intuition about what is required from you to construct the proof. Thus, although the focus of this week was supposed to be purely on the structural components, in reality, it was truly the real introduction on what it means to prove something. One of the first proofs we worked through was the following:

S: "n e À, ½P½> n

In this example, P is the set of all primes and ½P½ is the size of P.  When creating the structure of the proof, the choice of how you wish to approach the proof makes a difference. For example, the example provided below is one that uses contradiction:

Assume ØS: $n  e À, ½P½> n #negation of S

                Then there is a finite list, p1, pk of elements in P

Let q = p₁ x...x p_k   #q is the product of all primes

Then q > 1   #as q is at least 2 x 3 = 6

Then q + 1 > 2

Then $d  e P such that d divides q + 1  #every integer >2 has a prime divisor

Then d is one of p₁ to p_k  # these are all possible primes

Then d divides q

Then d divides q + 1 – q   #as d divides both q +1 and q (number theory)

Then d divides 1

Then d = 1   #only 1 divides 1

Then 1 e P   #this is the contradiction as 1 is not a prime number

Then S

This is just an example from the notes. But without knowing that the intention was to show a contradiction, it would be difficult to figure out what is required when it comes to setting some basic assumptions and values. In the end, there is more to a proof than what may meet the eye at first glance. So to answer the question: what’s in a proof? It is some great formatting and some even better thinking.

To Thine Own Proof Be True - Week 4

This is the first week of proofs and thus it is the commencement of what I believe to be the scariest material I am going to learn at university. However, although I am extremely hesitant to start working on proofs, the one thing that has resonated the most with me this week is how we were taught to approach a proof. In order to do a proof, you must have an understanding about what is actually going on. It takes creativity and examples to sometimes gain this understanding. I am also realizing more and more that is also about allowing trial and error. While this is applicable to more complex proofs, the same method can be applied to simple proofs. Take this example:

P Þ (Q Þ (R Þ S))       Û        P Ù Q Ù  R Þ S

P Þ (Q Þ (ØR Ú S))   #implication

P Þ (ØQ Ú (ØR Ú S))  #implication 

ØP Ú(ØQ Ú (ØR Ú S))  #implication

(ØP Ú ØQ Ú ØR )Ú S   #associative

Ø(P Ù Q Ù R )Ú S   #DeMorgan’s Laws

P Ù Q Ù  R Þ S    #implication

Again, while the proof is simple, I still had to look at where I was starting from, figure out where I was going and understand the small steps that got me from one end to the other. I plan to use the same thought process in more complex proofs. While it may take more time, more creativity and a greater acceptance of the mistakes that I will surely make, I just have to remember: to be true to my proof, I have to start to trust in my logic.

To Conjugate or to Negate. That is the Statement - Week 3

Translating English into logical symbols is not a simple feat and once having translated a simple sentence, I am starting to feel pretty good about myself. However it is one thing to memorize a translation, i.e, to know that if someone says if this, then this, I can use an implication, but it is another to comprehend the meaning behind the sentence and then translate it onto paper. My TA had a fantastic suggestion to conjugate or negate any sentence that I am trying to translate (and in this case I am using the inclusive or). Here is one of the examples from Exercise #2 that was particularly challenging at first. However, I tried to come up with a sentence that made the most sense to me (which was the opposite meaning of the statement given) and then apply a negation afterwards.

This is the statement I decided to take on as a challenge (and challenge me it did):

“No course has more than two prerequisites”

Here is how I decided to translate it.

Ø ( $x e C, $y e C, $z e C, $w e C, (P(x,y) Ù P(w,y) Ù P(z,y)) Ù ( x≠w Ù x≠ z Ù w≠z)

Now I tried to push the negation partway through:

"x e C, "y e C, "z e C,  "z e C, Ø((P(x,y) Ù P(w,y) Ù P(z,y)) Ù (x≠w Ù x≠z Ù w≠z))

The entire statement written out looks a bit overwhelming, so I decided to break it down into smaller parts. Here is the latter half of the statement that I now need to negate:

Ø((P(x,y) Ù P(w,y) Ù P(z,y)) Ù (x≠w Ù x≠z Ù w≠z))

This follows the negation pattern that we saw in class this week:

(P(x) Ù Q(x)) Û (P(x) Þ ØQ(x))

For my example, using this type of relationship, it would translate to the following:

Ø((P(x,y) Ù P(w,y) Ù P(z,y)) Ù (x≠w Ù x≠z Ù w≠z)) Û ((P(x,y) Ù P(w,y) Ù P(z,y)) Þ Ø(x≠w Ù x≠z Ù w≠z))

I am almost done. I just want to negate the final component

Ø((x≠w Ù x≠z Ù w≠z)) Û (x=y Ú x=z Ú w=z)

Whew, that was exhausting! Finally, the finished product:

"x e C, "y e C, "z e C,  "z e C, ((P(x,y) Ù P(w,y) Ù P(z,y)) Þ (x=y Ú x=z Ú w=z)

While it took several steps to complete, performing this action actually made the symbols and their relationships with each other more intuitive. So if I want to do well in this class, the question of whether or not to conjugate or to negate is easily answered…the answer is yes. And that is a statement