Test 3 Q3 review - Problem Solving

Below is the last question in test 3 i did hours ago. I wrote down the proof briefly which may not be that convincible, so i decide to prove it again.

Prove L(1*(0+e)1*(0+e)1*) = L2, the language has at most two zeros.

To prove the equivalence, we actually prove that for any element x , it can be represented by
L(1*(0+e)1*(0+e)1*) or L2. The former one looks a little bit complicated but actually it is possible to simplify it to make the proof much easier and shorter. By applying the distributivity, the transformation is going to be like:
L(1*(0+e)1*(0+e)1*) <=> L((1*0+1*e)(1*0+1*e)1*) , apply identity and annihilator for concatenation here, we get L((0+1*)(0+1*)1*), then apply idempotence of Kleene star, the simplest form is L((0+1*)(0+1*)).
Now, we are really just proving L((0+1*)(0+1*)) = L2.

In first part, we prove L((0+1*)(0+1*)) is a subset of L2.
L2 tells us how we rewrite L((0+1*)(0+1*)), that is to say, the number of zero is crucial.
It's definitely true by just looking at L((0+1*)(0+1*)), but we need demonstrate it with stronger reason. All cases include zero-free, one zero and two zeros. (0+1*) has either one zero or repetition of 1 or e. Then the concatenation of two (0+1*) has two zeros at most which satisfies L2. Then x \in L((0+1*)(0+1*)) implies x \in L2.

In second part, we prove L2 is a subset of L((0+1*)(0+1*)).
In this part, the setting for the typical elemtent x depends on L((0+1*)(0+1*)).
Since there are at most two zeros, i don't think there are too much things to worry about.
We just ensure x can be zero-free or with one zero or with two zeros.
x = (0+1/e/1*)(0+1/e/1*), (0+1*) is satisfying the language L((0+1*)(0+1*)) here.
Hence, the proof is done.

For such questions, once the languages on both sides are well understood, the proof will be just following the formal procedure.

Chapter Seven Review

#############
Formal Language:
#############
Any set of strings can be empty, finite, or infinite.
Length of string: s, number of symbols in s, ex: "+"=1, "e"=0.

#############
Regular Expressions(Regex):
#############
Basis : empty, empty string, one-symbol character;
Kleene star can be used to restrict the pattern of a regex:
even or odd numbers of some characters;
Idempotence of Kleene star: R** = R*
Distributivity: (A(B+C)) = (AB+AC), ((B+C)A) = (BA + BC)

Proving equality of two languages => Prove mutual inclusion:
1. Analyze the pattern of a language and divide into pieces if possible;
2. Transformations: in general case, expand some terms to make up the equality;
3. Check from both directions, conclusion.

