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.

SLOG 6

This week we started learning about computability. I understood pretty much everything we did until the stuff on reductions. I found the building the halt function using the initialized function to be confusing. I think the most confusing thing for me was the f_prime function because I don't know where that comes from. I'll have to read the course notes to see if I can get a better understanding. If I don't I will have to go to office hours to try and get a better explanation.

We also big omega proofs and general big oh proofs. I liked the big omega proofs because they were polynomials and I find big oh and big omega proofs for polynomials are pretty easy. The general big oh proofs were much more trickier. You can't just follow a simple procedure to prove them like the proofs with polynomials. You actually have to use the definitions of each function being in big oh to come up with a B and a C. The tutorial questions are on general big oh proofs so that will be good practice for me to get more comfortable with them.

In tutorial, I think I got 2/2 on the quiz because it was a polynomial big oh proof and I really like those and can do them pretty easily so I found the quiz to be pretty easy.

SLOG 5

This week the new thing that we learned was proving big-Oh using limits. Proving that the limit is infinity is not too complicated but I was kind of confused when the actual whole proof was written out. I think the most confusing part was the whole n >= n' thing when translating the limit to its definition because no actual value for n' was chosen that's just what was written in the proof. So I'm not sure if that's the way you're supposed to do it or if you actually do have to pick a n' because writing the whole proof is kinda simple if you don't. I guess I'll see the way you're supposed to do it on the tutorial work next week and hopefully that clears all my confusion. If it doesn't, I'll have to look at many more examples.

We also did a lot of examples of proving different polynomials being in or not being in big-Oh. I really enjoyed this because they seem like they're actually really easy to do. It's really easy to tell if the polynomial is actually in big-Oh or not since you just have to look at the highest degree. And the examples made it really clear how to actually show they are in big-Oh. Hopefully, I really do understand this stuff pretty well and I can do the tutorial work pretty easily.

I think I did okay on the test. I'm pretty sure I did the first and last proofs correctly but I know I made a mistake on the second one. I think most of the proof was correct but I realized like 2 minutes after handing it in that my chose of w would not always work and immediately thought of one that would always work. So hopefully even with that error, I still get a decent mark.

The quiz in tutorial was so easy that it wasn't easy. When doing it I completely over thought what was actually happening in the function and realized at the end that it was actually really, really simple. Because it took me so long to figure out what the pattern was, I think my explanation for how I got my answer wasn't very good.

SLOG 4

This week we did more on sorting algorithm analysis and also learned about O, Ω, and ϴ. I really understood the definitions O, Ω, and ϴ and I feel like proving that a function belongs to them is not really that hard, so I really enjoyed that part of the lecture. I found determining the worst-case running time and more specifically the lower bound worst running time to be kind of confusing. For the example of finding the lower bound in class I did not get why each loop was at n/3 iterations. There were 3 loops so I don't know if it came from that or something completely different. I will have to look at more examples and try calculating some on my own to hopefully fully grasp the concept. 

I'm pretty confident that I got 2/2 on the tutorial quiz because it was pretty similar to a question for the work we had to do and I did not find that question particularly difficult. I also finished the assignment and although I'm pretty sure I knew whether each claim was true or false, I'm not sure if I did all the proofs correctly. There are only a couple where I am really confident they are completely correct.

SLOG 3

So we finished up proofs and started on sorting algorithm complexity. When we started on proofs, I really did not know how to approach them at all. Learning the proof structures really helped. When you write down the proper proof structure, it is a little easier to visualize the problem and you always have a place where you can start. I'm still not too great at actually proving the problems but I'm getting better. I just need to do some more practice and get even more comfortable doing them. I'm pretty sure I didn't get 2/2 on the tutorial quiz this week because I ended up confusing myself and didn't have time to completely start over.

We only really covered the very basics of sorting algorithm complexity and I think I understand it all so far. I feel like it will probably get much harder eventually and probably pretty confusing so I'm not looking forward to that.

This week I need to get started on the assignment and get a bunch of practice in for the test since both of those are coming up in a week.

SLOG 2

This week we learned a lot of new material in class. Some highlights include how to negate a statement, truth tables, and various laws. I feel fairly confident negating statements as we went over numerous examples in class and after doing some practice on my own I think I can do alright with them. The truth tables also seem fairly simple to use although we only did simple examples and I think that they probably would not seem so straight forward with much more difficult examples. The laws are little bit confusing because I have never seen them written symbolically. Seeing them written this way will take some getting used to.

Last week's quiz did not go as planned. I was not careful enough with my work and write down the answers backwards. Not reading the question carefully and not watching what I'm writing down has been a problem for me in the past so I really need to work on that and read things over multiple times. I think I got the answer right for the quiz this week right though.

I did the assignment and I feel like it was really fair. It was a little challenging but not overly difficult. There is one question that I'm too sure about but I still have a week to think it over and hopefully it and all the other answers right.