Problem-Solving, Part 2.

This is the DFSA, without any state invariants described, because I'm not sure how to articulate them, exactly.

Once a string has gone through an accepting state, and it has another bit added, this DFSA shows what state that new string will go into. For example, if 0000 has a 1 added, its last four bits will be 0001, so it goes to the state where the last four bits are 0001.

I will elaborate further on how I developed this, in the next entry.

Problem-Solving Exercise, Part 1.

I have decided to draw the 16-state DFSA from A3, Q1, instead of the difference engine I said I was going to take a look at. I don't know if I'll have time for the difference engine, and I had already completed most of this before I realized that I could do this for the problem-solving exercise. I'll scan some of the process work I did in pencil, but I've redrawn it on the computer.

1. UNDERSTANDING THE PROBLEM
   • What is the unknown? What are the data? What is the condition? 
   • I know that I have to come up with a 16-state DFSA that describes the language of binary strings whose fourth-last bit is 0. I do not know, at first, how the states will be connected, especially once they branch out after an accepting state has been reached. Each state has to have an edge labelled 0 and an edge labelled 1 coming from it, because every binary string can be made bigger by a 1 or a 0 added, and this DFSA has to handle all possible binary strings.
   • Is it possible to satisfy the condition? Is the condition sufficient to determine the unknown? Or is it insufficient? Or redundant? Or contradictory? 
   • Yes, I believe intuitively that this is possible, especially since we need to prove in assignment three that no DFSA with less than 16 states can handle this language. I know that I can only have 16 states, so it is just a question of how to connect them.
   • Draw a figure. Introduce suitable notation. 
   • Figures will be provided as they evolve, in each entry.
   • Separate the various parts of the condition. Can you write them down? 
   •  The condition is the entire DFSA.
2. DEVISING A PLAN
   • Second. Find the connection between the data and the unknown. You may be obliged to consider auxiliary problems if an immediate connection cannot be found. You should obtain eventually a plan of the solution.
   • Have you seen it before? Or have you seen the same problem in a slightly different form? 
   • We have handled many binary-string DFSAs in class and tutorial. The problem is loosely related.
   • Do you know a related problem? Do you know a theorem that could be useful? 
   • All of our binary string problems have been related, in a way, because many of them deal with binary strings that may be repeatedly accepted as they grow. I cannot think of any theorems I would apply now. 
   • Look at the unknown! And try to think of a familiar problem having the same or a similar unknown. 
   • I don't know that we have ever been given a problem where we need to construct a DFSA with a precise number of states.
   • Could you restate the problem? Could you restate it still differently? Go back to definitions. 
   • I feel it's pretty clear.
   • If you cannot solve the proposed problem try to solve first some related problem. Could you imagine a more accessible related problem? A more general problem? A more special problem? An analogous problem? Could you solve a part of the problem? Keep only a part of the condition, drop the other part; how far is the unknown then determined, how can it vary? Could you derive something useful from the data? Could you think of other data appropriate to determine the unknown? Could you change the unknown or data, or both if necessary, so that the new unknown and the new data are nearer to each other? 
   • At first I had trouble connecting the accepting states to further elaborations, so I just drew the DFSA below, which is incomplete. I did not know at first how to handle any strings longer than length 4, who have already had a previous section of themselves in an accepting state.
   • Did you use all the data? Did you use the whole condition? Have you taken into account all essential notions involved in the problem? 
   • In the figure below, no. It only works for strings who have not yet gone through an accepting state.

This was my first attempt at the DFSA. It has 17 states because I wasn't sure yet how I would handle a string where the fourth-last bit wasn't 0, so I did a separate state for that, and for an empty string, which I later realized could be combined (states q0 and q16). The DFSA in this image isn't complete because at first I wasn't sure how I would connect the accepting states if they had bits added, for example, this DFSA handles every binary string of length 4 whose first digit is a 0, but it can't handle any longer strings that are build from previously accepted strings, like 00001 - I didn't know at first where the arrows from the accepting states would be going.

We experienced a tutorial shift last week and I got a taste of what it's like to come into a quiz barely prepared. I read the section in the Course Notes about DFSAs before office hours on Thursday, but I found it completely overwhelming and I wasn't certain of how detailed the tutorial questions were asking us to be. During office hours I learned that we were only then responsible for the diagram, not the quintuple function, and I understood the lecture material and my answers during tutorial ended up being correct, so I'm hoping I got the 2/2 on the quiz.

The material from chapter 7 is coinciding nicely with a short lesson we had on regular expressions in CSC207. I still haven't taken a close look at how Java implements regular expressions, but now that I can visualize them using the DFSAs, I feel like I understand them a lot better.

