Friday 5 April 2013

Big Theta

Unfortunately, I have not had a chance to solve a proof involving Big Theta, it's that time of the year where I'm nocturnal, and making an 11am class seems impossible (unfortuantely).

Of course, Danny Heap was a great professor, so I always made an effort to go, In fact, I may have broken a personal record in how many lectures attended for a course.

Anyway.

I will attempt to solve a Big Theta proof in the following post.

Prove that 5n^3 - 3n^2 + 2n + 3 in in Big Theta(2n^3 - n^2 + n + 1)

Case 1:

Case 2:

Then 5n^3 - 3n^2 + 2n + 3 in Big O(2n^3 - n^2 + n + 1)  AND 5n^3 - 3n^2 + 2n + 3 in Big Omega (2n^3 - n^2 + n + 1) 
Hence 5n^3 - 3n^2 + 2n + 3 in Big Theta(2n^3 - n^2 + n + 1)

return False in [P(x) for x in L]

Questions like cost me a great first test score.

I just didn't understand them, and figured, because it was programming related, the probability of being tested on it was low. In retrospect, I'm an idiot.

I did manage to understand the question, in the last few minutes of the exam, but of course, that wasn't enough time to do complete the question.

This is the way in which I understood it;

P(x) is a boolean function, that takes the arguement 'x'.
It will return a value, either True or False.
The parantheses means that boolean function P takes x as an arguement.

L is a list.

(x) are values in the list, that when passed through P(x), return a boolean value.

[...for x in L] is saying, for each value 'x' in the list L.
[P(x) for x in L] is saying, pass value x through function P, for each value x, in the list L.
In other words, each value in the list will be passed through the function to return different boolean values.
Its closed in "[ ]" because we are collecting a list of those values.

So when we say
return False in [P(x) for x in L]
We are asking the program to tell us, if there is a single False in the list of boolean values we've collected, if so return True, because it does exist.
If not, return False, because it does not exist.

This is an example of Universal quantification, as we are trying to find a signle counter example to refute it, and if it doesnt exist, the statement is true.


SLOG Posts I have commented on.

 I understand the importance of giving feedback, and this is a short account of my responses to other SLOGgers posts.


http://whoshavesthebarber.wordpress.com/2013/03/28/■-the-atomic-number-of-people-in-a-csc165-lecture/

http://zjcsc165slog.blogspot.ca/2013/03/week-11-mar-25-mar-29-a3-and-halt.html

http://suzushirocsc.blogspot.ca/2013/04/who-wouldnt-want-free-lunch.html

http://captainslog165.wordpress.com/2013/04/05/stardate-87008-57-problem-solving-colin-s-score/comment-page-1/#comment-6

http://ryanocon.blogspot.ca/2013/03/test-this-week-im-counting-on-doing.html?showComment=1365210604988#c85223379010348562

http://ryanocon.blogspot.ca/2013/03/i-have-started-to-get-behind-in-this.html#comment-form

http://kevinhughcsc165.blogspot.ca/2013/02/wellthis-is-awkward.html#comment-form

http://c3fancho.blogspot.ca/2013/01/what-i-learned-list-comprehensions.html?showComment=1365210924905#c5844809406737192717

http://go-get-em-slogger.blogspot.ca/2013/03/problem-solving-episode.html?showComment=1365211057467#c5248701858503116705

http://hezhi1.blogspot.ca/2013/03/march-20-week-8.html#comment-form

A list of my favourite other SLOGS.

http://zjcsc165slog.blogspot.ca/ A great, regularly updated slog, about her experience with the course.
http://whoshavesthebarber.wordpress.com/ Includes pictures, which is a great idea, and lots of problem solving related posts.
http://vennsunslog165.blogspot.ca/ Regular summaries of what took place this year.
http://suzushirocsc.blogspot.ca/ - Detailed posts about the course material, and some problem solving.
http://captainslog165.wordpress.com/ - Very detailed, Lots of posts,

These 3 are my favourites because they are regularly updated, and have given me some kind of insight into understanding the course material.

Wednesday 16 January 2013

First Entry.

Hello.

This is my first entry to my CSC165 course log (SLOG).
It is definitely an interesting way to monitor peoples understanding of the course material.
At this point, the material presents no challenge, Its quite understandable. I feel like setting up a blog was harder than writing the quiz/tutorial.

We studied about the difference between Universal and Existential Quantifiers, and the anti-symmetry between them. We're representing these concepts graphically, with Venn Diagrams, which is a convenient way of looking at them. 

Well, I feel like thats all there is to say at the moment. Im sure when the course picks up in pace, there'll be a lot more to talk about, but at the moment, it's quite easy.

Until next time,
Mohammad.