Week 12: Final Remarks

    So this is the final week of the course before exam time, and hence the last slog. It's gone by quite fast but I learned a lot of new things and really found the experience quite valuable. I think, of the many courses I've done at this university, the concepts learned here will probably stick with me a lot more since they really introduced me to new ways of thinking and understanding problems.

   Anyways, I'm going to be talking about computability since I didn't touch on it last week and it's the final lesson of this class. As far as all the concepts I've learned in this course have gone, this is by far the most abstract and confusing to me. Of course, I've had past challenges with other things in this course, but I always felt that they made sense, but I just needed to do the practice and readings to develop a good intuition to solve them. This, however, takes some more time I think. Either way, I think it's a very interesting topic and I'll do my best here to explain what I've understood from lecture, course notes, and some videos I've been watching on the subject.
    First off, the definition of computability is that a function f is computable if for all inputs possible for the x, it will return the value of f(x). In other words, will the function halt (not end up in an infinite loop). Halting doesn't necessarily mean the function has to return some value you can work with. The function crashing is still considered halting if the input x doesn't satisfy function f. This definition only applies to functions that are well-defined though, or in other words, if we can say what f(x) is for every x in some domain.

So, we were shown in class how the halting problem was proven to not be computable. That wasn't too tricky. The trick is how to prove using reduction. It takes a while to understand what the reduction code is doing in the first place, and how to write it. Other than that, how is this written as a proof? Is it just writing out the function and if the implementation is right then it's proven, or is there more to do? I've been doing some research and getting vague answers, but hopefully I'll get it soon.

Week 11: Recap from the Previous Weeks

    Since I haven't discussed how I've been doing with Big-O, Algorithms, and the other things from the past 3 weeks, I felt that by now I've caught up well enough and am ready to discuss how I'm doing.

    First off, algorithm analysis. I've done some practice to figure out how many times each loop in an algorithm should run in terms of n. The main issue I've been having is putting it all together. Perhaps this is because I need to better understand Sigma notation and how to use it properly, since I've forgotten some stuff from high-school. I need to brush up on worst-cases, mainly to think about how I can discover what the worst case of an algorithm should be when it may not be too obvious. There are also times where the worst case and best case seem the same (as in, the algorithm only increases running time with increasing size, not anything else such as searching for an item that doesn't exist like in linear search).

    As for Big-O and Big-Omega, I understand the notation fairly well. At first the whole over-estimation and under-estimation thing confused me (it was difficult to understand what was going on in the notes, there were a lot of numbers that seemed to come out of nowhere). I was pretty excited when I finally figured it out, and it's actually a fairly easy method to use with polynomials.
As for non-polynomials, while I don't find limits and l'hopital's rule too challenging, the definition of a limit and all those other things were slightly confusing. I didn't really understand fully why you go from existential n' in the limit definition and then back to existential n (when disproving if f(n) exists in O(g(n)).

   Finally, for bigger picture general expressions in Big-O, it pretty much varies for me. Some were easier to figure out than others, I really just need more practice with different situations. I do, however, understand the whole picking c and B thing. I should also check up on what the whole max thing is that kept coming up, because while I understand what a maximum is, I don't fully understand its use here other than getting a big number.

  I haven't touched on computability because I have little to say about it right now. More on that next week. 

Solving the Ships Puzzle Using Polya's Method

