Well, CSC236 is coming to an end.
I have certainly learned a lot throughout the duration of the course. I began with virtually no clue what induction was, I had never heard of it, now I can confidently say I understand it.The course layout/structure was a good one, kept me honest, if I slacked the work piled up and ended up taking more time. All in all degree aside I am glad I took this course an feel I learned a lot.
Regards,
Carl
Tuesday 4 December 2012
Sunday 25 November 2012
Problem Solving Post
For my problem solving post I decided to complete a problem from the site "cut the knot" as the prof recommended. I surffed around the site trying all the different problems but this particular problem I will provide a solution for, Box Labels, had extra nostalgic value as it reminded me of doing probability problems with hidden objects in boxes back when I was first learning probability.
The problem is described as such:
Each of the three boxes contains 2 balls. In one there are two white balls, in another two black balls, and in the third one ball is black, the other is white. Boxes have been labeled to indicate their contents. However, whoever did the job got all labels wrong. The task is to straighten things out. You may select 1 box and blindly pick up a ball out of it.I will attempt a solution via the G. Polya method.
UNDERSTANDING THE PROBLEM
First I will divide up the question into what I know and what I need to find out.
Given Information >> 3 boxes.1 box labelled 2 blacks denoted from here on out as bb
1 box labelled 2 whites denoted from here on out as ww
1 box labelled1 of each denoted from here on out as bw
All the boxes are labelled incorrectly
I am permitted to choose one ball from one of the boxes and discover it's colour
Unkown >> I must discover which labels belong to which box
Condition >> I am only alowed to see one ball from one of the boxes then must label the boxes . correctly
DEVISING A PLAN
It seems to be the case that if I pick a ball from bb and it is white then I will still be left with the possibilities of either bw or ww, and not tell me the other boxes either. Or if I pick a ball and it is black then it will tell me that the box is bw and the state of the other two boxes.
A similar situation would occur is I choose from ww.
Where as if I pick from the bw box regardless of weather I pick a black ball or white ball it seems to reveal the content of all boxes. So it becmes apparent that I must choose from the bw box, now I set out to prove it by examining all possiblities.
PROOF
Case1
Without loss of generality suppose I pick from bb (ww would represent the same cases)
Case1a
If I pick a ball from bb and it is white it will tell me that the content is either bw or ww, but that doesn't tell me what exactly is in the box nor does it reveal the other boxes only shrink the possibilities.
Case1b
If I pick a ball from bb and it is black it will tell me that the content of that box is bw because it can't be bb due to the label and it then tells me the labels of the other 2 boxes because the remaining labels are bw and ww and the remaining boxes are ww and bb so it is clear to see the bw label will go with the ww labelled box and the ww labeled box will go with the bw label
So case 1 leads me to a 50% chance
Case2
pick from bw labelled box
Case2a
If I pick a ball from bw and it is white it will tell me that the content is ww since it can't be bw by the label and revels the other two boxes must be different from what they are labelled. 2 boxes remaining one labelled ww and one bb and 2 labels ww and bw thus the bb labelled box gets the bw label and the ww labelled box gets the bb.
Case2b
If I pick a ball from bw and it is black it will tell me that the content is bb since it can't be bw by the label and revels the other two boxes must be different from what they are labelled. 2 boxes remaining one labelled bb and one ww and 2 labels ww and bw thus the bb labelled box gets the ww label and the ww labelled box gets the bw
.
So case 2 leads me to a 100% chance
Thus the dominate strategy for correctly labelling is too choose from the bw box.
LOOKING BACK
Taking a step back and examining my proof it seems to hold up. My intuitive thought that I must choose from bw was right !!!!!!!! The Polya strategy is certainly appears to be a good method, especially since it tells you to lay out all the information you have and want so you can set up your goals accordingly.
Carl
The problem is described as such:
Each of the three boxes contains 2 balls. In one there are two white balls, in another two black balls, and in the third one ball is black, the other is white. Boxes have been labeled to indicate their contents. However, whoever did the job got all labels wrong. The task is to straighten things out. You may select 1 box and blindly pick up a ball out of it.I will attempt a solution via the G. Polya method.
UNDERSTANDING THE PROBLEM
First I will divide up the question into what I know and what I need to find out.
Given Information >> 3 boxes.1 box labelled 2 blacks denoted from here on out as bb
1 box labelled 2 whites denoted from here on out as ww
1 box labelled1 of each denoted from here on out as bw
All the boxes are labelled incorrectly
I am permitted to choose one ball from one of the boxes and discover it's colour
Unkown >> I must discover which labels belong to which box
Condition >> I am only alowed to see one ball from one of the boxes then must label the boxes . correctly
DEVISING A PLAN
It seems to be the case that if I pick a ball from bb and it is white then I will still be left with the possibilities of either bw or ww, and not tell me the other boxes either. Or if I pick a ball and it is black then it will tell me that the box is bw and the state of the other two boxes.
A similar situation would occur is I choose from ww.
Where as if I pick from the bw box regardless of weather I pick a black ball or white ball it seems to reveal the content of all boxes. So it becmes apparent that I must choose from the bw box, now I set out to prove it by examining all possiblities.
PROOF
It is clear by the nature of the problem that what ever box I pull a ball from must give me a definitive answer as to what the content of the other boxes are.
Scratch work:Case1
Without loss of generality suppose I pick from bb (ww would represent the same cases)
Case1a
If I pick a ball from bb and it is white it will tell me that the content is either bw or ww, but that doesn't tell me what exactly is in the box nor does it reveal the other boxes only shrink the possibilities.
Case1b
If I pick a ball from bb and it is black it will tell me that the content of that box is bw because it can't be bb due to the label and it then tells me the labels of the other 2 boxes because the remaining labels are bw and ww and the remaining boxes are ww and bb so it is clear to see the bw label will go with the ww labelled box and the ww labeled box will go with the bw label
So case 1 leads me to a 50% chance
Case2
pick from bw labelled box
Case2a
If I pick a ball from bw and it is white it will tell me that the content is ww since it can't be bw by the label and revels the other two boxes must be different from what they are labelled. 2 boxes remaining one labelled ww and one bb and 2 labels ww and bw thus the bb labelled box gets the bw label and the ww labelled box gets the bb.
Case2b
If I pick a ball from bw and it is black it will tell me that the content is bb since it can't be bw by the label and revels the other two boxes must be different from what they are labelled. 2 boxes remaining one labelled bb and one ww and 2 labels ww and bw thus the bb labelled box gets the ww label and the ww labelled box gets the bw
.
So case 2 leads me to a 100% chance
Thus the dominate strategy for correctly labelling is too choose from the bw box.
LOOKING BACK
Taking a step back and examining my proof it seems to hold up. My intuitive thought that I must choose from bw was right !!!!!!!! The Polya strategy is certainly appears to be a good method, especially since it tells you to lay out all the information you have and want so you can set up your goals accordingly.
Carl
Monday 19 November 2012
Post Test2
Well Test 2 and Assignment 2 went surprisingly well, quite the confidence boosters. As the course is progressing I am definitely starting to feel more comfortable writing proofs, which is a good thing because I suppose I'll need them for future courses.
Last class we began learning about languages and alphabets; there seems to be a million definitions- hopefully they don't take too long to memorise. The DFSA accepting states looks interesting and I can see the real life applications.Time to go work on A3.
Carl
Last class we began learning about languages and alphabets; there seems to be a million definitions- hopefully they don't take too long to memorise. The DFSA accepting states looks interesting and I can see the real life applications.Time to go work on A3.
Carl
Sunday 11 November 2012
Test 2
It's hard to say how Test 2 went, I felt as though I provided a sound argument in each proof but I am not sure if it was syntactically right since the topic of correctness is new and we haven't done many examples.
Carl
Carl
Sunday 4 November 2012
Test 2 Approaching
Well assignment 2 is finished- but I have learned not to get too excited; as a chance to rest in this course seems about as likely as a unicorn. As Pachino put it...
http://www.youtube.com/watch?v=UPw-3e_pzqU
And so here we are, Sunday November 4th 2012. After spending all last week cramming for an Economics Test, I spent all weekend cramming for a Math test and, not to be out done of course; now I get to spend the next 3 days cramming for CSC236.
The Test will focus on unit 3 Topics probably including: recursively defined functions, time complexity and unwrapping. Dealing with recursively defined functions during induction and unwrapping shouldn't be overly difficult. Although when it come to time complexity I find that the problems can VERY hard to solve. I am glad we at least have the A2 answers available so we can see the form for Big Θ notation to prepare for the test.
Carl
http://www.youtube.com/watch?v=UPw-3e_pzqU
And so here we are, Sunday November 4th 2012. After spending all last week cramming for an Economics Test, I spent all weekend cramming for a Math test and, not to be out done of course; now I get to spend the next 3 days cramming for CSC236.
The Test will focus on unit 3 Topics probably including: recursively defined functions, time complexity and unwrapping. Dealing with recursively defined functions during induction and unwrapping shouldn't be overly difficult. Although when it come to time complexity I find that the problems can VERY hard to solve. I am glad we at least have the A2 answers available so we can see the form for Big Θ notation to prepare for the test.
Carl
Sunday 28 October 2012
Assignment Two
Assignment two appears to be progressing nicely.
Question#1
The OMCOFS recursive definition ended up being easy to find....once I realised that for string length 5 there is 8, not 7 possibilities (11011 alluded me for a stressful 10min ). Completing the question after that was not exceedingly difficult.
Question#2
Showing the intuitive non-decreasing property was easy. Showing that T(n) is of order log(n) is slightly more difficult for me because I forget how to show Big Theta. Currently I am waiting for the prof to post his most recent lecture notes and I'm sure it will shed a bit more light on the situation or if worse comes to worse I'll have to revisit the the dark, dark abyss; my notes from 165.
On an unrelated note I have noticed that where ever I walk there seem to be stray dogs, so I hypothesised that stray dogs must have at least 3 noses so they can better tell my position and walk near me. And believe it or not I was able to prove it:
Proof. No dog has 2 noses. Since one dog has one more nose than no dog, it must have three noses.
Carl
Question#1
The OMCOFS recursive definition ended up being easy to find....once I realised that for string length 5 there is 8, not 7 possibilities (11011 alluded me for a stressful 10min ). Completing the question after that was not exceedingly difficult.
Question#2
Showing the intuitive non-decreasing property was easy. Showing that T(n) is of order log(n) is slightly more difficult for me because I forget how to show Big Theta. Currently I am waiting for the prof to post his most recent lecture notes and I'm sure it will shed a bit more light on the situation or if worse comes to worse I'll have to revisit the the dark, dark abyss; my notes from 165.
On an unrelated note I have noticed that where ever I walk there seem to be stray dogs, so I hypothesised that stray dogs must have at least 3 noses so they can better tell my position and walk near me. And believe it or not I was able to prove it:
Proof. No dog has 2 noses. Since one dog has one more nose than no dog, it must have three noses.
Carl
Sunday 21 October 2012
We meet again Big O
Ah time complexity,
Seems reasonable that in a course called Introduction to the Theory of Computation we'd examine run-times. I must say although it took a while to grasp in 165 and will probably take an equally long time to RE-grasp in 236 this is a topic I am genuinely interested in. It's nice to know the fewest cuts to break apart chocolate but not actually practical. nor does it have any important implications. Understanding how long a program will take to run on the other hand seems VERY important. I am reminded of a story Diane told us in CSC108 in which her and her colleagues were going to solve a complex problem relating to U of T student data but upon examining the run time it just wasn't feasible.
To help me understand time complexity I decided I would apply it to my everyday life and decided to measure the time complexity of my dinner last night, unfortunately my calculations were off because I kept 'goin back four seconds'.
Carl
Seems reasonable that in a course called Introduction to the Theory of Computation we'd examine run-times. I must say although it took a while to grasp in 165 and will probably take an equally long time to RE-grasp in 236 this is a topic I am genuinely interested in. It's nice to know the fewest cuts to break apart chocolate but not actually practical. nor does it have any important implications. Understanding how long a program will take to run on the other hand seems VERY important. I am reminded of a story Diane told us in CSC108 in which her and her colleagues were going to solve a complex problem relating to U of T student data but upon examining the run time it just wasn't feasible.
To help me understand time complexity I decided I would apply it to my everyday life and decided to measure the time complexity of my dinner last night, unfortunately my calculations were off because I kept 'goin back four seconds'.
Carl
Subscribe to:
Posts (Atom)