Trying This

As a problem solving exercise, I've started working on the problem in /TryThisProblem on Danny's problem-solving wiki site (https://wwwcgi.cdf.toronto.edu/~heap/cgi-bin/Solvent/wiki.pl?Problem_Solving_Home_Page/TryThisProblem).

I like this problem. As Danny says, good problems fight back. This problem, to me, seems to have a challenging depth to it. It doesn't immediately present me with a fairly clear path of attack. But, it did immediately get me thinking, and really grabbed hold of me.

My first step was to (obivously) read the problem. As I was doing this for the second time, I was noting the problem down on paper, more in my own words. For instance, I defined f(n) more symbolically than is done on the wiki page.

This was done to help me frame the problem, and get the problem set up to use a the "mathematical vocabulary" (if you will) that fits me best.

As I was looking at this problem, the way I had it laid out helped. Examining it, I started thinking a couple main ideas:

• Couldn't a closed form for F(m, n) be found?
  
• Would this hypothetical closed form even help with the main thrust of the problem?
• This "closed" form should have two cases, one for each parity of input n (i.e. one for an even n, one case for an odd n)
• It would be nice to be able to look at the results of each application of f(n) lying underneath F(m, n). The parity of these sub-results, in particular, seemed like a key to a closed form, or at least getting insight into the behaviour of F(m, n)

Trying to start on the road to this closed form, armed with my two cases of input n's, I looked at the results of a single application of f(n), given generalized input n's (one for each case, 2k for even, 2k-1 for odd, where k is in the natural numbers, an k > 0).

With even this starting examination, I felt a wave of insight wash over me. The generalized behaviour of compositions of f(n) started to become quite a bit more clear.

My initial results:

• In the case that n is even, f(n) is either even, or odd. In other words, f(n) produces a natural number greater than 0.
• In the case that n is odd, f(n) is always even. This result was intriguing to me.

So, if n is odd, f(n) then produces an even result. This result, if passed to f(n) again, is subject to the arithmetic of the even branch of f(n). This even branch then produces either an even or odd result.

Now it seems to me that this either even or odd result of f(n) from an even input n can be passed to f(n) again, over and over until f(n) produces an odd result. Passing this result to f(n) again sends it to the odd branch, which produces an even number. Evidently, another application of f(n) to this number starts the process described above again.

The way I think of it is that f(n) takes odd numbers and makes them even, which "bounces" them back to the even branch. This branch then reduces them 1 (the desired condition), or reduces them to some odd number greater than 1. The odd branch makes the number even then "bounces" it back to the even branch. So it appears that we have this interplay, a numerical game of catch between the two branches of the function under repeated the composition used in F(m, n).

So, a closed form isn't so simple, but poking around in the area of that problem at least gave me some somewhat more refined ideas about the main problem.

And that's as far as I've gotten. I know it's not much, but it feels like this exercise was already a valuable experience. And hopefully what I've written above doesn't come across as rambling overmuch. What I described was the thought process I went through.

If I can, I will make another post if I make progress on this problem.

The Last Stretch

I've now found that my optimism on heading into the last segment of the course was warranted. As I mentioned in my last post, despite some trouble with test 2, my grasp and enjoyment of formal languages, FSAs and further course material has been encouraging.

I think part of my enjoyment of this material comes from the difference in feel of reasoning about symbols and strings instead of simply numbers. Don't get me wrong, there is always an appeal to a precise proof in a more typical mathematical domain. But reasoning with language just seems refreshing.

Regex's, in their practical usage, have been a favourite of mine for some time. The theoretical variety of Regex's we studied in 236 is seemingly not so distant from the practical sort. This similarity really helped to engage me in the material.

When it comes to FSAs, I would almost say they have a certain graphical or mechanical appeal.
Reasoning using the machinery of an FSA is fun. I think it's fun in the sort of way a mechanical contraption is. The FSA graphical simulators available on the web, and demonstrated by Danny in lecture, only add to the more tangible aspect of FSAs.

Now, for the validation of my optimism. Assignment three and test three proved to be satisfying. They both involved a fair amount of effort, but I didn't feel too stumped, and enjoyed the level of challenge of both their sets of questions.

Specifically, I found the test to be quite fair. I'd like to discuss the question about proving that a Regex without a union operator denoted a language of length zero, one or infinity. Thinking about the implications of using each allowed operator, that is, concatenation and kleene star, on their own, along with looking at base cases for possible input strings gave me an intuition on how to structure my proof. This intuition came to pretty quickly after following this line of reasoning. Splitting the proof into cases of just concatenation being used, and then a case for using kleene star allowed me to delve into the language-length implications of either operator. And of course the implication of a blank regex on its denoted language's length seemed fairly trivial.

All in all, I'm happy with my experience with the last part of the course! Enjoyable material coupled with very reasonable work made it fun... relatively speaking, in terms of a university course.

Recovery from the Second Test Through Formal Languages

The second test was not especially kind to me. Or, in other words, I did not do a very good job of writing the test. I felt like I knew and genuinely understood the material well. Also, I entered this test with a certain confidence, since I had received a good mark on the first test. Somehow, both of these factors did not translate into a mark I would even call mediocre. I fared poorly, and it came as a bit of a surprise.

The learning experience that I will take out of this instance of underwhelming performance is that a comfort with material cannot beat the mastery of it that comes with repeated, extensive practice. If I had practiced a variety of questions, I do have a feeling that I would have accomplished on par with my expectations.

Moving past the disappointment, I am enjoying getting a grasp on formal languages and FSAs. With formal languages in particular, I was a bit worried that proofs involving them would cause me trouble. Their structural, less algebraic proof techniques seemed to some extent unnatural to me initially. Seeing formal language proofs in lecture was a start, and definitely did help. But working on the small yet valuable problem sets that have involved formal languages has really helped me hone my reasoning regarding them. The review of lecture slides and the course reader that accompanied completing the problem sets was a large part of what made the experience so valuable.

With all that said, I can say in summary that it's nice to feel like I'm back on my feet in 236, despite the setback of my last test's results.

First Test

To be honest, I was somewhat stressed-out over the first test. I tried to start studying reasonably far ahead of time, but kept getting thrown off track. I'm not sure if it was a bit of laziness or an inability to properly fight distraction, or both, but staying on task proved difficult. Maybe my trouble focusing came out of an abundance of preparation by means of the problem sets and the first assignment.

Now that, just this evening, I have received my marked test back, I do think that the homework prepared me well. It feels as if through Danny having us do exercises in class, our regular problem sets, and the assignment, we're really set up for success in this class. The regularity of the marked work required of us annoyed me to some extent at first. I was looking for time off 236! But, after throwing myself into the necessary rhythm of the course, I find that doing less work at once, but doing it more often is less of an annoyance. This is because I'm now used to it, and I really don't mind the problem sets in particular, because they're short, but still a valuable nugget of a learning experience.

And so, back to the test itself, I'd have to say I'm pleased with how it went. My mark was not perfect, but I got a grade I'm quite happy with. The markers were generous, fair, and their feedback made me think about the questions after getting the test back. I asked Danny about a couple notes the marker left on a certain question. This lead to Danny going over the slight issues with my proof, which turned into another chance for me to learn. After we finished our discussion, I really felt like I understood a part of base cases and their relationship to the induction step and induction in general to a greater degree. Instead of just knowing the steps of the tool of induction, and how to use it, we get a handle on the details of what makes induction tick. It's actually very cool stuff.

The Start

Unfortunately, this blog has been created later than I wanted. Upon seeing mention of something called a "SLOG" in the course syllabus, my first thought was "What the hell is a SLOG?" After I got past the unusual terminology, I discovered what seemed like an even more unusual idea: marking university students' reflection on work of a mathematical nature. Caring to this extent about our subjective opinion and personal story, rather than just if our proof had the right steps our or answers being correct - that's something I've never seen before. And I didn't expect it to happen, either.

But between 236 problem sets and all the other regular assignments and work I've been having to do, I slipped on following through with engaging in my end of this unique but welcome idea. Well, here it is. I'm glad that I took the plunge, especially since I'm not much of a blogger nowadays. It's fun. I may tread backwards and reflect on some of my past 236 stories and struggles from the problem sets and assignment, and I hope to post shortly either before and/or after the first test to reflect on it.