0011 - My Frustration...again

Just had to crank up my "Pick-me-up" playlist on Youtube. Just in case you're wondering, my playlist consists of 4 songs that loop forever. Feel free to listen to these as you read, or at your leisure:







Why am I playing my "Pick-me-up" playlist? If you can recall a previous blog post about "My Frustration," just know that I'm more frustrated right now than I have been at any point in this process. Granted, I'm 3 months into working on a problem that has consumed the greater portions of great men's lives before me. Those guys must have gone completely insane, because damn. This problem is stupid hard.

I just had my latest algorithm go up in smoke. Granted, I knew it wasn't complete, I knew it wasn't correct. I also knew that it was returning accurate results on large-sized graphs upwards of 90% of the time, which is pretty good. However, I finally admitted to myself tonight something that I've known for at least a week: at best, my algorithm is a decent heuristic, nothing more. It's like solving this problem is winning the World Cup, and I'm playing hopscotch while jumping rope. It makes no sense. I'm not even part of the game. I'm not even playing my game correctly. I feel like a dumbass.

So, since tonight is apparently full disclosure night, I'm going to share the BS algorithm I built because I'm brainless.

This algorithm will solve a majority of the graphs you throw at it, assuming that the graphs are formatted in a peculiar way: if two nodes are connected by an edge, it is represented in a 2-dimensional array with a 1; if they are not connected by an edge, it is represented as a 0; also, each node itself is represented with a 2. For example,

0 1 2 3 4 5 6 7 8 9
0 2 0 0 0 0 0 1 0 1 0
1 0 2 1 1 1 1 1 1 1 0
2 0 1 2 0 0 0 1 1 1 1
3 0 1 0 2 1 1 0 1 1 0
4 0 1 0 1 2 0 0 1 1 0
5 0 1 0 1 0 2 1 0 1 1
6 1 1 1 0 0 1 2 1 0 1
7 0 1 1 1 1 0 1 2 1 0
8 1 1 1 1 1 1 0 1 2 0
9 0 0 1 0 0 1 1 0 0 2

is a 10 node graph (nodes 0-9). You'll notice the diagonal line of 2's - these correspond to the nth column on the nth row, such as (0,0), (1,1), etc. So the first row represents the relationships of node 0. There is a 2 for 0, meaning that this is node 0. There are 0's for 1, 2, 3, 4, 5, 7, and 9, indicating that 0 is not connected to those numbers. There are 1's for 6 and 8, indicating that these two nodes are connected to node 0.

Okay, so that graph is used by the following algorithm (first few lines explain global variables):

gSize - integer that represents the number of nodes in the graph
best - integer that contains the largest independent set found thus far
g[][] - 2 dimensional integer array that contains the original graph (such as expressed above)
s[i][j] - 2 dimensional integer array that contains the optimal solution array for each node i; initialized with the original values of g[][]

IS():
    for i = 0 to gSize:
        while(true):
            temp = Weight(i)
            if temp < gSize:
                Switch(i, temp)
            else:
                break
         currBest = GetBest(i)
         if currBest > best:
             best = currBest

Weight(i):
    currBest = 0, currIndex = gSize
    for j = i to gSize:
        currWeight = 0
        if s[i][j] = 0:
            match = true
            for k = i to gSize:
                if s[i][k] == 0 && g[j][k] == 0:
                    currWeight++
                else if g[j][k] == 2:
                    currWeight++
                else if s[i][k] == 0 && g[j][k] == 1:
                    match = false
            if match == true:
                return j
        if currWeight > currBest && currWeight != 0:
            currBest = currWeight
            currIndex = j
        else if currWeight == currBest && currWeight != 0:
            first = 0, second = 0
            for k = i to gSize:
                if s[i][k] == 0 && g[currIndex][k] == 0:
                    for l = i to gSize:
                        if s[i][l] == 0 && g[currIndex][l] == 0 
                          && g[k][l] == 0:
                            first++
                if s[i][k] == 0 && g[j][k] == 0:
                    for l = i to gSize:
                        if s[i][l] == 0 && g[j][l] == 0 && g[k][l] == 0:
                            second++
            if second > first:
                currIndex = j
    return currIndex

Switch(i, j)
    s[i][j] = 2
    for k = 0 to gSize:
        if g[j][k] == 1:
            s[i][k] = 1

GetBest(i)
    currBest = 0
    for j = i to gSize:
        if s[i][j] == 2:
            currBest++
    return currBest


If you don't understand that, it's totally fine. It doesn't work anyway. If you do understand it, feel free to try to solve the graph I gave above with this algorithm. Here's a hint: you'll get a largest independent set of 3, while the correct answer is 4 because node 0 will connect with node 9 before the rest of them, while node 9 is actually not a part of the true largest set. In fact, my algorithm will come up with a largest independent set made up of nodes 0, 9, and 1 (picked in that order), whereas the actual largest independent set (as determined by me working it out by hand) is 0, 2, 4, and 5 (not necessarily picked in that order).

