"Understanding how DNA transmits all it knows about cancer, physics, dreaming and love will keep man searching for some time." David R. Brower

The subsequence teaser question that was given out in class on friday kept me thinking for a while about it. I guess it was the fact that the natural solution was one thats implementation was extremely long that kept me thinking. I guess I never really thought about the fact that there are problems that need solving all around us that may be hard to solve just because of their size.

Any way I thought about a possible solution and I don't even know if I'm on the right track or not nut I figured I would jot down my thoughts and maybe latter try to code it up and see if im on the right track.

Here it is.

Scan the list once. While doing so create a dictionary with the items of the list as keys and there index placements in the list as values. in addition to that create a binary search tree from the list in order to cut down search time when retrieving a certain element from a list.

given a a case that the main string was 'xyxayxya' and you were looking for the number of occurrences of 'xya' instead of looking at the string you can refer to the dictionary that would look like this

{'a': [3, 6], 'x': [0, 2, 5], 'y': [1, 4]}

then for every character of the sub string 'xya' you check recursively how many times the next character happens at an index that is strictly larger.

looking at x[0] would return y[1] would return a[3, 6] would return y[4] would return a[6]

looking at x[2] would return y[4] would return a[6]

looking at x[5] would return nothing because there is no y at a bigger index.

I'll try to code this up and see where it goes.

Thanks for reading

"Everything is vague to a degree you do not realize till you have tried to make it precise." Bertrand Russell

Since test 1 is done with it seems that the course is turning the corner and we have now started working with proofs. I find proofs very interesting especial given the new found knowledge of the different techniques in approaching logical statements. I feel that in the past when dealing with proofs unless I had a clear path to follow I could stare at a the problem without knowing where to begin. 165 has given me a new perspective on problem solving and I can feel how my mental tool box is slowly growing and enabling me to structure proofs on my own without knowing where the result will lead me to.

In spite of all this rambling, I found the last assignment a little bit tricky. I generally try to do to get started on the assignment relatively close to the date we get them and go over them to correct any mistakes closer to the due date. When going back to review my work this time, after a week of going over proofs I discovered that my approach was all wrong and consequently so were all my answers. For some reason while trying to prove

∀ n ∈ N, U(n) => U(n2)

Where U(n) is defined as,

∀ n ∈ N, U(N) ⇔ ∃K ∈ N, N = 5K + 1

I'm not sure if it was the way the definition of U(n) was given but something about the ∀ n ∈ N, coming before the U(n) itself made me think that all I had to do was prove existence. When going back to review my work (at around 9:15pm the day it was due) I realized my mistake and franticly tried to figure out the right way to fix it. I hope it when't well and I'm pretty sure I got it right in the end.

The current topic that is blowing my mind is proving the obvious, who would have imagined.....