###
FSA
###
Proof procedure, induction:
Basis: x=e, &*(q_e,x)=q_e. P(e) true.
Induction Step: Assume x = x'a, assume P(x'). Analyze the cases.
In all cases, x = x'a and &*(s,x) = &*(q_e,x'a)=&(&*(q_e,x'),a)
according to our induction hypothesis.
Then using the transistions functions, we prove P(x') => P(x), in all cases.

####
NFSA
####
Difference: Each transition takes the machine to a subset of states rather than a unique
state.

Notes:
Every regex has equivalent NFSA.
Every NFSA has equivalent DFSA.

DFSA

In some degree, the most challenging question in assignment 3 may be the last one.
I once got stuck on combing the two machines representing binary string with odd length and multiple of five respectively. I wasn't sure what were the exact steps using cartesian product. So i considered all the combinations of the cases of the third machine i want to construct.
That is exactly the result of cartesian product. Excluding the initial state, there are 5*2 = 10 states
for x = n mod 5 with odd/even length. These are the state invariants. Then We can see directly from some binary numbers and derive the transitions. Then the desired machine is fulfilled.
The proof of a DFA is straightforward. For me it is kind of a process of verifying each state go to the correct place via a path or an edge. Graphically, each state is a node with inputs and outputs.
Thus the transitions explain the correctness of traversals in a machine.

review of Week 10

The annoying assignments, exercises, quizzes and term tests seem to be paused except for CSC236. This weekend i have to engage into the second last assignment with my partner. I also have a somehow big project of csc207 to worry about. Insipte of the workload of a computer science student, i now write for my 6%~11% of the final mark.
These two week we saw pretty much things about finite state automata and regular expressions. Regular expression is a descriptive way to express the language. We can design our own language with different alphabet using regular expressions. Through the example in the lecture, such as an alphabet of binary numbers containing even or odd zeros, i learned a logical procedure to analyze the syntax between various languages. The interesting part for me is the algebra on regexes. Without changing the language, one can apply some principles such as: commutativity, distributivity to the regular expressions. This simplifying process allows more variations on a language and it provides some interesting design patterns of a language.
Another thing is the DFA, or DFSA. The first time i saw it was in CSC148 when we were doing the graph algorithm. It seems there is quite a few connection from the DFA to graph algorithm. Machines of DFA accept their unique pattern of strings. We can easily find out whether a string is valid to the machine by traversing between the states. The hard part is how we construct a desired machine for a particular collection of strings. By observing the pattern of some strings, we need to derive some crucial parts of the machine like the state invariants and the transition functions. A graph is usually helpful to verify the state the next character heads is correct, which is to say, we need to carefully set our initial state, final state, states between and all the edges. Such things is really thoughtful.

After Test 2..

Since there is always a lot of people there in the day section, i wrote the night section test.
I don't know how big the difference between the day section and night section test. They may follow the same patter pretty much. I didn't work out satisfying answers on the test.
About the palindrome, i remembered well that i did the same thing in CSC108 lab. But one thing
to regret is that i forgot the prove structure. I tried using complete induction but i didn't organize the frame well.
Related to the last question in the test, i really got a mess in my mind during the test.
I got frustrated when i could not figure out right away the main purpose of the function downward(n). Things happened and i got all blank in my brain. When i got calm down and refreshed my mind, i tried out some typical examples. Unfortunatley, i didn't realize that the loop invairant was sth like the floor of lgn until hours after the test. Anyway i cannot say i fail the test, at least i failed getting an insight on the subtle things.

More on iteration

The 3-hour night version lecture is a real torture. For the example counter(m,n), i can't relate the loop invariant directly to the correctness of the program. It's weird that the b value is set to 6.
I tried pick two non-zeros natural numbers for m and n randomly. And the loop has to execute 6 more times to terminate after a and b decrease to 0 since b is assigned to 6 and c has to counter 6 more times. It may be necessary to use the loop invariant c = 7m + n to go to the postcondition, but it seems not to be that straightforward to be understood. Now i realize the importance of code design that make other people's life easier, for people who are learning how to prove loop invariant. Back to the loop invariant, i usually trace algorithm on simple example, like iterates for a few times and see what kind of changes are caused. As to me it's more helpful than just thinking of some fancy relationship between precondition and postcondition.
For more complicated loops, like nested loops, these things have to be done inside out. Prove termination and loop invariant in the very inside, then for any value of the loop outside, prove termination and loop invariant for outside loop. In the selection_sort example, the inside loop is going from index j=i+1 to the end of the list. Selection_sort is basically "selecting" a proper position for an element in the unsorted section of that list. I take a [4,2,3,1] as an example to run the loop. The inside loop actually helps me to evaluate a position by comparing the value of 4 to 2,3 and 1, then the outer loop moves to the next index and this easily sorts the whole list. But the inside loop may have k+1 iteration or may not. Since the value of the number could be equivalent. These "special" cases happened because of the postcondition, which is non-decreasing order here. Then it's not hard to prove the program "moves" and "compares" in some range.

Busy Week 8

A2 was submitted a few days ago, but i didn't work out the first problem, neither did my partner.
I didn't derive a valid recursive formula for the 3rd problem as well. So i just proved it without a valid formula, which might lose some marks probably.
Luckily the 207 midterm was over this afternoon, i now have more time to review the materials Danny had talked about iterative programs.
It's again easy to start with, and more interesting than the previous sections. Obviously, we will use a lot of simple induction stuff here, for proving correctness of iterative programs. It's tricky to seek for a proper loop invariant, and it always takes times to go through the loop and see how this 'incomplete solution' works. Again, to prove the correctness, we carefully trace the loop and the changes each time it caused. This helps us to fulfill the implication from the ith to the (i+1)th loop.

the end of week 7

Proving program correctness is always an annoying part, especially dealing with searching items and sorting items in an array or list. There are many conditions to consider for the program(most of them we have seen during this week were recursive programs) correctness.

The proof of correctness may be like: by induction, for size of the input,
prove precondition -> termination&postcondition. It seems the structure of
complete induction is well following recursive structure.

Then we go through the first few lines and if lucky enough we can proceed to the
annoying part of the recursive function. In this case, the recursive step leads us
to examine the whole function again with different input size, a smaller size.
We don't stop checking until we get the expected result - the post condition.
But how to split up the size so that it will look more straightforward and easier to
be checked? For the binary search, the way is to break into the middle of a list.
So there may be various ways and algorithms for various problems to shrink the
searching or sorting range. The next thing is to continue on executing. The case
must be carefully chosen otherwise some unexpected errors may cause the crush
of the program.

The proof is complicated at most of the time so as to ensure all the codes work from the
first line with the initial input. It saves us a lot of time to complement any cases or to fix
up any mistakes afterwards.

Lecture about Program Correctness

Monday came, Danny didn't come.
A lecturer named Nick presented us a lecture about program correctness.
Nick started by the sentence "My program is correct." He talked about how correct a program
would be from different points of view. He spent some minutes on explaining the definition of conditions, the relationship between precondition and input, postcondition and output.
This helps us to recall what we have learned in CSC165.
Then he gave the very familiar example, binary research, to reinforce the concept on how a program would be correct in each step. One question(maybe just for fun, maybe not) he mentioned during the lecture was 'how do you crush a program', which sounds very illegal.
But at the same time, this is just the way to prove the program correctness backwards.
I believe if one can crush a program easily, then it wouldn't be too hard to prove correctness.
That is where you see right from wrong. So yes, let's enjoy crushing our programs.

Week 6

This week we focused on analyzing the complexity of mergesort and did some unwinding and proof. The repeating substitution procedure is simple. In most cases, when n>some integer, according to the definition, we can easily get a formula from the right hand side. Since we want the f(n) or g(n) or whatever to decrease to f(0)/g(0)=1, the formula we eventually derive will be like a constant to the power of something plus something else. To make a conjecture, we just carefully define n, which is usually natural numbers with some restrictions. The divide-and-conquer strategy provides us a way of breaking big problems into smaller and smaller parts. Then the size will be small enought for us to directly solve. Well, at least with spliting up and solving one of the subproblems, the base cases, we can always get a few marks.

term test 1

i used simple induction for all the three questions. Since i guess it would be easier to prove P(n)=>P(n=1) for the predicate in the three questions, except the last question. it seems it would be proper if i used complete induction to prove it. Similar problem i had seen before. since i was writing in a hurry, i just picked the most familiar technique for me to solve, which is simple induction. I was stuck when i was dividing the set into a part that can be applied with IH. The n+1 element took me a lot of time to derive the subsets containing it. I might be wrong on the answer since the induction step wasn't that successful. if there were 5 more minutes maybe i could do the induction step one more time and find out which number of subsets is going wrong.
Luckily the first two questions required less cases to analyze. i think i did well in the recursive one.

review for week 4

The algorithm complexity part is usually thoughtful-provoking.
I didn't see big differences when i run a program on my laptop or some computers, but i did see the way that much fewer steps generated by applying recursion. Well, iterative functions come more naturally for me though great efficiency recursion has. Everytime i'm analyzing recursive functions, my sight jumps back and forth. Thought it makes my codes neat, it usually takes time for me to solve a problem recursively. We also did a bit of unwinding, estimating the time complexity of binary search and the proof of it.

how wrong would a proof be

I'm given some ideas of how a induction "traps" is raised by today's lecture. As to me, this happens that i write down the proof before convincing myself that each step follows the previous steps rigorously. We know that there are base case, induction hypothesis and induction step in a formal induction proof. The subtle may be made by missing one of them or by saying something that mismatching the fact. I sometimes make mistakes by making implicit assumption, and the result is that i couldn't reach the conclusion since it is incorrect at the beginning. To understand the statement is also important since the predicate is chosen from the statement. For the last problem on assignment 1, we should carefully remain the property of a ternary tree when we make our assumption. Good luck for the assignment 1.

working on practices

By reading the textbook, the simple induction and complete induction seem not that confusing. To make sure that i understand the definition and examples, i redid the proof in lecture and in the textbook. It's really important to find the right base case: is this case the very fundamental of the problem? do we need more base cases?
The scratch work helps a lot because it's always convinent to make changes when i look backwards in the problem. All of the mathematical problems we've encountered in this course are solvable. The key is always to know what kind of strategy to use corresponding to the problem and follow it step by step.
For example, we want to find out the possible unit digit that 3^n can have by using simple induction. The method is specified as simple induction. Then we just need to figure out the base case and the induction step. It's easy to find the P(0). Then we have to determine P(n) and let it imply to P(n+1). There are different predicates in different questions. We must make sure we understand how does P(n) work here so that it leads exactly to P(n+1). It's really helpful to correspond our assumption to its inductive case and understand the property. When transforming 3^(n+1) into 3*3^n, slight change is made but huge differnce occurs. We now can see the answers explicitly because 3^n had been extracted. This means we have proved our inductive case correctly.

Week 1 in CSC236

Since i took CSC165 in the summer, this is my first time to use SLOG.
After reading the SLOG handout, i kinda understand what is it now. Compared with the bulletin board, SLOG is a better platform to post one's opinions, with more details and informations.
It's an exciting thing that we can record what we've learned and what we've doubted. By viewing others' blog we can try to explore a different way to think the same problem. That's a good thing.

The materials in the first week were not too much and not that confusing. So far we took a review about the simple induction and strong induction by dealing with some mathematical statements. They seem quite familiar, but the problems are always tricky.
The proof of recursive program and program correctness might get harder in the future. For now, i will try my best to conquer any difficulties in the most basic part.