The problem is that I tried to simplify the selection process by weighting nodes based on similarity to the current node in question (in this algorithm, this would be node i). In so doing, I managed to actually solve a vast majority of the graphs that I tested. However, it was not perfect, so there were incorrect solutions.


So, how do I fix this? In short, I'm going to have to teach my computer to think, or at least to appear to be thinking. Backtracking, if you remember, has a worst-case time complexity of T(n) = O(2^n). I'm not taking that many steps when I work these out by hand, but I can't rightly explain to you my by hand method (which is part of the problem). The algorithm I outlined above has a time complexity of T(n) = O(n^5) (more or less...), which is much mo' bettah, but also doesn't get the right freaking answer.

So I'm creating a new class in my test app, opening up my steno pads, busting the dry erase markers back out, and listening to my Pick-me-up Playlist. Because I've got a lot of work to do.

0009 - Burnout (Explicit Content)

Burnout is a bitch. Anyone who has dealt with burnout knows this. However, folks who have seen others deal with burnout without having personal experience can often see it as whining and/or dealing with the consequences of getting in over your head. They're not wrong, but that oversimplification can lead to something that might be even more dangerous than burnout itself: bottling it all up.

Let's face it: people don't like being ridiculed. That's why I rarely write blog posts, I advertise new blog posts on Twitter exactly one (1) time, usually late at night so it will get lost in people's feeds, and I get nervous when I hit 5+ pageviews on a post (especially when people aren't commenting). It's because I just know deep down in my heart that someone is going to read my blog and think "This guy's an idiot and probably should never be loved and die alone."

Back to the topic...
When someone is feeling burnt out, they have limited options with limited results:
1. They can share how they're feeling and have people reach out to help them, which can (not always will) make the situation better
2. They can share how they're feeling and be ignored, which will make the situation worse
3. They can share how they're feeling and be ridiculed, which will make the situation much worse
4. They can keep it to themselves and have an altruistic person magically come along and make things better, which will make the situation better but pretty much will never happen
5. They can keep it to themselves and eventually regain the fire that got them started in the first place, which will, at least temporarily, make things better
6. They can keep it to themselves and eventually go postal and/or grind themselves down into nothing, which is pretty much the worst result

So, yeah. Burnout is a bitch. But what can we do about it?
In my endless wisdom and experience, I have concocted the following cockamamie scheme:

1. We, as a community, should learn to recognize burnout within our communities
We are all members of multiple communities, whether we realize it or not. It's not just the people you live around, the people you work around, your classmates, the church you attend, your group of friends, or the IRC channels you frequent, either. Members of your broad vocational field ("technology" in my case) and more specific fields (most likely plural; for me, they are "elevators," ".Net development," "logistics," "warehouse management," "analysis," etc. Do I personally manufacture elevators? No, but I'm a member of that vocational community.) are members of your communities. More than likely, you know people who have experience burnout in your community and know how your community was diminished because of the loss of that person's enthusiasm and abilities. What events or circumstances led up to that point? Were there any indications from the person that they were starting to feel burnt out? This can vary from community to community and from person to person, so there is no hard and fast rule for recognizing that this is happening. At best, when you hear someone talking about being overwhelmed, not having the energy to finish fairly normal tasks, and/or wanting to quit, move to a yurt on the side of the interstate, and raise goats and guineas, talk to them about that. Ask questions. Pry. Be a pain in the ass. Try to let them know, in your social misfit way, that you care about them and want them to be around for a while. Even if there's nothing that you can do (or that they will let you do), you will hopefully at least let them know that you care about them, which may help them open up later.

2. We, as people, should learn to recognize burnout within ourselves EARLY
I was raised by a father and a mother who sucked at recognizing burnout in themselves. Whenever something needed to be done at our church, my mom was doing it. Whenever there were new responsibilities that needed to be taken on at work, my dad was doing it. This resulted in ever-increasing amounts of stress for both of them and, finally, to burnout for both. What could and should have been fun, relaxing, and rewarding experiences for them became drudgery and extra stressors (on top of raising 3 boys, one of whom was me). When the weekend came around and it was time for them to relax, they kept right on working. This went on for years. Even after they were burnt out with involvement in various communities, they kept on taking on more responsibilities and pushing themselves farther than they should have ever gone.
So how can we recognize burnout in ourselves before we get to the breaking point? As before, there is no hard and fast rule. However, by asking ourselves a few questions, we might be able to figure it out. Why do you do what you do? If it's because it won't be done unless you do it, is this something that absolutely must be done? What would stop someone else from doing it? What will happen if it is not done? What are you not doing so that you can do this?

