Really cool class today on developing a systematic approach to problem solving - working with determining the pattern of creases in a folded strip of paper. It produces a sequence as expressed in this Wikipedia article: http://en.wikipedia.org/wiki/Regular_paperfolding_sequence - which also goes by the more dramatic name "dragon curve sequence," after its similarity to a very beautiful fractal: http://en.wikipedia.org/wiki/Dragon_curve
The problem ultimately was not about the solution but about the process of solving, in a sort of "the journey is more important than the destination" scenario, so I won't go into what the solution actually is, although read the article if you want to know. It was a bit amusing that virtually every group proceeded by the same method to finding a solution: examine small cases to establish a pattern, a method hammered in by programming and math classes over the years, and one which I often use in my day-to-day life - for instance, while trying to find a function to represent a curve in a graph, which is essentially the same problem with some slight changes (paper folding has a number of folds n which provides a pattern of two alternating variables, written as 0s and 1s in the Wikipedia article; representing a curve has a group of coordinates - usually two, x and y, but sometimes three, with z added in 3D space - which can be gathered to produce a function of how each variable changes relative to the other(s)).
It made me wonder if our reliance on this method is potentially too lazy: what happens when we come across a circumstance which can't be solved using small cases to establish a pattern? It's difficult for me to even conceive of such a problem, since it would require:
- a large sample
- cases which vary over a great area and seemingly with no pattern
But there's always got to be a pattern, right? Just thinking about something occurring with no resolvable pattern is... scary. I can't imagine we'd come up against something like that in 165, but it's interesting to think about it. How does one solve such a problem?
If there's no pattern, then there can be no general case. So then we aren't dealing with a series or sequence, right? There will be no n which can be adjusted to fit any example.
The whole scenario is so difficult to conceptualize, and I have to wonder if it's worth the trouble. We can't effectively predict what a person will want to do in their life if they are born in this place, in this year on this day of the month, with these people as parents (who have their own lives where we were supposed to have calculated this) and with these people around them who they are likely to interact with and these political, social and economic forces working on their world... we can't even do this effectively if the person was abandoned in the woods.
Moving back to computer science, it raises a question about how do you effectively build AI, which run on pattern recognition and learning from pattern recognition. If your computer butler wakes you up early and you're visibly upset (visible in the sense that the computer butler says, "Oh hey, you are upset,") then the computer butler can use the patterns to determine when is a better time to wake you.
But what should the computer butler do for waking a baby or raising a baby? Could a computer raise a child based on predictions and patterns? What kind of child would that be?
This has shot off into the aether a little, but I suppose the question I'm hopping around is "What is a pattern?" And this little exercise put a really interesting spin on how we try to answer that question. We can look at the little bit of data we have and try to figure out what to do. Then we produce a hypothesis or two, tinker and see if they work, and start over if they don't. If the paper folds aren't in a Fibonacci sequence, then we try a different hypothesis based on where we went wrong. At some point, it should work. It just better be soon.
Friday, September 26, 2014
Thursday, September 18, 2014
Weeks 1 & 2: Return of the Clog!
The CLOG-SLOG is back!
CSC165 has begun, and the change is material is refreshing for now. Given that we haven't really touched much code, I am inclined to believe the course will remain fairly theoretical. So be it. I can handle theory.
The lectures have remained mainly in the field (or Venn diagram, if you will) of logic and Venn diagrams so far. I am familiar with these sorts of techniques from some logic lectures in high school, although there are some differences. Our work has mostly covered "if" at the moment ("only if" just recently reared its head) and "iff" still has a class or two to emerge fully. For now, I've made a small table to help me work through implications. It's neat how different "if" and "iff" ultimately are when determining information from a statement. Observe:
In these tables, we are checking to see whether our implication is TRUE or FALSE each time. What is interesting is that a regular "if" only limits a contradiction - when A occurs but B does not, even though A implies B. Anything goes if A does not occur, as the right column shows.
By contrast, "iff" excludes all results but the implication: B can only happen if A happens first (which is another way of stating "B only if A" - for this scenario at least, and as far as I can tell).
I don't know why the example comes to mind, but I like to consider an apocalyptic prophecy in this scenario. If 2012 or Ragnarok is upon us, then everyone will die very quickly. That's an "if" statement, and if 2012 or Ragnarok is NOT upon us (~A), then...?
Well, there are other ways to have everyone die very quickly. So don't get too hopeful if 2012 or Ragnarok is not upon us: that doesn't mean you're safe - there could be something else brewing. The Rapture, for instance.
The Rapture is a bit more strict compared to 2012 or Ragnarok. If and only if you were a good person while alive, you will go to heaven during the Rapture. If you weren't good enough, tough. Enjoy hell on earth.
One thing about "if" statements is that they can be more precise when there's fewer options. If a bit isn't 1, then it's 0. If a bit isn't 0, then it's 1. This can be used in statements in programs easily: if the value is True, then print "success!" Barring errors, you know that this code won't ever print anything aside from "success!":
def bool_success(value):
"""Return "success!" if value boolean is True."""
return "success!" if value
But again, now the "if" is just functioning as an "iff," since it's waiting for 1 particular possibility to occur. That's how I like to conceive of it: "if" checks for 1 possibility to produce the result, but doesn't care if another possibility triggers it (consider an "elif" statement which produces the same result after an "if", or an "or" statement within an "if"), while "iff" is the only way to get a particular result (all other answers lead elsewhither).
The other area I briefly mentioned that we touched on was Venn diagrams, a very useful tool for visualizing how areas interact. I am enjoying the opportunity to learn the new symbols ("for all" and "there exists," to name two) and the new terminology ("converse", "contrapositive") although I admit it can be disorienting if I lose focus. Nonetheless, all seems to mesh together in a fun set of patterns:
my TA imparted a very useful trick to remember when testing universal or existential claims, which he referred to as "big or small" - distinguishing between when an example or counterexample is needed (just one thing to find!), or when we need to prove no examples or counterexamples exist (check all the things!). This has helped somewhat.
From here on, it will be a matter of seeing how the Venn diagrams can grow more complicated: we've already looked at subsets and intersections - but is there any way a Venn diagram can express an "or" visually?
CSC165 has begun, and the change is material is refreshing for now. Given that we haven't really touched much code, I am inclined to believe the course will remain fairly theoretical. So be it. I can handle theory.
The lectures have remained mainly in the field (or Venn diagram, if you will) of logic and Venn diagrams so far. I am familiar with these sorts of techniques from some logic lectures in high school, although there are some differences. Our work has mostly covered "if" at the moment ("only if" just recently reared its head) and "iff" still has a class or two to emerge fully. For now, I've made a small table to help me work through implications. It's neat how different "if" and "iff" ultimately are when determining information from a statement. Observe:
In these tables, we are checking to see whether our implication is TRUE or FALSE each time. What is interesting is that a regular "if" only limits a contradiction - when A occurs but B does not, even though A implies B. Anything goes if A does not occur, as the right column shows.
By contrast, "iff" excludes all results but the implication: B can only happen if A happens first (which is another way of stating "B only if A" - for this scenario at least, and as far as I can tell).
I don't know why the example comes to mind, but I like to consider an apocalyptic prophecy in this scenario. If 2012 or Ragnarok is upon us, then everyone will die very quickly. That's an "if" statement, and if 2012 or Ragnarok is NOT upon us (~A), then...?
Well, there are other ways to have everyone die very quickly. So don't get too hopeful if 2012 or Ragnarok is not upon us: that doesn't mean you're safe - there could be something else brewing. The Rapture, for instance.
The Rapture is a bit more strict compared to 2012 or Ragnarok. If and only if you were a good person while alive, you will go to heaven during the Rapture. If you weren't good enough, tough. Enjoy hell on earth.
One thing about "if" statements is that they can be more precise when there's fewer options. If a bit isn't 1, then it's 0. If a bit isn't 0, then it's 1. This can be used in statements in programs easily: if the value is True, then print "success!" Barring errors, you know that this code won't ever print anything aside from "success!":
def bool_success(value):
"""Return "success!" if value boolean is True."""
return "success!" if value
But again, now the "if" is just functioning as an "iff," since it's waiting for 1 particular possibility to occur. That's how I like to conceive of it: "if" checks for 1 possibility to produce the result, but doesn't care if another possibility triggers it (consider an "elif" statement which produces the same result after an "if", or an "or" statement within an "if"), while "iff" is the only way to get a particular result (all other answers lead elsewhither).
The other area I briefly mentioned that we touched on was Venn diagrams, a very useful tool for visualizing how areas interact. I am enjoying the opportunity to learn the new symbols ("for all" and "there exists," to name two) and the new terminology ("converse", "contrapositive") although I admit it can be disorienting if I lose focus. Nonetheless, all seems to mesh together in a fun set of patterns:
my TA imparted a very useful trick to remember when testing universal or existential claims, which he referred to as "big or small" - distinguishing between when an example or counterexample is needed (just one thing to find!), or when we need to prove no examples or counterexamples exist (check all the things!). This has helped somewhat.
From here on, it will be a matter of seeing how the Venn diagrams can grow more complicated: we've already looked at subsets and intersections - but is there any way a Venn diagram can express an "or" visually?
Subscribe to:
Posts (Atom)