Final SLOG

We've finally reached the end of CSC165! For the most part I enjoyed this class because I learned a lot of good things that can potentially be helpful in other classes down the road. At the beginning of the course, I really did not like proofs and really had no idea how to approach them. Now at the end, I feel much more comfortable with them and they aren't as scary to me as they used to be. The one thing I liked the most about the class is how the stuff you learn earlier in the year didn't just go away. The first thing we did in class was learn about and symbols and logic and we still had to use them when talking about proofs and big oh stuff. It really made studying for the exam easier since I hadn't completely forgotten everything about logic. Going into the exam, there were no concepts that I didn't understand. I had a little trouble with the general big oh proofs and halting / computability to start with but I spent a lot of time on them and realized that they weren't really that hard and you just kind of had to be clever with what you chose for the big oh proofs and you just had to basically do the same thing as in the notes for the halting stuff. Hopefully I did well on the exam because I did a lot of studying for it and throughout a lot of work throughout the whole year so I really hope it all pays off.

Problem Solving

The problem I chose to do is free lunch problem.
To start, I made a table to help visualize the problem and see who would win the lunch each time a new friend is added until there are 17 people at the table.

# of friends      free lunch winner
1                       f1
2                       f1
3                       f3
4                       f1
5                       f3
6                       f5
7                       f7
8                       f1
9                       f3
10                     f5
11                     f7
12                     f9
13                     f11
14                     f13
15                     f15
16                     f1
17                     f3

It's pretty obvious that if you sit at position 1 and there is an odd number of people, you will be eliminated on the second go around the table since an even number comes after every odd number.
Looking at the table, you can see  that the person at position 1 wins if the number of people is equal to 2^n where n is an integer >= 0. So if you continue the pattern, then in addition to f1 winning when there are 1, 2, 4, 8, or 16 friends, f1 will also win if there are 32, 64, 128, and so on friends. Another pattern you can find from looking at the table is that each time another person is added to the table, the friend who wins the free lunch always increases by 2 each time until you get back to a number that is equal to 2^n, in which case f1 wins again. So as an example from the table, the winners for when there are between 4 and 8 people at the table  are f1, f3, f5, f7, and then f1 again. So the pattern for determining the winner is to first find the largest integer power of 2 that is < than the number of people and then the friend that wins is 1 + 2(the difference between the number of people and that power of 2). So if there are 10 friends, the largest 2^n < 10 is 8 so it would be 1 + (2*2) = 5 and f5 would win the free lunch. If there are 50 friends, the largest 2^n < 50 is 32 so it would be 1 + (2*18) = 37 and f37 would win the free lunch.

In general, the formula for finding the winner is 1 + 2(n - k) where n is the number of friends and k is the largest integer power of 2 that is less than n.

So once again using 10 and 50 as examples:
n = 10, k = 2^3 = 8
1 + 2(10 - 8) = 1 + 2(2) =1 + 4 = 5

n = 50, k = 2^5 = 32
1 + 2(50 - 32) = 1 +2(18)  = 1 + 36 = 37

These match up with what was found before so this formula is correct.