Hello, world. I'm posting this blog post after exams, so this post is not really an entry for the course SLOGs.... it's more like a Dear Diary entry where I pour out the contents of my aching heart. A soliloquy of my despair.
I'm currently in a state of panic. I went into the exam feeling fairly confident. I mean, I was able to answer all of the questions from the 2010/2013 exams, how bad could it possibly be? As long as I got over 40%, I'd still end up with a mark in the 70s. I prepared so much for it. My cheat sheet was crammed full of all of the possible questions from the assignments, tests, and lecture notes.
*echoing* Prepared so much for it. Prepared so much for it. Prepared so much for it *echoing*
On a scale of 1-10, I bombed that exam with a 100. I don't think I could have possibly messed up more than I did on that exam, besides like.... not showing up for the exam at all. All of the questions I thought would be on the exam, all of the questions that I prepared for.... were not on the exam. No halt (!!) , no generic big-Oh, no conversion of statements (Not all, Any). Nope. Nope. Nope.
I pretty much threw a course worth of achievements (I was so, so proud of my grade in the course... a mark in the high 90s) into a pile of feces.
I was expecting delta-epsilons to be on the exam, but I wasn't expecting TWO such questions to be on the exam. And they weren't ones I was familiar with. As soon as I saw the two, my mind went blank. Then I realized I couldn't solve both. I entered this state of complete and utter panic. I started sweating. My mind went blank. I'm actually fairly certain I was shaking at one point.
All of the questions I successfully answered, I somehow managed to misread the questions, and actually answer the wrong question. You're not reading that wrong. All of the questions that I SHOULD have gotten right, I somehow managed to prove something... that didn't even answer the question they asked. So I bombed the exam. Thoroughly.
How does one do this? How does one throw away a semester's worth of efforts in the matter of 3 hours. I failed that exam, without a matter of a doubt. We will be receiving our marks before Christmas, but I already know the result.
I went into the exam with high 90s, and now I'm not going to meet the minimum requirement for passing the course. I am going to have to repeat this course. I don't think words exist to describe how sad I am right now.
What is life.
Friday, December 12, 2014
Tuesday, December 2, 2014
That last minute struggle
After creeping and commenting on people's SLOGs over the course of this semester, I have to say that it's remarkable how people have gone from 2 posts all semester long (and this was the case for most people's SLOGs even 2 weeks ago!!!), to walls of texts. Oh, University, how is it that you are able to bring out the procrastinator that lies deep within all of our hearts.
Overall, I feel that the SLOGs are an excellent way of proving to yourself that you know what you're talking about. It's one thing to understand a concept, and another to demonstrate that you actually do understand the concept that you claim to understand. Was that statement extremely convoluted? Yes. But you know what I mean.
Throughout this semester, I've often gone from assuming that I understood a concept-- to realizing that I didn't. This was helped in part by reading SLOGs. I found it helpful to utilize other student's SLOGs to gain a better understanding of certain concepts. You often learn more from people who are also learning the material themselves. Good times.
Another thing that I have noticed is that I have spent a disproportionate amount of time in this course convincing others to realize why their proofs are insufficient or wrong. I'm not normally a confrontational person, but it can be a little exasperating at times when you're arguing with group members. You cannot prove a statement by restating it -- and you also cannot prove a statement by cleverly manipulating your proof so that it proves your statement, but only in certain cases. I'm not telling you that my answer is correct, but I'm most certainly pointing out why your proof cannot be correct.
After spending a semester taking CSC165, I have come to the realization that, although I have difficulty actually proving proofs, I have a strong foundation -- I can almost always tell when a proof is insufficient or wrong. I have also done enough practice proofs and studying to ensure that I am able to write proofs for the vast majority of proofs I should encounter in the exam. Hopefully this statement holds true for the actual exam. I also hope that, in the future, I will be able to devise proofs to problems with which I have not had prior experience with. Perhaps hone my intuition and induction skills?
Overall, it's been a great run. I can honestly say that this is most probably the only kind of course in which I would hear two students arguing over office hours with interjections of "BUT MY PROOF IS MORE ELEGANT" <-- legitimately, this was screamed aloud during Larry's office hours. Oh, UofT, you really, truly amaze me sometimes.
Anyways, I would 10/10 take this course again, and I would highly recommend it to any student - regardless of their major. Informative, educational, and enjoyable. Unfortunately, this SLOG will be seeing its imminent demise after the due date tomorrow, but it's been a great run.
Adieu!
Overall, I feel that the SLOGs are an excellent way of proving to yourself that you know what you're talking about. It's one thing to understand a concept, and another to demonstrate that you actually do understand the concept that you claim to understand. Was that statement extremely convoluted? Yes. But you know what I mean.
Throughout this semester, I've often gone from assuming that I understood a concept-- to realizing that I didn't. This was helped in part by reading SLOGs. I found it helpful to utilize other student's SLOGs to gain a better understanding of certain concepts. You often learn more from people who are also learning the material themselves. Good times.
Another thing that I have noticed is that I have spent a disproportionate amount of time in this course convincing others to realize why their proofs are insufficient or wrong. I'm not normally a confrontational person, but it can be a little exasperating at times when you're arguing with group members. You cannot prove a statement by restating it -- and you also cannot prove a statement by cleverly manipulating your proof so that it proves your statement, but only in certain cases. I'm not telling you that my answer is correct, but I'm most certainly pointing out why your proof cannot be correct.
After spending a semester taking CSC165, I have come to the realization that, although I have difficulty actually proving proofs, I have a strong foundation -- I can almost always tell when a proof is insufficient or wrong. I have also done enough practice proofs and studying to ensure that I am able to write proofs for the vast majority of proofs I should encounter in the exam. Hopefully this statement holds true for the actual exam. I also hope that, in the future, I will be able to devise proofs to problems with which I have not had prior experience with. Perhaps hone my intuition and induction skills?
Overall, it's been a great run. I can honestly say that this is most probably the only kind of course in which I would hear two students arguing over office hours with interjections of "BUT MY PROOF IS MORE ELEGANT" <-- legitimately, this was screamed aloud during Larry's office hours. Oh, UofT, you really, truly amaze me sometimes.
Anyways, I would 10/10 take this course again, and I would highly recommend it to any student - regardless of their major. Informative, educational, and enjoyable. Unfortunately, this SLOG will be seeing its imminent demise after the due date tomorrow, but it's been a great run.
Adieu!
Computability
I promised, and I shall deliver.
When we disprove the existence of a working halt function, what we are doing is claiming that not only has a working function not been written, but that a halt function cannot possibly exist. The disproof outlined in the coursenotes uses proof by contradiction.
First, assume that the halt function exists.
In this example, the author has cleverly constructed a function, confused, where if confused is passed itself as an argument, one can deduce that there will be two cases here: that the function confused(), when passed itself as an argument confused(confused) will either halt, or it will not halt. Now, this is where things were a little confusing. To completely the paradox, one must pass confused as an argument on itself. Not just any two functions will do. By doing so, we arrive at a contradiction.
Case 1: Assume confused(confused) halts:
Then halt(confused,confused) returns True.
Then confused(confused) goes into an infinite loop.
So, confused(confused) halts ==> confused(confused) does not halt.
Case 2: Assume confused(confused) does not halt:
Then halt(confused, confused) returns False.
Then confused(confused) halts.
So, confused(confused) does not halt ==> confused(confused) halts.
From this, we can conclude that confused(confused) halts <==> confused(confused) does not halt.
Thus P <==> not P. This is a contradiction. Therefore, the halt function is non-computable.
_________________________________________________________________________________
Reductions are a way to prove the non-computability of a function.
In a reduction, we first assume that our function is computable, and derive a proof by contradiction. By doing so, we prove that if our function is computable, then the halt function is computable. Since we have already proven that the halt function is not computable, we arrive at the contrapositive of our derived implication: that our function must be non-computable. The trick is to create a function f_prime() that utilizes the function f(i) within its body in a cleverly constructed way. If we are able to reduce halt to the meaning of life, we have produced a valid implementation of the halt function using our function. i.e we are able to utilize our function with arguments f_prime and i to determine whether or not a function halts on an input i. We know that this is not possible.
A function f is computable iff it is well-defined and we can tell how to compute f(x) for every x in the domain. In general, a function that remarks on the behaviour of another function will be non-computable.
When we disprove the existence of a working halt function, what we are doing is claiming that not only has a working function not been written, but that a halt function cannot possibly exist. The disproof outlined in the coursenotes uses proof by contradiction.
First, assume that the halt function exists.
In this example, the author has cleverly constructed a function, confused, where if confused is passed itself as an argument, one can deduce that there will be two cases here: that the function confused(), when passed itself as an argument confused(confused) will either halt, or it will not halt. Now, this is where things were a little confusing. To completely the paradox, one must pass confused as an argument on itself. Not just any two functions will do. By doing so, we arrive at a contradiction.
Case 1: Assume confused(confused) halts:
Then halt(confused,confused) returns True.
Then confused(confused) goes into an infinite loop.
So, confused(confused) halts ==> confused(confused) does not halt.
Case 2: Assume confused(confused) does not halt:
Then halt(confused, confused) returns False.
Then confused(confused) halts.
So, confused(confused) does not halt ==> confused(confused) halts.
From this, we can conclude that confused(confused) halts <==> confused(confused) does not halt.
Thus P <==> not P. This is a contradiction. Therefore, the halt function is non-computable.
_________________________________________________________________________________
Reductions are a way to prove the non-computability of a function.
In a reduction, we first assume that our function is computable, and derive a proof by contradiction. By doing so, we prove that if our function is computable, then the halt function is computable. Since we have already proven that the halt function is not computable, we arrive at the contrapositive of our derived implication: that our function must be non-computable. The trick is to create a function f_prime() that utilizes the function f(i) within its body in a cleverly constructed way. If we are able to reduce halt to the meaning of life, we have produced a valid implementation of the halt function using our function. i.e we are able to utilize our function with arguments f_prime and i to determine whether or not a function halts on an input i. We know that this is not possible.
A function f is computable iff it is well-defined and we can tell how to compute f(x) for every x in the domain. In general, a function that remarks on the behaviour of another function will be non-computable.
Thursday, November 27, 2014
CSC165 - Using CSC165 outside of CSC165
I have created an account with ProjectEuler (https://projecteuler.net) in order to utilize the skills that I have learned in CSC165. Attempting to solve challenging mathematic and computational problems outside of the curriculum is actually almost therapeutic and relaxing. Although the algorithms that I have been implementing have been primitive, at best, it has been an educational experience. I hope that, as I progress through the problems, that my inductive reasoning skills will be honed. Endurance! Perseverance! Euler!
On a side note, I have actually come to understanding the halting problem and computability. Huzzah! I will update this blog with a heartwarming tale of an underdog overcoming all odds in order to achieve her dreams. Or, I'll update this blog with an explanation of the halting problem and computability. One of the two. 'Till next time. Adieu!
On a side note, I have actually come to understanding the halting problem and computability. Huzzah! I will update this blog with a heartwarming tale of an underdog overcoming all odds in order to achieve her dreams. Or, I'll update this blog with an explanation of the halting problem and computability. One of the two. 'Till next time. Adieu!
Friday, November 21, 2014
CSC165 - Bless office hours
We have learned about the halting problem this week and, for the most part, everything has gone in one ear and out the other. Even referring to the course notes and reviewing the lecture notes did not really give me the confidence that I was actually comprehending what I was incessantly studying.
After I requested a last-minute office hour with one of the professors for the course (thank you thank you thank you thank you!!), I can now confidently say that I may or may not understand reductions and computability (haha). Okay, but no, seriously. I now have a much clearer understanding of the halting problem, and what we're trying to prove when we prove that halt is non-computable. I'm also more confident about reductions; where we prove that another function, F, is non-computable by reducing halt to the aforementioned function. In essence, we prove that a function is not computable by implementing a valid implementation of halt using the function F.
In disproving the the halting problem, we perform a proof by contradiction by assuming that the halt function is computable. After we construct a function that contradicts the halt function, we can use proof by cases to show that there exists a function that contradicts itself by halting when it doesn't halt, and doesn't halt when it's supposed to halt.
---Update--
Sadly, despite his excellent explanation and step-by-step guidance... I have come to realize that I still do not understand the halting problem.
After I requested a last-minute office hour with one of the professors for the course (thank you thank you thank you thank you!!), I can now confidently say that I may or may not understand reductions and computability (haha). Okay, but no, seriously. I now have a much clearer understanding of the halting problem, and what we're trying to prove when we prove that halt is non-computable. I'm also more confident about reductions; where we prove that another function, F, is non-computable by reducing halt to the aforementioned function. In essence, we prove that a function is not computable by implementing a valid implementation of halt using the function F.
In disproving the the halting problem, we perform a proof by contradiction by assuming that the halt function is computable. After we construct a function that contradicts the halt function, we can use proof by cases to show that there exists a function that contradicts itself by halting when it doesn't halt, and doesn't halt when it's supposed to halt.
---Update--
Sadly, despite his excellent explanation and step-by-step guidance... I have come to realize that I still do not understand the halting problem.
Thursday, November 13, 2014
Under-estimating and Over-estimating
We have been covering big-oh notation over the past couple of weeks, and I feel that I'm starting to finally understand the basic concepts behind it. Progress? Maybe?
I think the most important realization was that when given a f(n) >= cg(n), that you should approach the problem by "under-estimating" the right and "over-estimating" the left, and ultimately meeting in the middle. Then, choose a c that makes the right-side an upperbound.
To under-estimate (Right Side)
- remove a positive term
- multiply a negative term
To over-estimate (Left Side)
- remove a negative term
- multiple a positive term
We're trying to simplify the function without changing the highest degree.
Progress has been made, folks.
Saturday, November 8, 2014
Search methods, Sort methods, Big-O
We have been learning about big-oh notation in the last couple of weeks. More specifically, we have been learning about three sets of notations: including O, omega, and theta. These sets encompasses the sets of function that either grow no faster, no slower, or as fast as various base functions f(n).
Looking up the graphical representations of these functions was actually a refresher; as I have not taken any true math courses for quite a while. Review will be necessary.
It was interesting to think of functions not in run time, but in growth. Rather than assessing a function for its capacity to run within seconds, we look towards the growth in the steps as the input increases, as a means of testing the efficiency of a function. This is certainly a new approach to measuring run times, as someone with limited exposure to programming. I look forward to broadening my knowledge in this area over the course of the next few weeks.
Wednesday, October 29, 2014
Hmmmm......
Well, after reviewing the blogs of my fellow classmates, I feel less guilty about not updating my blog more frequently. I have greater than one blog entry. That's a start! What? What's that you say? I shouldn't be comparing myself to others, and the assignment outline details that I should be updating at least once a week? Rubbish!
Just kidding. Please don't hurt me.
Anyways, the midterm is fast approaching, and proofs will be the death of me. Upon reviewing last year's assignment and midterm, I feel fairly confident. But proofs with multiple quantifiers still confound me. Unfortunately, the assignment this year is one that I find (personally) more difficult to parse than last year's version. My way of approaching proofs with multiple quantifiers, with variables appearing in the statement out of the order in which they have been quantified, is to first pray that it's an epsilon delta proof, and then to assess which variable comes first (epsilon or delta). Whichever variable appears second "wins". That is my only approach. THE END.
... Okay clearly that will not help me. But one can dream.
Claim 1.2 appears to be very similar to a delta epsilon proof. However, the quantifiers are placed out of order, so I'm a little lost
I will update as soon as I figure out what I am doing with my life.
Just kidding. Please don't hurt me.
Anyways, the midterm is fast approaching, and proofs will be the death of me. Upon reviewing last year's assignment and midterm, I feel fairly confident. But proofs with multiple quantifiers still confound me. Unfortunately, the assignment this year is one that I find (personally) more difficult to parse than last year's version. My way of approaching proofs with multiple quantifiers, with variables appearing in the statement out of the order in which they have been quantified, is to first pray that it's an epsilon delta proof, and then to assess which variable comes first (epsilon or delta). Whichever variable appears second "wins". That is my only approach. THE END.
... Okay clearly that will not help me. But one can dream.
Claim 1.2 appears to be very similar to a delta epsilon proof. However, the quantifiers are placed out of order, so I'm a little lost
I will update as soon as I figure out what I am doing with my life.
Saturday, October 25, 2014
Proving a Proof
Tips and tricks!
Whenever you introduce a let statement in a proof (when you pick a variable), conclude the end of that margin with an existential.
Whenever you introduce a generic variable , conclude the end of that margin with a universal.
Brief review of floors:
- The floor of x is the largest integer that is less than or equal to x.
- The floor of x is not a variable. It is a function, and quantifiers only apply to variables, so you cannot use a quantifier directly on floor.
Definition of floor:
Assume y is an int. Then y is less than or equal to x. Among all ints that are less than or equal to x, y is the LARGEST.
Note that the symbolic definition of floor and the english definition of floor are equivalent; one is just simpler to parse as a native english speaker.
Whenever you introduce a let statement in a proof (when you pick a variable), conclude the end of that margin with an existential.
Whenever you introduce a generic variable , conclude the end of that margin with a universal.
Brief review of floors:
- The floor of x is the largest integer that is less than or equal to x.
- The floor of x is not a variable. It is a function, and quantifiers only apply to variables, so you cannot use a quantifier directly on floor.
Definition of floor:
Assume y is an int. Then y is less than or equal to x. Among all ints that are less than or equal to x, y is the LARGEST.
Note that the symbolic definition of floor and the english definition of floor are equivalent; one is just simpler to parse as a native english speaker.
Tuesday, October 21, 2014
Encountering failure.
" So why do I talk about the benefits of failure? Simply because failure meant a stripping away of the inessential. I stopped pretending to myself that I was anything other than what I was, and began to direct all my energy into finishing the only work that mattered to me. Had I really succeeded at anything else, I might never have found the determination to succeed in the one arena I believed I truly belonged. I was set free, because my greatest fear had been realised, and I was still alive, and I still had a daughter whom I adored, and I had an old typewriter and a big idea. And so rock bottom became the solid foundation on which I rebuilt my life.
You might never fail on the scale I did, but some failure in life is inevitable. It is impossible to live without failing at something, unless you live so cautiously that you might as well not have lived at all – in which case, you fail by default."
- J.K. Rowling
It's odd to discuss failure in a CSC165 post given that my grade in the course is currently above 99%. (This is not gloating-- as I am wholly aware that this mark will plummet after I encounter what is next to come. Guaranteed. This becomes more obvious as this post goes on.) However, I live in perpetual fear that I will be discovered to be a "fraud". I am impossibly bad at math, and it is a constant, pulsatile reminder; that I am attending a university revered for it's difficulty, in a faculty renowned for its focus on computation, mathematics, and logic. Today, a post on the UofT Computer Science FB page further perpetuated this fear. To hear that the difficulty of Computer Science rises disproportionately each year was a shock in and of itself. A friend at Waterloo's program had said that he had found his first few years in Computer Science to be the most difficult. Whether or not the difficulty of the program increases as the years progress, regardless of my weaknesses in math, I will continue to press on -- to learn more about the things that I am passionate about. Life is a continuous struggle to reach the goals we set for ourselves. I am finally learning things that I am passionate about. Although I am at a disadvantage in terms of my learning background, and the years that I have had away from my math, I am confident that I am well versed in the art of Try-Harding. I spent so much time being disinterested in the things that I-did-not-want-to-do, that my second time around in a post-secondary institution has been all about spending all of my time studying-the-things-that-i-want-to-do. Even so, I ultimately decided to drop MAT223 this semester. This is the first time in my academic career that I have ever dropped a course. My first true encounter with failure. However, it made me realize that my desire to do well, and my efforts to do well, were not entirely realistic. Majoring in a field completely void of the mathematics, and working in a hospital for a year and a half is not conducive to writing algebraic proofs. We're not in Kansas anymore. It's time to start from square one in terms of math. To learn from the beginning, and to learn it well. At first, I was ashamed. Now? I am determined.
It is currently 3 AM. Further updates will be made this week as I pursue the dread mathematical proofs and the big-Oh(my god).
It is currently 3 AM. Further updates will be made this week as I pursue the dread mathematical proofs and the big-Oh(my god).
Wednesday, October 8, 2014
Slog: Week 5: Happy Ending... for now.
Greetings, audience.
This blog feels more and more like an intimate space for my inner thoughts about CSC165. Mostly because it often feels like I have 0 traffic and 0 post views (literally, I actually do). That's okay though. The company of me, myself, and I is more than enough. I mean, three is a crowd, right? There's some kind of english proverb about three being a crowd, no? *crickets chirping*
Moving on, then.
Today was the day of reckoning; a true test of skill. Yes, today was CSC165's Test 1 day. Armed with a double-sided, size 6 font cheat-sheet, I went into the test feeling overwhelmed, and frightened. I left feeling... ecstatic? Today was like the culmination of all of the concepts that I had been struggling with. However, the difference was that the test was formatted in such a way that it was very reflective of the practice test that Professor Heap had provided us with. It was more than fair, and still very challenging -- especially to people who were not prepared. However, it was very do-able to the people who had prepared by reviewing lectures, assignment one, past tests, and the course textbook. Kind and benevolent Heap. Compassionate Heap. Danny? Can I call you Danny?You took pity on these pathetic, miserable First Years, and you showed them the light. Hurrah.
For my cheat sheet, I prepared by consolidating information from all of the above mentioned resources, and doing my best to categorize this information by subject and concept. I included explanations or simple english translations of each law, including Transitivity, which ended up not being on the test. I feel that, despite not being on the test, that I have a stronger grasp of Transitivity. I do not regret spending time on this concept. YOLO.
I found that one of the questions on the test was very reflective of question 4 of Assignment 1. I had already had a strong grasp on the concepts of proving or disproving existential and universal statements, so this question ended up being very straightforward. In summary:
To prove a universal statement: you must prove that every element is an example -- that there is no counter example.
To disprove a universal statement: you must provide at least a single counter-example
To prove an existential statement: you must provide a single example
To disprove an existential statement: you must prove that every element is a counter-example -- that there is no example.
I believe that it's very important to be able to visualize statements in terms of sets -- to be able to determine whether proving a statement implies that a set must be occupied, or that a set must not be occupied. Not because every statement should be interpreted as a set -- but because it is important to be able to determine how to prove a statement true or false, and this is glaringly obvious with the aid of sets, especially at an introductory level. It is another aid to ensure that you are interpreting and understanding logical statements correctly. This concept becomes increasingly more difficult with the introduction of multiple quantifiers and multiple predicates.
Another concept on Test 1were the concepts of logic in Python (programming language). In summary:
(True not in ____) is logically equivalent to (not any ____)
- True not in = there is no true example, all are false
- This is similar to saying "all are not", "none are true", "not any"
- For all, not P(x)
(False not in _____)is logically equivalent to (all _____)
- False not in = there is no counter-example, all are True
- This is similar to saying "all are true", "none are false"
- For all, P(x)
(False in ____) is logically equivalent to (not all ______)
- This is similar to saying "there are some that are not", "there is a False", "not all are"
- There exists x such that P(x) is False
(True in ______) is logically equivalent to (any _____)
- This is similar to saying "There exists at least one example", "Any"
- There exists x such that P(x) is True
Therefore,
- not in = universal quantifier.
- in = existential quantifier
- any/not all = existential quantifier
- all/not any = universal quantifier
Another way to think about this: In English, when you ask someone about the existence of midnight snacks, you can phrase the question in a variety of ways:
"Are there any chips?" ---> any: is there at least one bag of chips? at least one example
"Aren't there any chips?" ---> not any: there are no chips? no example
"You ate all of the chips" ---> all: all of the bag were eaten, without any exception. the entirety. no counter-example.
"So, what you're saying is that not all of the chips were eaten" ---> not all: there is at least one counter-example. Yay! a bag of chips.
I think the moral of the story is that there better be some leftover chips. Or something like that. Overall, today was a lovely day. I will celebrate by eating copious amounts of junk food, and studying for my linear algebra quiz tomorrow. A quiz that I will most likely fail, because I have neglected it in lieu of studying for 165. Curses.
This blog feels more and more like an intimate space for my inner thoughts about CSC165. Mostly because it often feels like I have 0 traffic and 0 post views (literally, I actually do). That's okay though. The company of me, myself, and I is more than enough. I mean, three is a crowd, right? There's some kind of english proverb about three being a crowd, no? *crickets chirping*
Moving on, then.
Today was the day of reckoning; a true test of skill. Yes, today was CSC165's Test 1 day. Armed with a double-sided, size 6 font cheat-sheet, I went into the test feeling overwhelmed, and frightened. I left feeling... ecstatic? Today was like the culmination of all of the concepts that I had been struggling with. However, the difference was that the test was formatted in such a way that it was very reflective of the practice test that Professor Heap had provided us with. It was more than fair, and still very challenging -- especially to people who were not prepared. However, it was very do-able to the people who had prepared by reviewing lectures, assignment one, past tests, and the course textbook. Kind and benevolent Heap. Compassionate Heap. Danny? Can I call you Danny?You took pity on these pathetic, miserable First Years, and you showed them the light. Hurrah.
For my cheat sheet, I prepared by consolidating information from all of the above mentioned resources, and doing my best to categorize this information by subject and concept. I included explanations or simple english translations of each law, including Transitivity, which ended up not being on the test. I feel that, despite not being on the test, that I have a stronger grasp of Transitivity. I do not regret spending time on this concept. YOLO.
I found that one of the questions on the test was very reflective of question 4 of Assignment 1. I had already had a strong grasp on the concepts of proving or disproving existential and universal statements, so this question ended up being very straightforward. In summary:
To prove a universal statement: you must prove that every element is an example -- that there is no counter example.
To disprove a universal statement: you must provide at least a single counter-example
To prove an existential statement: you must provide a single example
To disprove an existential statement: you must prove that every element is a counter-example -- that there is no example.
I believe that it's very important to be able to visualize statements in terms of sets -- to be able to determine whether proving a statement implies that a set must be occupied, or that a set must not be occupied. Not because every statement should be interpreted as a set -- but because it is important to be able to determine how to prove a statement true or false, and this is glaringly obvious with the aid of sets, especially at an introductory level. It is another aid to ensure that you are interpreting and understanding logical statements correctly. This concept becomes increasingly more difficult with the introduction of multiple quantifiers and multiple predicates.
Another concept on Test 1were the concepts of logic in Python (programming language). In summary:
(True not in ____) is logically equivalent to (not any ____)
- True not in = there is no true example, all are false
- This is similar to saying "all are not", "none are true", "not any"
- For all, not P(x)
(False not in _____)is logically equivalent to (all _____)
- False not in = there is no counter-example, all are True
- This is similar to saying "all are true", "none are false"
- For all, P(x)
(False in ____) is logically equivalent to (not all ______)
- This is similar to saying "there are some that are not", "there is a False", "not all are"
- There exists x such that P(x) is False
(True in ______) is logically equivalent to (any _____)
- This is similar to saying "There exists at least one example", "Any"
- There exists x such that P(x) is True
Therefore,
- not in = universal quantifier.
- in = existential quantifier
- any/not all = existential quantifier
- all/not any = universal quantifier
Another way to think about this: In English, when you ask someone about the existence of midnight snacks, you can phrase the question in a variety of ways:
"Are there any chips?" ---> any: is there at least one bag of chips? at least one example
"Aren't there any chips?" ---> not any: there are no chips? no example
"You ate all of the chips" ---> all: all of the bag were eaten, without any exception. the entirety. no counter-example.
"So, what you're saying is that not all of the chips were eaten" ---> not all: there is at least one counter-example. Yay! a bag of chips.
I think the moral of the story is that there better be some leftover chips. Or something like that. Overall, today was a lovely day. I will celebrate by eating copious amounts of junk food, and studying for my linear algebra quiz tomorrow. A quiz that I will most likely fail, because I have neglected it in lieu of studying for 165. Curses.
Monday, October 6, 2014
Emergency Update
Captain, the sink is shipping.
I have yet to to be able to consistently analyze and interpret statements with multiple quantifiers. This is particularly the case when the operands are not presented in the order that they were introduced, or when the operand appears in multiple instances.
I attended a help session at the Undergraduate Computer Science Help Centre, and with the kind assistance of TA, I was able to understand one of the examples for a whole... 2 hours. Any attempts to recollect this session have been unsuccessful. All that remains of my momentary success are unintelligible scribbled notes on 2 sheets of paper. Disaster.
Abort! Abort! The midterm is on Wednesday!!
I have yet to to be able to consistently analyze and interpret statements with multiple quantifiers. This is particularly the case when the operands are not presented in the order that they were introduced, or when the operand appears in multiple instances.
I attended a help session at the Undergraduate Computer Science Help Centre, and with the kind assistance of TA, I was able to understand one of the examples for a whole... 2 hours. Any attempts to recollect this session have been unsuccessful. All that remains of my momentary success are unintelligible scribbled notes on 2 sheets of paper. Disaster.
Abort! Abort! The midterm is on Wednesday!!
Friday, October 3, 2014
SLOG 3: Week 4
Today, the first assignment for CSC165 was due. For the assignment, I used LaTex to produce mathematical statements for the first time. Overall, it was an interesting experience, and I hope to continue to learn more about LaTeX and become more versed in this program.
A realization that I came to this week was that, although I'm struggling in this course, I'm not alone in this struggle. While discussing the assignment with students, and attending today's lecture, I became significantly more confident in my capabilities. Grasping some of the concepts in CSC165 has been a uphill climb, and there are often times that I had wondered if I was hopelessly alone in my incompetency. However, hearing that many other students were stuck on some of the same things that I had been stuck on a week ago was heartening, and has given me newfound confidence.
The midterm next week will allow us the aid of an 8.5x11" double sided cheat-sheet. I am both excited and nervous that the midterm will be testing us on our capacity to produce and comprehend logical statements, rather than brute memorization.
I will most likely update this blog with another post in the upcoming days as the day of the midterm approaches. Winter is coming.
Sunday, September 28, 2014
SLOG 2: Week 3
This week in CSC165, we're continuing to utilize quantifiers to make universal and existential claims. However, we're now discussing the topics of conjunction, disjunction, negation, and implication. I'm still finding it difficult to convey human thoughts and expressions into mathematical ones, especially given that there are multiple formats that we can express these ideas.
Set notation, predicates, and implications are all used to produce mathematical statements. Thus far, we have been proving equivalencies using both truth tables and logical arithmetic. I have found the Table 2.17 on pg 29 of the course notes for CSC165 to be invaluable in keeping me on track with answering tutorial and assignment questions.
Some realizations that I have made include: the equivalency of an inverse (not A implies not B) to a converse (B implies A). I have also come to realize that a contrapositive (not Q implies not P) is equivalent to P implies Q.Some goals I hope to accomplish over the course of the next few weeks:
1) Becoming more adept at proving equivalencies.
2) Being able to recognize equivalencies that are listed in Table 2.17 on sight
3) Allow myself to think more intuitively so that CSC165 is less of a challenge
Wednesday, September 17, 2014
SLOG 1: Week 2
Needless to say, the past two weeks have been a tumultuous start to my my undergraduate career. In summary: relearning old material, and learning new material -- with a dash of chaos and disorder mixed in between.
I am taking CSC165 in conjunction with a couple of other related courses. The classes that I find most relevent are CSC108(Intro to Computer Programming) and MAT223(Linear Algebra I). CSC165 places an emphasis on logical thought and reasoning: it is about expressing yourself precisely and without ambiguity, utilizing mathematical notation to communicate yourself. CSC108 is also focused on expressing human ideas in a new computer language(Python). Alternately, MAT223 is not about converting human ideas and expressions into a new "language"; instead, we are learning about utilizing echelon matrices to convert mathematical equations into a form in which we can easily solve a system of linear equations. Although I do not know enough about my courses to accurately represent or summarize them in their entirety, these are my initial impressions of these courses.
It can be a little difficult to wrap my head around these concepts, and I am continually learning that the concepts that I thought I understood during lectures are actually a complete mystery to me outside of lecture. My plan of action: review until I hammer the concepts down.
I am taking CSC165 in conjunction with a couple of other related courses. The classes that I find most relevent are CSC108(Intro to Computer Programming) and MAT223(Linear Algebra I). CSC165 places an emphasis on logical thought and reasoning: it is about expressing yourself precisely and without ambiguity, utilizing mathematical notation to communicate yourself. CSC108 is also focused on expressing human ideas in a new computer language(Python). Alternately, MAT223 is not about converting human ideas and expressions into a new "language"; instead, we are learning about utilizing echelon matrices to convert mathematical equations into a form in which we can easily solve a system of linear equations. Although I do not know enough about my courses to accurately represent or summarize them in their entirety, these are my initial impressions of these courses.
It can be a little difficult to wrap my head around these concepts, and I am continually learning that the concepts that I thought I understood during lectures are actually a complete mystery to me outside of lecture. My plan of action: review until I hammer the concepts down.
Subscribe to:
Posts (Atom)