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.