Big O, Big Omega, Theta - Slog #8

When we first learned about Big O, Big Omega and Theta this past few weeks, I often went into a blank state as to what the definitions were.
To sum it up,
Big O: O(g) = {f : N -> R+, ∃ c ∈ R+, ∃ B ∈ N, ∀n ∈ N, n ≥ B => f(n) ≤ c g(n)
Function f is bounded above by function g (constant factor of c).

Big Omega: Ω(g) = {f : N -> R+, ∃ c ∈ R+, ∃ B ∈ N, ∀n ∈ N, n ≥ B => f(n) ≥ c g(n)
Function f is bounded below by function g (constant factor of c).


Theta : Θ(g) = {f : N -> R+, ∃ c ∈ R+, ∃ B ∈ N,  ∀n ∈ N, n ≥ B => c1 g(n) ≤ f(n) ≤ c2 g(n) 
Note: It's basically the combination of Big O and Big Omega. 

Function f is bounded above by function g by a constant factor of c2 and bounded below by the same function with a constant factor of c1.

Reminiscing Pre/Post Test - Slog #7

In honest truth, I had initially feared that we'll be tested on proving/disproving limits (epsilon and delta proofs) since there were very few examples provided.

An example from the lecture:
∀ϵ ∈ R+, ∃ δ ∈ R+, ∀ y ∈ R, | y - π | -> |y^2 - π^2| < ϵ

To my understanding, (I hope) this means:
"For all epsilon, there exist a delta so that for all y is δ units of π implying that  
lim       y^2 = π^2
x -> π
As to providing the "body" of the proof, it's still a very vague topic and I hope through further practice and possibly future visits to office hours, this could be clear up. 

To my relief, I found the term test to be relatively fair since it incorporated proofs similar to the ones from the lecture and tutorials. When the solutions came out, I was stunned that the third question concerning "floor" was much easier than what I wrote down.

In essence,  I become worrisome before testing, and even more worried post-test while waiting for the marks.

Upcoming Test & Assignment 2 - Slog #6

Now that we have wrapped up the introduction to proofs, I can confidently admit that proofs are fun to tackle. Surely, it takes sometime to understand and decide whether to prove or disprove the statement. Even when that's all figured out, the challenge was actually writing up the "body" of the proof. In my group, we extensively attempted direct proof, indirect proof and contrapositive to conjure up a sensible solution. Oppose to watching the professor write the proofs and unanimously agreeing, this assignment was great practice in independently building up my proofs. Although I found the majority of the questions to be fair, my group oddly stumbled on question 1. The difficulty arises from transitioning a single inequality (such as a < b)
to a transitive inequality (a < b < c).

As for the next term test, I'm quite worry since I tend to linger on a question longer than time provided. Especially with the topic of complexity. Tutorial was useful in helping us determine the number of steps of a program.For instance, we were told that for every +,-, =, >, <, [], while, and, len operations, a extra 1 step is carried out. Using summation to determine the general equation of steps takes sometime but it's not too difficult. What I'm more worried about is writing the asymptotic proofs.

Term Test Results - Slog #5

As the week wrapped up and we move onto Reading Week, I am quite satisfied with how I did on the term test. As always after I write a test, I usually think pessimistically about the results to come. In a weird and convoluted way, having the mindset that I would fail usually gives me more motivation to study harder. In honest truth, I wasn't so confident while writing my answers down. In particular, there were uncertainties as to whether my explanations for question 1(b) was sufficient. Now that results are in, my lengthy but correct answers could have been shorten by referring to it`s negation instead of just listing all the examples or counter-examples. This could have saved me quite a bit of time that could have been invested into another question. But what`s done is done. So next time I should go in with a calm mind and be more observant with what the tools and knowledge I could use.


As for this week's lectures, we discussed more about proving different types of statements. Reassured by my TA, it's nice that we receive a large portion (40% was it?) of our marks from just writing the proof structure. For many of the proof structures there's a technique as to how you write it. 

If it is existential quantification such as ∃ x ∈ D, then we  write "Let x = ___. Then x ∈ D".

If it is a  universal quantification such as ∀x∈D, we write "Assume x in D".

I also noticed that most of the actual body of the proofs contain a lot of manipulation of mathematical expression and some background knowledge of their definitions.

Stressful Week - Slog #4

With the snowstorm and a week full of midterms, I'm glad it's finally over.
Initially, I had the impression that the term test would be difficult considering that an aid sheet was allowed. Instead, I thought it wasn't too difficult or easy; it was fair. Taking time into account, it was difficult to browse through the sheet. Overall, in my opinion, a lot of the content I wrote were useless since the test mostly pertained to list comprehensions and symbolism. Indeed, it`s great practice writing the sheet as you're basically reviewing all the concepts before actually taking the test thus it would greatly increasing the chances of being able to formulate the answer without aid.

As we wrap up logical notation, it seems easier now with more practice as oppose to my impression of it in January. But now, proofs worry me. 
As for the recent lectures, the proof structure seems straight forward. At this point, the only difficulties are formulating the body of the proof. For instance, during lectures we prove that something is odd by referring to the definition of 2k + 1. Yes this is true but I doubt I'll be able to come up with the actual "arguments"  for much harder proofs.

Now, as we anticipate the marks of our midterms, I hope I did well (?). Even it doesn't turn out to be my best, I'll just have to prepare more next time. 

Logical Confusion? - Slog #3

During the beginning of week 3, we were assigned tutorial exercises to translate sentences to their symbolic form. I have to admit, it was mind boggling at first. I was conflicted between choosing to use conjunction(^) or implication(->). Thankfully, this dilemma has cleared up. With the TA's help, I was able to grasp the basics of logical notation.

As the week progressed, I started to work with my group on assignment #1. With other peers, things became more clear to me as we tackled each question. With more practice, I am able to apply everything I have learned in Chapter 2, such as the Vacuous Truth, DeMorgan's law, truth tables and the manipulation rules.

On Friday's lecture, I found the folding paper exercise very engaging and mind stimulating. It was an interesting approach towards introducing proofs. As we being week 4, I hope it's not too hard to understand :)

Thinking back to my first perception of this course , I have to say that CSC165 isn't overly difficult as I mentioned previously. It just require practice. After all, practice makes perfect!   

Regained Confidence - Slog #2

After the second week of CSC165, I'm starting to pick up and understand more of the course material. Early in the week, I found myself to be very confused as the lecture hour progressed. Nevertheless, I found it especially helpful to learn future content from the course notes before the professor address it in class so I would have a key idea as to what is being discussed about.

This week's lecture consisted of implications, contrapositive and converses. There was a more extensive use of symbols in comparison to the first week. I noticed that deciphering symbols to sentences are less stressful than converting sentences to symbols. At this moment, it takes me quite some time to write symbols based on the sentence since the English language implies many different meanings, consequently making it harder for me to write in its symbolic form.
 
Additionally, going through tutorial exercises with the TA and discussions with other students were very helpful in clearing up any misunderstandings that I had initially.Although I still find myself slow compared to the rest of my peers, I feel that as long as I prepare ahead I'll be able to acheive great progress.