Parallel Algorithms part XXX

Disclaimer:  If you have not taken a course in complexity theory of computation (or if you have a life), you might not find this post all that entertaining.  Just be warned.

I'm in a Parallel Algorithms Theory class right now, and since I've already taken a few classes in parallel programming and had lots of experience, I thought it might be insightful.  Unfortunately, I learned the truth about the class today and am still trying to find the missing link to reality.

It seems that there are three general steps to creating a "work-time optimal" algorithm.  These are, in order:

1. Assume an extremem number of processors, such that p>>n. This works best for doing something trivial, such as searching a sorted array for a given element. n can be any arbitrary number between one and the size of an integer (around 4 billion).
2. Create a convoluted algorithm such that:
• The number of parallel steps is very small (Try getting close to O(log log n) )
• The number of steps required to orchestrate parallelization and setup is significantly large (preferably close to n²)
3. Hand-wave and use several mathematical approximations with Big-Oh to show that your new algorithm is actually constant time O(1).

Once this has been done, publish your results and teach a Parallel Algorithms course.

Everything's Bigger in Texas

Well, I've been silent on the blogging for some time, but since I'll be away from home for a while, I figured I'd start it back up.

This past summer, I decided I wasn't living life "on the edge" enough, so within a ten-day time period, I bought my first car, graduated from BYU (a two-day affair), drove 22+ hours to an entirely new state (and almost country), and started graduate school at the University of Texas at Austin.  Oh.  And within 14 days, I had caused $1400 worth of damage to an otherwise steal-of-a-deal car.

I rather like it here.  I didn't really have many expectations, other than the oft-repeated statement of pride, "Everything's Bigger in Texas," so I was pleasantly surprised.

First, everything is bigger in Texas.  I ordered a glass of water at a local Tex-Mex  restaurant ("it's authentic," Alyse's family said—which begs to question the authenticity of a food type that contains the state it's cooked in and the country from which it is influenced in its title), and it really was bigger.  You can see the straw barely poking up over the top on the back side:  I only needed refills once instead of the usual 6 or 7 times.  I'm glad I'm not in Germany.

I also like the openness of Austin.  Since Alyse served a mission here a few months ago, she drove down with me and stayed with her family.  Taking her home after we'd finished our day's festivities, we drove through the countryside.  I would have parked my car, got out and enjoyed the full moon and big farms (or at least rolled down my window to take in the smells) had it not been for the 80 degrees and 95% humidity at 11:30 at night.

Mostly, I love everybody's inner yee-haw. Walking from the institute building to school today, I saw a group of workers including a Hispanic man wearing cowboy boots.  He's real Tex-Mex.

Maybe I'll grow to love this place.  And maybe, during the cooler months this "winter," I'll even wear my cowboy boots once or twice.  Just for kicks.

Tweeting (and Old Men)

When Bishop Burton talked about “tweeting” in Tuesday’s campus devotional, I was only mildly surprised as the girl sitting next to me confessed she didn't know what Twitter was. It’s impressive, especially for how old they are, that the leaders of the Church are so in-touch with the latest technology. Texting and blogging are regularly mentioned in General Conference, even from the older members of the Quorum of the Twelve Apostles or First Presidency. I find this especially fascinating when my own father—a computer science professor—occasionally demonstrates ignorance to such developments. On the other hand, the horrible encounters I frequently had with the Church's email on my mission make me question the reality of its progression. I especially get a kick out of Church leaders like Brother VanDenBerghe who enthusiastically support electronic greeting cards as “a quick and easy way to let [a sick friend] know [they are] concerned.” Now that I think about it, isn't it somewhat ironic that Bishop Burton decided the best format for the tweets from his latest General Conference talk was in twenty-five pages of printed text?

"Am I Addicted?"

Sometimes I wonder if I have an addiction. In reference to this self-proclaimed obsession, I told myself a few months ago, “If I can find a girl with whom I enjoy spending more time than I do with [my addiction], I’ll get married to her quick.” Dr. K’s Ensign article gives several factors for identifying an addictive tendency, and quite a few of them fit. I do “play” compulsively, often for longer periods than I had planned. Frequently, I “have difficulty stopping,” and even when I am not “playing,” I find myself “[obsessing] about the game, plotting and planning [my] next opportunity to play.” Occasionally, my schoolwork suffers because of the time and energy I spend with this activity, and my sleep patterns have changed since I “became involved.” Perhaps I should seek help or counseling, but I don’t think my research mentor would approve—after all, the more time I spend on this “addiction,” the closer we’ll get to another publication.

