It's really been quite a busy few weeks, and I have a lot to discuss, based on the past classes and topics, so this SLOG will be quite a bit longer than some of my other ones. I'll start with the ever-feared big-oh and big omega and especially big theta proofs. I missed out on a class, so there is a bit of a gap when it comes to big-oh for me, so it's difficult for me to even begin speaking about my issues but I'll do my best. For starters, big-oh's general formula sticks in my head: There exists a c in positive real numbers and there exists a breakpoint B in natural numbers that for all natural numbers in n, n is greater than or equal to the breakpoint B and f(n) is less than or equal to g(n). I still don't fully understand what the breakpoint equates to; is it the smallest number the worst case of big-oh can fall under? It's just hard for me to grasp that concept entirely, which will be looked into in detail before the exam. Also, big theta is extremely confusing. I assume big theta to be a conglomeration of big oh and big omega, but how could there be an element bound above and below f(n)? In tutorial, there needed to exist two separate c's: one for big oh and one for big omega, each somehow falling in line to support the claim big theta makes. It's very frustrating, but I also need to study more on this for the test. Big omega itself is the opposite of big oh, so I would just need to look into one to make more sense of the other. To assist myself, I will be visiting the help center sometime this week for further instruction.
Moving on from their concepts, the structure of the proof itself is simple: choose a c and a breakpoint, then dive into the antecedent to create an inequality that will be solved as equal in the end. Of course, the structure IS always the simplest part of a proof, and has not as much to do with the "proving" part of a proof. Point being made: I need lots of practice with big-oh in general, in all shapes and forms, as it is a different type of concept I have not yet encountered in any of my other courses. We skimmed over it in CSC148, but here it's broken down into full algorithmic detail, and I need to practice it for the test. The polynomial big-oh equations are that much more challenging, as there are more terms to deal with, which slightly confuses me, but I have faith in myself to be able to tackle these problems in my studies.
Going towards more computational problems, halting really confuses me. It reminds me a lot of recursion in my CSC148 class, calling a function within itself to produce a type of looping effect. In proving these types of halting problems, I can't trace the code well enough in my head to easily solve these problems. Normally, not to be overconfident, I'm fairly good at tracing through a mental call stack in coding, but halting is something completely different: calling a function as a parameter to test whether or not the function itself will run a loop without halting. I do have the lecture notes, practice questions, and slides to reference in terms of this problem, and I have no trouble finding other examples of halting problems when i google it, so all these resources do help me a lot in terms of this issue.
Finally, I'll talk about induction, but only briefly, as the topic of induction was almost immediately lost on me on the first day. I enjoy math and calculation when there is a clearcut answer to be found and taken from an equation, but induction assumes that if a set follows a certain pattern, you would be able to reach an answer. I don't understand this at all, and quite frankly, I;m not too sure on how to tackle this problem. I could always google it as I would with halting, which I will do later, but induction only appears later in CSC236, so I'm a bit lazier when it comes to searching up proper induction (as any good computer scientist would be!). Making base cases is of course the easier step in induction, but once Prof. Heap switched it around to do the inductive step first, I was even more confused than I originally was. I would need to see him in office hours to make sure I understand a lot of the concepts I have listed in this post, but I am certain that with practice, I'll have no trouble passing the course and moving on to larger and more difficult problems, that I will once again be able to solve.
No comments:
Post a Comment