Polya problem solving

Question (From week 10 lecture):

If L1 is the set of binary strings with an even number of zeroes, and L2 is

the set of binary strings with an odd number of 1s, can you express L1 /\ L2 as a regex?

1) Understand the problem

Data: L1 is defined, L2 is defined, L1 /\ L2 is defined.

Unkown: Regular Expression for L1 /\ L2

I know it is possible to come up with one because Prof Heap said somebody did it on the bulletin board.

Seperate: First write L1s regex, then write L2s regex then combine.

2) Plan

I will:

i) Find regular expressions for L1 and L2

ii) Break up the regular expression for L1 and insert pieces of the regular expression of L2 into it to create the cases of the intersection

iii) Combine the cases with + (ORs)

iv) Factor to reduce size.

This was devised by noticing the similarity between this and straight forward algebra. If we first examine L1, the 1s in L1's regex can be seen as variables holding the place of a regex to satisfy L2's condition also. The solution to this problem could possibly be applied to creating regular expressions to denote unions of other languages.

3) Carry out the plan

i) A regular expression to denote L1: (1*01*01*)*

A regular expression to denote L2: 0*10*(0*10*10*)*

ii) If we examine L1, we need to have an odd number of 1s in the 1*s. To do this, there are a few cases. 1) The first, second and third 1* contains an odd number of 1s (then odd + odd + odd = odd). 2) The first 1* contains an odd number of 1s (then odd + even + even = odd).  3) The second 1* contains an odd number of 1s (then even + odd + even = odd). 4) The third 1* contains an odd number of 1s (then even + even + odd = off).

1) 1(11)*[01(11)*01(11)*]*

2) 1(11)*[0(11)*0(11)*]*

3) [(11)* 0 1(11)*0(11)*][(11)*01(11)*0(11)*01(11)*0(11)*]* 

# 3 is an interesting case because we cannot split up the 0s. Thus we must have at least 1 repetition and then subsequent repititions will contain two center pieces (1(11)*). This is interesting because in this case, 0s can only increment by 4 rather than 2

4) [(11)*0(11)*0]*1(11)*

iii) {1(11)*[01(11)*01(11)*]*} + {1(11)*[0(11)*0(11)*]*} + {[(11)* 0 1(11)*0(11)*][(11)*01(11)*0(11)*01(11)*0(11)*]* } + { [(11)*0(11)*0]*1(11)*}

iv) Notice how two of the cases start with the same regex? We can combine these with +

{1(11)*[[01(11)*01(11)*]+[0(11)*0(11)*]]*} + {[(11)* 0 1(11)*0(11)*][(11)*01(11)*0(11)*01(11)*0(11)*]* } + { [(11)*0(11)*0]*1(11)*}

Finally, I am sure this works because of the means of construction. All cases are accounted for.

4) Looking Back.

Although this is a complex way of doing this, the regex is right based on the way it is constructed (including each possible case then logically combining them). 

We learned a better way of doing this in lecture, using FSAs and then converting them to regex. I think that is a more practical way since it is more systematic and will work on all problems. However, in problems where you are doing different things with the 0s and 1s, this solution should work.

Week 13

The test wasn't too bad. The state question was very easy, and I kept looking at the transitions to make sure there wasn't a trick somewhere in there (like making the state invariant of q1 be x equiv 2%3 rather than 1%3). I couldn't find any tricks. The other questions were less straightforward. I almost forgot that I had to prove Language equivelancy both ways and I ended up rewriting my proof in the last 5-10 minutes.

All in all, I study the wrong things. I expected the test to have questions on the pumping lemma, turning NFSAs into DFSAs into regex and things of that nature.

Week 12

The assignment went by smoothly once again with the help of my group. Working in groups is great as everybody has different insights into the problems, so the thing I will get stuck on my partner has a quick solution to and vice versa. Despite this, I obviously need to practice proving Regex equivelancy and will make sure to review it before the test. I can create my own equivelant regular expressions and practice proving their equivelancy.

The lecture: AAAAHH! There's almost no notes on the bulletin board and I wasn't feeling great and had to miss class. The pumping lemma, from the lecture notes, is very easy and I grasped it quickly. My only question that arises is why there needs to be a u v and a w. Although its obvious there are uses for it, there are situations that it seems pointless. For example, the question of having a string with the same amount of 1s as 0s, it could easily be solved with just a v and a w. The u is just dead weight. Oh well, I'll do it the way im taught!