So, for those that don't know the "Ship Puzzle", it's a puzzle created by Einstein supposedly, that bears some similarities to the famous Zebra Puzzle (or fish puzzle. . . it's the one with the houses). Since the Zebra puzzle has plenty of sources with step by step solutions, I'd rather do one puzzle that doesn't tempt me to just cheat, so I'll be solving the Ships puzzle step by step using the Polya method.

So here's the puzzle:

There are 5 ships in a port:

1. The Greek ship leaves at six and carries coffee.
2. The Ship in the middle has a black chimney.
3. The English ship leaves at nine.
4. The French ship with blue chimney is to the left of a ship that carries coffee.
5. To the right of the ship carrying cocoa is a ship going to Marseille.
6. The Brazilian ship is heading for Manila.
7. Next to the ship carrying rice is a ship with a green chimney.
8. A ship going to Genoa leaves at five.
9. The Spanish ship leaves at seven and is to the right of the ship going to Marseille.
10. The ship with a red chimney goes to Hamburg.
11. Next to the ship leaving at seven is a ship with a white chimney.
12. The ship on the border carries corn.
13. The ship with a black chimney leaves at eight.
14. The ship carrying corn is anchored next to the ship carrying rice.
15. The ship to Hamburg leaves at six.

Which ship goes to Port Said? Which ship carries tea?
___________________________________________________
So, the first step in Polya's method is to see if I understand the problem. First off, it's asking me to answer who is going to Port Said, and which ship carries tea. Therefore there are two things missing out of of here that I can fill in based on this information. Secondly, I know that there are a total of 5 ships, each has a country, a position it is docked in a port, a good that it carries, a time it departs, a place it arrives at, and a chimney with a specific color.

Next step is to come up with a plan and go through with it. What the givens tells me is that the best method to solve it would be to create a grid with this information, and fill it in step by step:

Dock Position	1	2	3	4	5
Country
Carries
Depart Time
Going to
Chimney

So, now that I made a grid, the next step to do is find any points in the list of givens that immediately place an item in the grid. Interestingly, without the grid, this would probably have been harder to do since you have to visualize the positions, but it's the second point in the list that gives away a position.

2. The Ship in the middle has a black chimney.

So, adding this to the grid, since there is an odd number of positions, the middle is position 3.

	1	2	3	4	5
Country
Carries
Depart Time
Going to
Chimney			Black

Now, it's time to find other points that relate to the middle ship having a black chimney:

13. The ship with a black chimney leaves at eight.

	1	2	3	4	5
Country
Carries
Depart Time			8:00
Going to
Chimney			Black

This next part is where it gets tricky, because nothing is given directly. I had to connect several things together and take a good guess. First off, the french ship (with blue chimney) is on the left of the ship carrying coffee, and the ship carrying coffee is the greek ship, which leaves at 6. That simply means that the French ship cannot be in the 5th position. I'll keep this in mind for later. 

Here's something that can give a position away: To the right of a ship carrying cocoa is a ship traveling to Marseilles. Also, the Spanish ship is to the right of the ship going to Marseilles. 

Here I'm going to have to take a bit of a leap and come up with a possible position for all this that makes the most sense. I'm going to assume that since the French ship is to the left, its safest position to place it is in the first position. The safest position to place the Greek ship is next to it. This works out since we know the Greeks have coffee, and therefore cannot have cocoa. That leaves the third position with cocoa, followed by the ship travelling to Marseilles, and the Spanish ship to the right of that.

	1	2	3	4	5
Country	French				Spanish
Carries		coffee	Cocoa
Depart Time			8:00
Going to				Marseilles
Chimney			Black

\

Now, once again, fill in the blanks with given information. 

	1	2	3	4	5
Country	French	Greek			Spanish
Carries		Coffee	Cocoa
Depart Time		6:00	8:00		7:00
Going to				Marseilles
Chimney	Blue		Black

At this point, to make it more clear, I've eliminated all the hints that I've made complete use of, now left with the following: 

3. The English ship leaves at nine.
6. The Brazilian ship is heading for Manila.
7. Next to the ship carrying rice is a ship with a green chimney.
8. A ship going to Genoa leaves at five.
10. The ship with a red chimney goes to Hamburg.
11. Next to the ship leaving at seven is a ship with a white chimney.
12. The ship on the border carries corn.
14. The ship carrying corn is anchored next to the ship carrying rice.
15. The ship to Hamburg leaves at six.

So, once again, I can look for points that are based off of the position I already have:

11. Next to the ship leaving at seven is a ship with a white chimney.\

While next to can be directly right or left, since we know the Spanish ship leaves at seven and I placed it to the far right, that means the position of the white chimney has to be 4. 

	1	2	3	4	5
Country	French	Greek			Spanish
Carries		Coffee	Cocoa
Depart Time		6:00	8:00		7:00
Going to				Marseilles
Chimney	Blue		Black	White

Now for something a bit more tricky (no guessing though). We now that the ship on the border carries corn. But what border? Could be the french or Spanish. However, we also know that the ship on the border is anchored next to the ship carrying rice! The French are anchored to a ship carrying coffee, so that only leaves the Spanish with corn. It's also best to fill in everything else I know about corn. 

	1	2	3	4	5
Country	French	Greek			Spanish
Carries		Coffee	Cocoa	Rice	Corn
Depart Time		6:00	8:00		7:00
Going to				Marseilles
Chimney	Blue		Black	White

I'm going to eliminate the clues once again: 

3. The English ship leaves at nine.
6. The Brazilian ship is heading for Manila.
7. Next to the ship carrying rice is a ship with a green chimney.
8. A ship going to Genoa leaves at five.
10. The ship with a red chimney goes to Hamburg.
15. The ship to Hamburg leaves at six.

Now, If you haven't noticed, we have 4/5 spaces filled for items being carried, which actually already answers one of the questions. The riddle asked which ship carried tea. Looks like it's the French! Moving on now, there's still another question to be answered. What else can be filled in? 7. Next to the ship carrying rice is a ship with a green chimney. With rice in the fourth position, between a ship that has a black chimney and one with an unknown color, it must be the one with the unknown color (the Spanish ship). 

	1	2	3	4	5
Country	French	Greek			Spanish
Carries	Tea	Coffee	Cocoa	Rice	Corn
Depart Time		6:00	8:00		7:00
Going to				Marseilles
Chimney	Blue		Black	White	Green

Once again, we have a row with 4/5 solved! That leaves the color red in position 2. What do we know about red? It goes to Hamburg. What do we know about Hamburg? It leaves at 6. Yikes! I could have used this pointer earlier, turns out that's the Greek ship! (Tip: be more careful about this stuff!). 

	1	2	3	4	5
Country	French	Greek			Spanish
Carries	Tea	Coffee	Cocoa	Rice	Corn
Depart Time		6:00	8:00		7:00
Going to		Hamburg		Marseilles
Chimney	Blue	Red	Black	White	Green

Problem: we have few clues left but no 4/5 spaces. Let's eliminate our clues down a bit:

3. The English ship leaves at nine.
6. The Brazilian ship is heading for Manila.
8. A ship going to Genoa leaves at five.

So, the English ship leaves at nine, and a ship going to Genoa leaves at 5. We have two time slots empty, the French ship and the White chimney ship. However, the white chimney ship already has a travel destination (Marseilles). That must mean that the French ship is going to Genoa (and leaving at 5). Also, the other position must leave at 9:00, and hence must be the English ship. Finally, that leaves the last position in the middle to be the Brazilian ship which is heading to Manilla. 

	1	2	3	4	5
Country	French	Greek	Brazil	English	Spanish
Carries	Tea	Coffee	Cocoa	Rice	Corn
Depart Time	5:00	6:00	8:00	9:00	7:00
Going to	Genoa	Hamburg	Manila	Marseilles
Chimney	Blue	Red	Black	White	Green

Great, now there's one spot left. What was the question asking? Which ship goes to Port Said? 

Excellent, we don't know the destination of the spanish ship but we know the other 4, so the Spanish ship must be travelling to Port Said!

	1	2	3	4	5
Country	French	Greek	Brazil	English	Spanish
Carries	Tea	Coffee	Cocoa	Rice	Corn
Depart Time	5:00	6:00	8:00	9:00	7:00
Going to	Genoa	Hamburg	Manila	Marseilles	Port Said
Chimney	Blue	Red	Black	White	Green

Now that I've carried out my plan and solved the puzzle, it's time to take the step of looking back. How could this have been better? First off, the obvious point is that I should have noticed the Red chimney ship departs at 6:00, which happens to be the Greek ship which also happens to go to Hamburg. That would have likely saved me the whole guessing issue earlier with choosing the safest position for several different places. Moving forward, it's crucial to spent a lot of time really making the connections all together for each point and then move on to fitting them in place. That being said, I don't regret the grid, I can't think of a better method to have gone ahead with in this problem.