Zigg's csc236 Domain

Problem Solving: Part II

2008-12-02T20:35:00.000-08:00

Last time, I played around with methods to efficently sort a string of angle brackets, into a particular form. I discovered Inward Paired Form (IPF) and Outward Paired Form (OPF), as logical steps to getting a solution to the problem mentioned in the last post.

I believe at this point, I have found the (one of) the most efficent ways to sort the angle bracket strings accordingly. It turns out that the previously rejected IPF is infact useful in the solution to this problem.

Before I go into detail about all of this, let me present a table with my findings:

“>_<”

“>>_<<”

">>>_<<<”

“>>>>_<<<<”

Start String -> IPF

><_

>_><<

><>_<

><><_

>>_><<<

>><>_<<

>><><_<

>><_<><

>_<><><

_><><><

>>>_><<<<

>>><>_<<<

>>><><_<<

>>><_<><<

>>_<><><<

>_><><><<

><>_><><<

><><>_><<

><><><>_<

><><><><_

IPF -> OPF

<>_

><_<>

_<><>

<>_><><

<><>_<>

<><><>_

><><><_<>

><><_<><>

><_<><><>

_<><><><>

OPF -> Solution

<_>

<_><>

<<>_>

<<_>>

<><><_>

<><_<>>

<_<><>>

<<_><>>

<<<>_>>

<<<_>>>

<_><><><>

<<>_><><>

<<><>_><>

<<><><>_>

<<><><_>>

<<><_<>>>

<<_<><>>>

<<<_><>>>

<<<<>_>>>

<<<<_>>>>

This chart shows the most efficent ways (I could find) of arriving at the solution, for 4 pairs of strings that (increment by one set of <> brackets). The solution I use has the following process:

Start String -> Inward Paired Form -> Outward Paired Form -> Solution

Immediately, the problem of insufficient cleverness arises. How do I know this is the most efficent way to obtain a solution? To be honest, I don't. I there are other cases I could have checked (although, I checked many). I found this method to be fairly straightforward; furthermore: to make the solutions even more efficient after this point became fairly difficult. Because (unlike other, random methods), the one above is easy to conceptualize, in addition to appearing highly efficent, I choose it for my final solution.

Because I am letting the above method be my final solution; I can answer the second part of the question to this problem: What is the minimum number of moves needed for an n bracket string?

Because of the conceptualization of this problem, steps can be fairly easily counted. Let every move be one step. Then, the total number of moves for an arbitrary string of angle brackets is:

| Start String -> IPF| + | IPF -> OPF| + |OPF -> Solution|

Where "||" indicates the number of moves for each process. Let us consider each process in turn:

1) | IPF -> OPF|:

From the table, it can easily be seen that for n sets of brackets, n moves are needed for this step in the solution. Then simply, f(n) = n here.

2) |Start String -> IPF| AND |OPF -> Solution|

A glance at the table shows that both processes have the same number of steps. If f is a function that represents the number of steps for each sub-process, then:

f(0) = 0
f(1) = 1
f(2)= 3
f(3) = 6
f(4) = 10

which results in the following recursive formula:

{ n n = 0, 1 |
f(n) = { |
{ f(n-1) n >= 2 |

We can unwind the formula accordingly....

f(n) = f(n-1) + n
= [f(n-2) + (n-1)] + n
= [f(n-3) + (n-2)] + (n-1) + n
.......
= [0 ] + 1 + 2 .....n

Simply, the sum from 1 to n. So then f(n) = n(n+1)/2 .
-------

Then, our final formula for | Start String -> IPF| + | IPF -> OPF| + |OPF -> Solution| is:

f(n) = 2(n(n+1)/2 ) + n
= n(n+1) + n
= n^2 + 2n

If I have time, I will give some proofs of my findings. That is all, for now.

Problem Solving Post: Part 1

2008-11-26T23:42:00.000-08:00

A requirement for the course SLOG is to solve (or at least attempt) to solve a fairly advanced problem, from a list of problems. Its time to complete this requirement. From the list, I chose the following problem to pursue:

"Start with some number of >'s lined up on the left side of a page, followed by a single space and then an equal number of <'s lined up on the right. The goal is to achieve the mirror image (>'s lined up on the right, <'s lined up on the left, with a single space between them). There are two legal moves:

Either symbol may swap places with the space, if it is adjacent.
Either symbol may swap places with the space, if it is separated from it by a symbol of the opposite type.

Here's a solution for a single symbol of each type:

start	>		<
move 1		>	<
move 2	<	>
move 3	<		>

Is there a general solution for an arbitrary number of >'s and <'s, with a single space in the middle? What is the minimum number of moves required?"

Looks like a standard problem, but fights back well. The problem has two parts:

1) find a general solution

2) find the minimum number of moves. (which adds an extra condition to (1)).

I have made some progress towards both requirements. My notes so far are below:

-----

1) Find a general solution:

Now, this is quite difficult; because the number of possible "moves" grows rapidly as the number of symmetrical symbols increases.

It is also not clear what the most efficent way of doing things is; and how to develop a scalable, general solution.

After a lot of experimentation, I found the following:

For ">_<", ">>_<<" and ">>>_<<<" the minimum number of moves (I found) were 3, 8 and 19, respectively. Such numbers do not play well with a natural number formula; flooring/ceiling might be required.

Upon looking at this problem, I immediately suspected that It could be solved in a recursive fashion. For example, the solution to ">>_<<" can be found by first solving for ">_<". Doing this guarentees a solution to any problem of size n for this question; however it is NOT the most efficent way of doing things.

Consider the case k = 2 ">>_<<".

Solving by using the case k=1, the solution is as follows:

0: >>_<<
1: >_><<
2: ><>_<
3: >(<_>)<
4: >_<><
5: _><><
6: <>_><
7: <><>_
8: <><_>
9: <_<>>
10: <<_>>

Compared to not solving the problem recursively; NOT solving for the k-1 case first:

0: >>_<<
1: >_><<
2: ><>_<
3:><><_
4:<>_<>
5:_<><>
6:<_><>
7:<<>_>
8:<<_>>

My next focus was on a particular forms that are ideal for the solution. You may have noticed that many things "come together" for the sort, when the "<><>_" or "_<><>" form is encountered.

Consider a larger case of this form: <><><>_

0: <><><>_
1: <><><_>
2: <><_<>>
3: <_<><>>
4: <<_><>>
5: <<<>_>>
6: <<<_>>>

Beautiful! I call this form the outward paired form; naturally because the symbols are paired, and point outwards. Notice that for moves 2 to 6, only jump swaps were done; no movement of the space was needed at any point; this gives some indication of high efficency (intuitively).

Out of curiosity, I also investigated the inward paired form:

0: ><><(><_)
1: ><(><_)<>
2: ><_<><>
3: _<><><> [just results in outward paired form!]

However, this is because we only traveled in one direction, start at 1 again...

1: ><(><_)<>
2: ><_<><>
3: ><<(_><)>
4: ><<<>_>
5: ><<<_>>
6: ><<_<>>
7: ..... not quite as efficent; we need to travel all the way to the end, and keep flipping.

=> Forget about inward paired form (for now).

Later, I will provide a formula for the general number of moves for k symbols, given that the string is in outward paired form.

Of course, this raises the question: for all the moves you spend to put the string in outward paired form, is there a more efficent way? what if substrings (k-1) were put into outward paired form instead?

2) find the minimum number of moves. (which adds an extra condition to (1)).

As you can see from above, I am still investigating this.

Then, my next research objective is to learn more about outward paired form, and in particular:

-is it better to use outward paired form recursively?

-Or...should the whole expression be put into outward paired form? Which is more efficent?

Such bring us closer to solving a general and efficent method for the problem as a whole.

Assignment II is done.

2008-10-29T16:20:00.000-07:00

It has been a while since I have updated this blog. As all of my final exams are in the first week of the exam schedual, this has put an increased work load on me. I have to start studying now it seems, in addition to the tasks I already have to do.

I got my midterm back a few weeks ago. Looking over it, my performance was sastifcatory; however I didn't get an A; which is a shame because this midterm was a bit of a give away (relative to the other courses I am doing). I dont see any marks to appeal, after looking over the midterm, so I will live with it.

Assignment II was sneaky! Questions 2, 3 and 4 did not appear to be too difficult. Question 2 was just a truncated, floored logarithm base 7. Question 3 was a bit strange, but doable. Question 4 was from the class notes, and tedious.

Question1 however. had a glaring problem: it was very easy to miss duplicate trees. As the recursive definition generated sets of all trees with n nodes (and as a basic propery of set theory: only one instance of an element in a set), it was very easy to overcount when calculating F(n).