Now I need to read the textbook to find out what I missed in lecture!

Week 11

Epsilon transitions are very weird.  The way NFSAs are defined with the epsilon transitions is very strange and I need to review this to get a better grasp on it. Same thing goes for turning NFSAs into DFSAs. However, the cartesian product is very easy, although tedious. Listing states over and over again changing 1 tiny thing each time is not my definition of fun. Despite their usefulness I can see myself growing to dislike both NFSAs and the cartesian product. Time will tell.

Week 10

DFSAs. These are the coolest things ever. You can draw a regular expression evaluator. It's a simple idea put together very interestingly. There are quite a few things to remember; states, transitions, start state, etc. but they are pretty obvious. I have to remember not to forget to mention the start state and the end state. All in all DFSAs are cool, easy, and seemingly useful. :)

I liked the example of the "difficult" regex to construct and how I was able to have a solution very quickly (despite being told it was hard). However on review, my solution had a hole that I need to fix, which is why I did not put it on the bulletin board. That is the problem I will do the full Polya method of problem solving on. 

Week 9

The test was not extremely difficult but I was unprepared due to my lack of understanding about loop invariants. The question involving the loop was the most difficult for me only for the fact that I did not know how to include an invariant that will help me in my proof. It was easy to prove that the function terminated but my proof was definitely not in the pattern of what we were taught (and was probably wrong). The rest of the questions were easy.

Finally a change in the flavor of the material, the regular expressions are a wonderful break from induction (unless were going to use that for this too...). They seemed very confusing at first (especially the Kleene star but by the end of a lecture, they made sense.) The proof was very bizare but I am sure that with practice these things will become easy.

Week 8

I did not attend the lecture and after writing the test I wish I had. It was very difficult to figure out the proofs for functions with loops simply from the lecture notes. The concept of a loop invariant, although seemingly useful, does not differ from a postcondition in my mind?

The assignment went by very well even with my limited amount of time to work through and understand it. The partner system helped very much and I am upset I never utilized partners before. The questions were very similar to those done in the lecture and it was not difficult to extend those ideas to the assignment.

Week 7

Proving correctness of a program is an interesting concept. Rather than the way we have been taught to check our code (through test cases), we now define preconditions and postconditions to see if they work every time the program is recursively called. I wonder if this would be too complex of a proof for one of our 207 assignments in order to avoid writing test cases. The concept itself is very interesting, yet the proofs themselves don't seem to be. Oh well.

The problem set was very straightforward. Probably one of the easier ones so far but it's always the stupid silly mistakes that make me lose marks. The only difficulties I encountered are determining what is a sufficient for these (non-numerical) proofs. I find I have to define what something like

# Postcondition: revString(s) returns a string with
# the characters of s in reverse order.

What does reverse order mean? If I am the one deciding it, can I just say reverse order is defined as:

revString(s[1:]) + s[0]

Week 6

I did not attend lecture this week due to the damned A1 for CSC207 so my comments will be solely based on Prof Heap's evening lecture notes. 

Time complexity: We did this a bit last year in 165 (i think) and 148 so this is not new. However, applying the unwrapping principle to time complexities is a nice summation of some of the things we learned so far. I found it interesting how we were allowed to essentially ignore a majority of cases and do the proof for the cases we can, then come back to the other ones later. This strategy seems like it will become quite useful over time. (Since I am writing this retrospectively I know how handy it comes in for A2). The proof however, was very standard, maybe even obvious, after that. 

Week 5

I was hoping on seeing my test before posting this entry but it's pretty late as it is so I will reply to this with my comments about the test when I see it.

The lectures: Well the problem set brings another lost mark from a stupid mistake, but not a bad result anyway. We discussed finding closed forms for recursively defined functions and I found this quite interesting. I have myself wondered if there was an easier way to find those Fibonacci numbers, had I known the closed form those Grade 12 Data tests would have been so much easier. At least I have a new tool in my toolbox. Finding closed forms (using the exponential method) is pretty intuitive once I saw it but I do not believe I would have ever figured out something like that.