Although perhaps this “addiction” is worse than I pretend...

Swine flu? Bah. What about real viruses?

I’ve been extremely frustrated with my Internet connection for the last few months. Apple Care blamed the problem on my ISP, and my ISP told me it's a problem with my computer. To make matters worse, obtaining relevant support from tech guys is nearly impossible (most of them aren’t native English speakers and the ones that do speak clearly are incredibly incompetent). So when I finally got a guy on the phone last night who actually knew what he was talking about, I was incredibly relieved. After spending a long time troubleshooting, he informed me I probably had a virus causing a "DNS flood attack." Internet security has changed a lot in the past few years. Before, it was sufficient to not download strange files and avoid a pornography or gambling addiction, but now you have to worry about strange Internet security threats and your wife becoming addicted to online chess. There’s no telling what will happen in the next twenty years.

Column A and Column B

I recently took the GRE. Again. I think I was hoping that by some stroke of luck, the gods would show their favor and grant me the knowledge I needed to ace the darn thing without studying. You can imagine what happened. Returning from the whole ordeal quite frustrated, I was pleasantly surprised with the slightly vindicating lecture given in my Computers and Ethics in Society class on “The Orders of Ignorance.” I quickly concluded that, while I could feel the strain of first-order ignorance many times during the GRE, I was rarely allowed to show my capacity with second- or third-order ignorance problems, which meant that the test did not show a true characterization of my intellect.

Which is funny, now that I think about it...

In Thomas Friedman’s "The World is Flat: A Brief History of the Twenty-First Century" (which is neither brief nor a complete history), the author describes the “flattening” of the world as the product—and future—of the 21st century. With a thorough flattening, businesses will perfect the practices of outsourcing, insourcing, and off-shoring. Technology and businesses will spread to other countries in an entirely symbiotic relationship.

Why is this so funny? Well, let’s look at the future of the flattened world. If Friedman is right, the world is progressing on a course of ultimate flatness. Eventually, open-source software will rule, putting money-hungry companies like Microsoft into the dust. Outsourcing for super-giants like Wal-Mart will be taken to an extreme: having completely exhausted the supply of cheap labor in developing nations, they will turn to robotic labor, which is both cheap and entirely obedient. Because of global expansion and the need for a unified language, the "one tongue to rule them all" will incorporate major sounds from every culture on this planet. When everything seems like it’s running the smoothest, the South Africans will suddenly realize nobody can pronounce their favorite clicking words. The wealthy Singaporean doctors will realize they’ve been replaced in the operating room by a twenty-dollar automated surgeon. Soon even the open-source programmers formerly playing with projects in their "spare time" will realize that, upon loosing their day job at the industry giant, they’ve been forced to take three part-time jobs flipping burgers at McDonalds (the only company who refused to hire robots).

Looking back on this madness, the world will see that while standardized testing like the GRE has the intention of providing an even playing ground for everyone, it only serves the purpose of making everyone homogenous. What the world really needs is not an enormous department store selling everything as cheap as it can get. Nor does it want every computer be a Dell because they can ship them the fastest. What it needs, instead, is innovation. A grocery store that sells only eggs because that’s its specialty. A computer store that sells computers of such high quality it can only make a few in a year. And especially, the world needs individuals who, on occasion, can see how the information displayed in “Column A” really is greater than “Column B” even though the practice GRE says otherwise.

That’s why I’m going into academics.

"Shawty fire burning on the dance floor..."

Interesting. I don’t quite understand it, but just a few days ago, I found myself frustrated that my carillon professor had assigned me a very simple song. “Me? A Clement? Being assigned a piece I could easily perfect in a week? That’s it. I quit.” And I set the music aside. Frequently, I've noticed that when I have no desire to perform, I always do poorly. I was reading an article with the abstract topic of LINUX design and realized the quintessential characteristic for designing an impressive piece of software is motivation. Sure, you need to be able to conquer second or third order ignorance, but burning the midnight oil and waking up before your roommates on a Saturday morning will place you further in line than anything else.

Perhaps the reason my carillon playing went over poorly is that I'm just burned out with school. Homework and studying is almost too much for me. Reading something uninteresting is about as much fun as straining spaghetti noodles for a living: a lot goes through, and you get a little bit of money for it, but nothing ever sticks.

So how do I get the motivation?