Problem-Solving, Part 3.

I knew that the DFSA would have to have exactly 16 states, and that each would correspond in some way to one of the binary strings of length 4. Establishing what the tree would look like  without the branching going from the accepting states was easy - a first state for the empty string/1111-string, and then another state for when we start to build the string whose fourth-last bit is 0. At this point, we know that we need another three bits to reach an accepting state, and at each new bit, that bit could either be a 0 or a 1. So, after the initial 0, there are two branching of from that one (0 and 1), then two for each of those two, then two for each of those two so that we get to all 8 accepting states (there are 8 length-4 binary strings that begin with 0, or half of them, because the other half must start with 1).

The real issue was in reasoning out how to build from any one accepting state. Once we had a string that ended in 0000, what would happen if we added a 1 to make it end in  0001, or another 0 to have it remain 0000? The 0000 would stay at the same state, so I have an arrow labelled 0 looping back to 0000. Then, an arrow labelled 1 going from the state 0000 to the state 0001. Any string that, with a bit added, still had its 4th last bit as 0 was easy to figure out - just go from one accepting state to the next.

The more difficult cases were the ones like 0100. If I add another bit to that, the new string no longer goes into an accepting state. Where does it go? Here is where I had to really think about my state invariants. What defines states q0-q7, the non-accepting states? I decided to define them by the certainty of their sequence of bits as it relates to their distance from an accepting state (because we know that once we have a 0, it is three bits away from an accepting state). So, what we know about q0 is that any string residing there has 1 as a fourth-last digit, and is at least 4 transitions away from an accepting state, because it will need at least 4 bits added because its fourth-last digit isn't 0. So, the state invariants are as follows...

q0 - fourth-last bit definitely isn't 0. Definitely needs at least 4 bits until it reaches an accepting state, but we don't know what any of those bits will be. This is the start state, as this applies to the empty string as well.

q1 - fourth-last bit, once we reach an accepting state, will definitely be 0. Needs at least 3 more bits to hit an accepting state, but we don't know what those three bits will be.

q2 - last two bits, once we reach an accepting state, will definitely be 01. Needs at least 2 more bits to hit an accepting state, but we don't know what those two bits will be.

q3 - last two bits, once we reach an accepting state, will definitely be 00. Needs at least 2 more bits to hit an accepting state, but we don't know what those two bits will be.

q4 - last three bits, once we reach an accepting state, will definitely be 011. Needs at least 1 more bit to hit an accepting state, but we don't know what that bit will be.

q5 - last three bits, once we reach an accepting state, will definitely be 010. Needs at least 1 more bit to hit an accepting state, but we don't know what that bit will be.

q6 - last three bits, once we reach an accepting state, will definitely be 001. Needs at least 1 more bit to hit an accepting state, but we don't know what that bit will be. 

q7 - last three bits, once we reach an accepting state, will definitely be 000. Needs at least 1 more bit to hit an accepting state, but we don't know what that bit will be.

q8 - last four bits are 0111. Accepting state.

q9 - last four bits are 0110. Accepting state.

q10 - last four bits are 0101. Accepting state. 

q11 - last four bits are 0100. Accepting state.  

q12 - last four bits are 0100. Accepting state.

q13 - last four bits are 0010. Accepting state.  

q14 - last four bits are 0001. Accepting state.

q15 - last four bits are 0000. Accepting state.   

So, when we run into a situation such as 0100 with 1 added, what do we do with it? Its last four bits are 1000, so its third-last bit is 0. That means it needs one more bit added to reach an accepting state, so we choose among the states where 1 more bit needs to be added before an accepting state is reached. 1000 will reach an accepting state in one bit, so its "last three bits once we reach an accepting state" are definitely 000, which is state q7. Then, depending on whether a 1 or a 0 is added, it will hit accepting state q14 or q15.

I used this reasoning to finalize the DFSA and add all the transitions coming out of each accepting state, whether a 0 or a 1 is added. No one state has two transition arrows going into the same state, which is in accordance with the proof we wrote for assignment 3.

From Polya's method...

Looking Back

• Fourth. Examine the solution obtained.
• Can you check the result? Can you check the argument? 
• I checked all 16 binary strings of length 4, either by building from an empty string or by adding a 1 or a 0 to all 8 accepting states - plus the empty string. I might write a proof of the state invariant tomorrow, if I have time - but I feel I have made significant progress on this problem already.
• Can you derive the solution differently? Can you see it at a glance? 
• There may be a different solution, but I feel that this one is elegant (well, if I had better mouse control in MS Paint it would have been, but you can appreciate the branching form despite the jittering) and easy to read. I definitely can't see another one at a glance. You can easily see how each accepting state, as it branches out with a 1 or a 0 being added, transitions to the next available accepting state that hasn't had an arrow pointing back up at it. 
• This problem was interesting in that we were already provided with a lot of structure for it - we proved in assignment 3 that such a DFSA would need at least 16 states, and on the discussion board we were asked to prove that it can have exactly 16 states. If we were asked - draw a DFSA that accepts the language of binary strings whose fourth-last digit is 0, and weren't given any hints about looking at the 16 binary strings of length 4, I would have been a lot more confused by this problem. So, my
• Can you use the result, or the method, for some other problem? 
• I might run into other problems where I can break a seemingly quite complex problem down to a certain small set of binary strings, and look at how changes affect each one in that set. I don't know that the actual result here will be terribly useful, but the method probably will be.

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.