Obviously this technique can be applied to almost any recursively defined function in some way yet the Fibonacci one in my opinion is the most interesting. The rest of the proofs were essentially things ive seen before and did have educational value but didn't catch my interest.

Week 4

So my blog has been blocked. Apparently I have created a spam blog where I am spamming very offending links/comments? Now a "human" must review my blog to make sure I'm not spamming. Oh well, I can't fall behind my sLog.

So heres my thoughts on week 4. More induction! Except this time, we use induction on recursively defined functions. Recursion is pretty straight forward (unless you need to figure out how to code it at times) but when I'm doing computer science my brain does not want to think in terms of math, therefore I don't like "unwrapping". But I must admit, I have always found the Fibonacci patterns, despite their recursive nature, quite interest. Next we looked at binary trees and I rather enjoyed this proof. I'm not sure I would have easily seen the idea of "unwrapping" in order to keep both values in the equation relatively similar and I am glad to have seen this now, rather than on the test for the first time.

Yet there is one thing about this week's lecture, and I am asuming from hereon out, that I am beginning to think will frustrate me slightly. We are done with python, and all these problems with python sure aren't helping me remember my java syntax from highschool. I'm sure there's people who were are not required to begin learning java and appreciate the problems being in python but I am wondering if test questions can be written in our programming language of choice. Speaking off the test, it's tommorow! ahh!

Week 3

So week 3 and the assignment are done.

The lectures this week were interesting. I enjoyed the circular proofs of the three induction principles. However, I find a problem with the way we chose to prove them. We said that we would need to take any one of the as an axiom and can prove the other two that way. I have no problems with any of the principles being axioms as they just seem obvious, but if they are axioms then none of them should require a proof. It seems very arbitrary to say "pick one, the other two need proofs". In short, they should all either be axioms or require proofs using something other than a different principle of induction.

The assignment was pretty easy (we will see if this statement holds true when I receive my marks). The first question was structured in such a way that the answer was obvious, although I'm sure that was intended as it was the first question. The second question, about the rotating lunch orders, I found very interesting. The proposition of creating lunch menus that do not differ by more than 1 choice is very easy, yet I find that I wasn't thinking of the algorithm. I somehow naturally knew what the structure should be and only after writing a few different sized lunch combinations did I notice the algorithm. The proof was straightforward. The final question with the golden ratio had me fooled for a little as I tried to equate the hint to the formula, rather than plugging in n1, and n2, into the formula to transform it into the form that the hint was. However, after I reached the n2/(n1-n2) form it was smooth sailing from there.

Two Weeks in One

I have finally created my SLog, hurray!

So now to catch up.

Week 1:
I was unable to attend lecture this week due to a work conflict; however. Upon reading the notes from the lectures I came upon the conclusion that I really like Prof Heap's new laptop and the fact that notes are available online and not written in chalk. This not only helps me when I miss a lecture (like this one) but allows me to pay closer attention in class instead of worrying about what to write down. Although last year (CSC165) had all the course notes in the online textbook, I find it easier to follow along with the exact order and examples with which it was taught originally.

Now the content: The course seems very similar in flavor to CSC165, simple induction is obviously a review and I have no problems with it. The problem set was very straightforward and since I am writing this in hindsight, I know now to make sure I am including the smallest possible base case i.e. look a little harder for it.

Week 2:
Seeing the notes being written in class makes me appreciate them much more. Also, the night lecture for this course is much less crowded than the day lecture for CSC165 last year, which I feel really suits the courses style. The frequent, do it yourself, type questions Prof Heap gives us does help, rather than us staring blindly while he works it out for the class.

The content: Complete induction is very simple and straightforward, partly because I was introduced to it last year at the end of a lecture when asking about a different solution for a question. To me it feels as if simple and complete induction are the same thing. The principle of well ordering, on the other hand, seems very strange. Every non-empty set has a smallest element? Obviously this is true but I don't quite see how it can be applied. I guess this is something I will have to pay extra attention to. The problem set this week was very straightforward, I will have to wait for the results to find out why (hopefully because I knew what I was doing and not because I did it very wrong). I looked at the assignment this week and it does not seem too problematic aside from the last question, which it seems like we don't need to do anymore. Phew!

I would like to work on the third problem set and finish the assignment before I post my third weeks blog so stay tuned.