3. We, as people, should learn to say "No"
4. We, as a community, should learn to accept "No"
5. We, as a community of people, should learn to all pitch in
So how is my mom still alive and not 15 years dead with stress-related heart disease? It's a quick story: We moved to a new church. She was asked to help out with something and said "Yes" with a slightly pained look in her eyes. The person who had asked her could see that pain and told her "It's okay to say 'no' sometimes." My mom apologized and said, "No." She felt really terrible about it until things magically worked out (i.e. someone else who had some extra free time said "Yes"). It was liberating for her. It was liberating for me (I say "No" way too often, most likely).
But did you see what happened? A community member recognized that pain, knew that pain, and acknowledged that pain. When the option to say "No" was given, and my mother took it, the community accepted that answer graciously, and someone else within the community who was better equipped at that time took on the responsibility.
Granted, not all communities accept "No" for an answer. Not all communities (hell, probably most communities) do not know how to pitch in. As a result, a small group of people shoulders the burdens for entire communities, and we end up with burnout.

So, in short, to help avoid burnout, follow these easy steps:
People burning out:
Communities:

 Everyone:

0008 - My Frustration

Part of my childhood that won't die (likely for many, if not most, others) is my imagination. I like to daydream. I like to construct elaborate fantasies about potential futures, and plot ways to make those futures a reality.

Unfortunately, all of the plots I concoct center on one of a few highly improbable events:
    1. Winning the lottery (I don't play the lottery, so will never win)
    2. Finding some other source of massive income within a relatively short timeframe

As I've gotten older, my daydreams have reached less and less into the future as the window for one of these improbable events narrows each and every day. As such, I have plunged myself headfirst into the second event: finding a source of massive income. My current event? Solving the P vs. NP problem and proving that P = NP.

For those who are not familiar with this problem or are a little rusty on the particulars, here's a brief rundown with some heavy generalization:
The complexity of an algorithm can be judged by its worst case time complexity. Worst case time complexity is a measure of how long it will take to solve the given problem using the given algorithm as a product of the size of the problem.
For example, an algorithm may use a loop to add the numbers 1-N together, like so:

sum = 0
for i = 1 to N:
    sum = sum + i

This has a worst case time complexity of N (i.e. if N = 10, this will take 10 steps to complete)
If we wanted, instead, to add each number from 1 to N to each other N times, we could use the following algorithm:

sum = 0
for i = 1 to N
    for j = 1 to N
        sum = sum + i

This has a worst case time complexity of N^2, because it takes N steps N times. Both of these problems are called P problems, because they can be solved in deterministic polynomial time (i.e the worst case time complexity is N^X, where X is a finite number less than N).
If, however, we wanted to find the largest independent set of a graph using backtracking, our algorithm would have a worst case time complexity of 2^N.

Confused?

Okay, first off, a "graph" in this instance is referring to a set of nodes that are connected by edges:
A-B-C
In this graph, A, B, and C are the nodes, and edges connect A to B and B to C.
Another example:
A-B-C
  \  |
    D
In this graph, A, B, C, and D are the nodes, and edges connect A to B, A to D, B to C, and B to D.

Second, an "independent set" is a collection of 1 to N nodes that are not connected with edges. For our first graph, the independent sets are {A}, {B}, {C}, and {A,C}. In our second graph, the independent sets are {A}, {B}, {C}, {D}, {A,C}, and {C,D}. The largest independent set is the independent set containing the most nodes (for graph 1, it is {A,C}; for graph 2, it is either {A,C} or {C,D}).

To date, the best algorithm to solve for the largest independent set utilizes backtracking, which I don't want to talk about in this post. Essentially, it attempts to test every possible combination of nodes and has a worst case time complexity of 2^N (i.e. with a problem size of 3, it would take 8 steps; with a problem size of 4, it would take 16 steps; with a problem size of 10, it would take 1024 steps). This is called nondeterministic polynomial time, or NP.

Enough of that.
My goal, and what I've been working on in my spare time for almost a month now, is to prove that P = NP, meaning that problems that are contained in the NP class (such as determining the largest independent set of a graph) can be solved with an algorithm in the P class. Unfortunately, this is very difficult, and is starting to frustrate me.
This problem was formally stated in 1971, so it's something that nobody has proved in the last 44 years, though many, many intelligent people have tried. As such, I'm not being very hard on myself for not solving it yet. However, every time I work up an algorithm that seems to work, I'm missing one of two important points:
1. It's accurate (i.e. it always reaches the correct solution)
2. It's in the P class
So far, I can only get one or the other. The closest I've come (earlier this evening) is an NP algorithm that is 100% accurate that, when removing two simple loops (and thereby changing the algorithm to the P class), becomes accurate only for problem sizes < 5.

So, I've decided that, as of about an hour ago, I am going to completely scrap what I've done so far. I've been approaching and representing the problem in the same way that everyone else has. I'm reinventing the wheel over and over (of my accurate solutions, I have worst case time complexities of N!, 2^N, and N^N!; don't ask about that last one - I was drinking). Now I just have to figure out a novel approach to the problem, and that will hopefully yield better results.

Or I can buy a Powerball ticket. Either way works.

Edit: as for why solving this problem will give me massive income, please view the following links:
http://en.wikipedia.org/wiki/Millennium_Prize_Problems
http://en.wikipedia.org/wiki/Fields_Medal
http://en.wikipedia.org/wiki/Abel_Prize
etc.