One would naturally try to resolve this by constructiong an F'(n), which subtracts duplicates from there F(n). While your at it, you can show Z^n != X^n + Y^n for n >=3 using elementary mathematical concepts only.

Seriously though, finding F'(n) is probably possible, but just very difficult and obscure. Thankfully, I was pointed in the right direction: use a recursive double.

Surprisingly, I also spend a fair amount of time on Q4. This was because, one had to first figure out if it was a flawed algorithm. Of course it isnt, however the algorithm can fail if the machine that executes it has poor floating point architecture.

For example, it can be shown that for: sqrt(k(k+1)), that the fractional part of this number must be <= 0.5. As n -> infinite, on a finite machine with approximated floating point numbers, you can actually get the fractional part to be 0.5....since the algorithm converts the root number to integer...this will round up.

Keeping this in mind, this is how you can make the algorithm fail:

1) take k to be an incredibly large integer.

2) use a set of inputs, (A, x, b, e) for bs1. let b = k, e = k+1, and x be at position k+1. Let x be at position k+1

Then, when the midpoint is calulated, the floating point roudning error will produce k + 0.5, which rounds to k+1.

When the computer compares A[m] >= x, A[m] = x clearly. This resutls in:

return bs1(x,A,b,m).

but e = m. Therefore bs1(x,A,b,m) = bs1(x,A,b,e). So an infinite cycle is produced. With a big enough k (or a cheapo FPU), one can break this algorithm.

Of course, this is not the algorithms fault; its a hardware problem. In trying to find flaws in the algorithm, this is a fun thing I realized.

END.

Not much to say.

2008-10-06T00:00:00.000-07:00

Not much to say right now.

I am preparing to study for the midterm on Friday.

There is one major problem I have encountered though. I would really like to select a course SLOG research topic. However, everytime i try to do this, either the SLOG PDF "doesnt exist", or the www.cdf website is forbidden/will not load. This is getting rather annoying; I would like to start as soon as possible on my selected topic.

EDIT: The website and pdf now work. I have selected the "Free lunch" problem as my first one. Later in the week, I will start to post my progress and solution to this problem.

First past the post!

2008-09-29T00:09:00.000-07:00

Ive started my first blog entry upto 3 weeks late. Oh well.

First, I will outline the structure of each blog post that I will make. Each post may contain any of the following sections:

- Thoughts on previous lectures
- Thoughts on assginment quesitons
- Discussion of difficulties encountered, and how they were resolved.
- Problem Solving (in particular, regarding at least one mathematical problem chosen from www.cgi.toronto.edu website).
- Any personal thoughts of my choice.

And now, onto my first post:
------------------------------------------
Beginnings:

Im still not sure why it took me this long to form a SLog for this course. Perhaps its because I have often detested blogging; a lot of blogs I encounter don't serve much of a purpose for me, or hold my interest. This is not to say that I believe there are no worthwhile blogs out there; rather, there is a lot of bad blogs for every good one found.

In the end, I guess I would rather take my 6 - 11% than uphold this belief; so I'll bypass it for now, in the interest of my GPA.

Regarding the lectures and material so far, there isnt much for me to say at this point. The material can sometimes be a tad obscure (WOP for example), but its not overly confounding to the reader. What I particularly like about the lectures is Professor Heap's style; its highly engauging. In fact, I dont think I have ever participated in a course that is so engauging in my university career.

It really helps with my retention of this course; this means less reading time and more practical work time for csc236 (and other subjects). The only downside is that if one is very tierd at the beginnning of the lecture, sitting though such a session can be painful to sit through... It doesn't help that I picked the 6-9pm lectures.

As for the assignment, I am a tad uneasy about it. My original view of induction was a highly mathematical and symbolic one: induction involves lots of inequalities, variables, and should sicken and intimidate anyone with a weakness in mathematics.

Professor Heap mentioned that logical "prose" proofs can be used. And for questions one and two, I found myself using a lot of words, and it not being so easy to use exclusively symbols. With more wordy proofs, I feel more uncertain and ambigous; I guess I'm not entirely sure what marks I will get on this assignment.

They say that "good problems fight back". I found that a few of the problems in this assignment did just that. Finding solutions were particularly satisfying in the end. I cant wait for grammars and some of the more obscure computer science stuff later on in the course!

END.