I'm glad the third assignment has a lot of work on correctness, because that is something that is currently very difficult for me. Surprisingly, though, even though I pulled most of my test answer for the correctness question out of a hat, I didn't do poorly on it. What really lowered my grade was the last question - I still think it was a really bizarre question to have worth four marks, especially when there were so many other things we've learned since the last test that we could have been tested on. I'm not going to ask for a remark because I really have no argument for one but I'm still really, really disappointed.

As for the assignment, I got exactly the mark I thought I would - I lost one mark for the explanation of why my recurrence correctly counted the number of OMCOFS. I did not feel confident in my answer and I learned from the marking that I had just approached it in the wrong way. My response was rambling and unstructured and I totally deserved that mark off.

Beginning the Problem-Solving Excursion

I'm starting to take a look at the Polya problem-solving process and the exercises on the Wiki. I'm looking over the previous students' solutions, not carefully to copy them but to just get a sense of the general formats they've used to solve them (this way I can also tell which ones are more difficult and therefore have longer solutions). I think I might try the Sums of Differences problem, because I've always been meaning to learn more about Charles Babbage's work, but have never gotten around to it - I hope I can make significant progress on the problem and get a better understanding of the problem that inspired him to start working on the first primitive computer.

As far as the last test is concerned, I'm hoping for a...grades shift. I took a look at the correctness slides before the test, but because we didn't have a tutorial or any assignment questions related to recursive correctness, I wasn't anticipating 50% of our test to be based on it. I completed the question as best I could, though I won't be surprised at a failing grade. Also, the final question - I don't really understand why it was worth four marks. I had never seen a question like that before, and though I almost got the right answer (I put the power of 2 in the wrong place), I don't know how we would have shown our work for it? A few students wrote down a solution where they used a temporary variable, but I had never seen anything like that before in programming (reducing a recursive call in that way) and there was no way I could have come up with such a thing. I understand how a solution like that would have merited four marks, but that isn't something we could have studied. Most of the things I did study, however, didn't appear on the test at all, including coming up with a closed form, proving the closed form by induction, and doing upper and lower bounds. I feel like I really wasted a lot of time going over old tutorials and the assignment - the only thing I recognized on the test was the Master Theorem, but that really wasn't something that required a lot of studying.

Anyway, I was so tired and distressed after the test that I didn't really pay attention to what was going on in lecture. The annotated slides from last week aren't up yet, so I'll have to read through the course notes carefully. I'm looking at sections 7.1 and 7.3 - it looks like we'll be using structural induction quite a bit, which is something I haven't had any practice with whatsoever. I'm in the evening section, it was the morning section that had it on their first test, and we haven't seen it in assignments nor in tutorials, so I'm glad I'll be able to understand it better with these new applications now.

It looks like we're not doing any tutorials on correctness? That's a shame, because that was something I felt I had a really good grasp on in CSC165, but with all of these new elements added onto it this year, I would really like to be able to get some practice on it, especially for iterative programs. I hope, then, that it will either be on the assignment, or that the exam won't have any big questions on proofs of correctness, just to balance out that horrible test.

I completed my assignment last Friday  with a few hours to spare. I don't think I will do as well on this one as I did on the first one, because there were a couple of points I felt uncertain about. I don't want to look at the sample solution quite yet, just out of nervousness (I'll have to look at it before the test, though), but I'm wondering now whether I did the upper/lower bound section correctly. I followed the general format of what we did in lecture, but I'm still worried about it.

Consistently, the number one issue I have with proofs is manipulating algebra, particularly in cases where there is a very simple mathematical rule that leads to a clean solution, that I am not aware of. This popped up again in the assignment when we were adding together the two instances of the closed form for the Fibonacci, one to the power of n and the other to the power of (n - 1). I destroyed...many pages in my notebook trying to fiddle around with powers and dividing and multiplying and expanding and factoring in different ways and I just could not figure out how to get to the final step in the algebra. I knew that there must be a simple solution, the proof couldn't possibly be so long, so I felt pretty ridiculous. I went to office hours and asked about it and another student pointed out that ϕ to the power of 2 is just (ϕ - 1). I had no idea (I should have read the textbook more carefully, hah). Within three or four steps, the algebra resolved itself neatly and I had completed my proof. 

Similar things have happened to me in the past, especially while manipulating logs. I didn't take Calculus or Advanced Functions when I was in Grade 12 because I was not anticipating taking any  hard science courses in university - until I had a change of heart in third year and decided to switch from humanities to computer science.  By then, I hadn't taken any math courses in six years, and I had to take those Grade 12 credits in night school. I was out of practice with these things for many years, and I still haven't taken first-year Calculus, so these skills are still pretty rusty for me. This is probably why I have trouble with chains of inequalities, too. There is usually some kind of elegant solution that completely evades me.