Mike Hewner's Homepage

I wanted to have the color of my term-mode mode line switch, depending on whether I was in character mode or line mode. I’m not sure why this became an overwhelming desire of mine, but it did. Not really knowing anything about emacs font faces, themes, or anything I pulled up my debugger and started spelunking in color-theme-buffer-local. I discovered a mysterious function face-remap-add-relative designed to do exactly what I wanted – let me remap a particular part of a single buffers theme and then undo that mapping when finished.

A smarter person might have checked the emacs manual and saved himself a lot of time.

Here’s how it works:

;; set the modeline background color and save a "cookie" so the change can be undone
(setq old-term-color (face-remap-add-relative 'mode-line :background "dark goldenrod"))

;; undo that change later
(face-remap-remove-relative old-term-color)


Interestingly, I’m pretty sure this ability to change colors for a specific buffer is one of the new features of Emacs 24. Yay progress.

So I have a new homepage at hewner.com. I’ve been thinking for a while that I ought to have a page with my various research, teaching, and programming stuff that I would be comfortable pointing folks to, so I’ve upgraded the old buffaloblog into your one-stop Mike info-porium.

One of the consequences of this is a new url for my blog (hewner.com/blog for the blog and hewner.com/feed for the RSS)…but if you’re reading this through your feed reader then all the redirecting worked as I intended it. One thing I did discover in this process is that WordPress supports category specific feeds – so if you’d rather never again hear me wax philosophical about my attempt teach P/NP to cats .

I’ve had a lot of fun playing with WordPress in the past few days; WP strikes a nice balance between giving you the configuration features you need and letting you have at the code when that needs to be done. The plugins I ended up using are:

• Akismet and Bad Behavior – Avoid blog spam
• List Category Posts – Lets me put blog post summaries on the Teaching and Programming pages
• Excluding Pages from Navigation – Lets me have extra pages that don’t appear in the navigation. I really don’t know why this feature doesn’t exist by default.
• Online Backup for WordPress – Backup WordPress DB
• Syntax Highlighter Evolved – For code snippets
• Twitter for WordPress – Twitter feed on the side
• This post helped me set up the old buffaloblog urls to redirect to the new hewner.com urls

Anyways, feel free to check out the new homepage and let me know what you think.

So it looks like I’ll be spending 6 weeks of my summer at Georgia’s Governor’s Honors Program (GHP). Students get assigned to a major and minor and basically get 6 weeks of super-intense boarding school. They apply for this, and some don’t make the cut.

I’m looking forward to GHP. I’m looking forward to the chance to teach a completely different group of students. This is kind of class teachers dream about – intelligent, motivated, naive enough to believe your lies. The CS classes will be in the context of a mathematics curriculum which I suspect will present its own challenges. I’m also looking forward to hanging out with a group of professors who would sacrifice 6 weeks of their summer to live on-site and get paid not much. That I think will make for some awesome lunch discussions.

A third perk is the opportunity to teach “seminars”. These are short evening classes that basically can be about anything you can convince a few students to come by and hear about. I’m hoping to use this to try out all the wacky neat-o technologies and techniques I never have an excuse to inflict on the students. I’m already thinking of dusting off my Big O and P/NP lectures. Why? Because I am insane. Maybe also one on Kodu, a super easy game framework by Microsoft that may have little pedagogical purpose but there is something to be said for making a game in 5 minutes using only an xbox controller. And perhaps something with microcontrollers…who knows?

What about you blog-reading people? What fun thing would you just like to inflict on a bunch of high school students? Group theory? Celluar Automata? I am all ears.

For you Seattle-ites: when I’m not tormenting the youth of Georgia, I plan to be in Ben’s place once again living like a drifter. A drifter with a unwavering, ninja-like focus on writing his proposal. But this drifter would not mind grabbing a coffee or drink with any old friends who happen to be out in his direction. I’ll be there from early May to mid-June.

Even though I really don’t play with my hardware toys much anymore, I keep an eye on the hardware hacker blogs. So when I heard rumors of the CUI32, I admit that I was salivating a little. I told myself it might be a good platform to teach a summer workshop to some high school students. This is like a star-wars fan telling you the $45 Bobba Fett miniature he just bought is “for his kids”.

But the is pretty hot. Designed for USB. Built in BASIC. Plus there seems to be a built-in bootloader so you don’t need an external programmer.

There is not a ton of documentation for this device. In particular, I had a heck of a time figuring out how to get Linux to communicate with its serial BASIC tty interface. By doing a “ls /dev/tty*” I could see there was a serial device called “/dev/ttyUSB0”. But how to talk to it. I tried minicom but it kept giving me errors. I was wondering if there was some mysterious undocumented setting about party, flow control, or some other madness that I never really understood.

Then I tried putty.

putty -serial /dev/ttyUSB0

Worked like a charm.

Awesome is my favorite window manager. It just warms your heart to see it running there in the process list whenever you do a ps –wwaux. And the fact that it is a very nice, flexible tiling window manager is just icing on the proverbial cake.

But it always annoyed me that it didn’t integrate with gnome. I like my drop down application list, complete with wireless control panels and shiny point-and-click applets. Maybe it’s a sign that I’m comfortable enough with my geek-cred that I can admit that. Of course I set all that stuff to autohide so no one looking over my shoulder can can know that I have wimped out.

Now I’ve figured out how to get it working properly. The details are all here: http://awesome.naquadah.org/wiki/Quickly_Setting_up_Awesome_with_Gnome

With the help of the textbook associated with the graph library I was using, I was able to build some graphs that require exponential runtime. Actually, factorial runtime which is slow, as my laptop’s second processor can attest to at this moment. The key to defeating the algorithm was to come up with a graph that was Biconnected but had no Hamiltonian Cycle. Once I had that, it was easy enough to to attach it to arbitrary-size complete graphs. The algorithm always checks the edges in order, so having this “unhamiltonianable” appendage stuck onto the end forced it to try every permutation of the first n – 7 vertices.

This may not be the most elegant solution ever, but it is a bit gratifying to know I haven’t completely lost everything I learned in algorithms class.

An for those who are curious, here, is an honest-to-goodness graph of an exponential algorithm sucking for real. Not quite as smooth as I would like, but then again I don’t think I’ll be able to get n = 20 even if I let this thing run overnight.

This is a question any theory-oriented friends of mine should feel free to jump in on.

So I wanted to make some graphs for explaining Big O. And I wanted to include exponential functions on that graph. But unlike my previous examples of such things, I didn’t want to say “oh wow, look at this graph of 2^n….see how terrible it is” because I know that real exponential functions in practice are often much happier than 2^n. I wanted real run-time data, ideally using source code from some trustworthy seeming source (i.e. not me).

“So heck,” said I, “surely Mathematica has implementations of some of these famous NP-Complete problems. I’ll run some of those and I think that that’s at least plausibly trustworthy.” So I poked around and found some graph algorithms – specifically traveling salesman and Hamiltonian cycle.

Then came the difficulty of generating good problem examples. I initially thought I’d just use random graphs but the runtime varied so much it just wasn’t reasonable. Then I noticed that if I passed in complete graph to Hamiltonian Cycle with one completely disconnected vertex, the Hamiltonian Cycle algorithm would be pretty dang slow:

But was it really exponential? This is where I’m stuck. I don’t really understand the algorithm that’s generating these solutions – for all I know it might be detecting the disconnected vertex (albeit somewhat late) and might be evidencing merely some (bad) polynomial time.

HamiltonianCycle[g_Graph,flag_:One] :=
        Module[{s={1},all={},done,adj=Edges[g],
                e=ToAdjacencyLists[g],x,v,ind,n=V[g]},
                ind=Table[1,{n}];
                While[ Length[s] > 0,
                        v = Last[s];
                        done = False;
                        While[ ind[[v]] < = Length[e[[v]]] && !done,
                               x = e[[v,ind[[v]]++]];
                               done = !MemberQ[s, x] && 
                                       (Length[s] == 1 ||
                                        BiconnectedQ[DeleteVertices[AddEdges[g, {{1, x}}], Rest[s]]])
                        ];
                        If[done, AppendTo[s,x], s=Drop[s,-1]; ind[[v]] = 1];
                        If[(Length[s] == n),
                                If [MemberQ[adj, Sort[{x, 1}]],
                                    AppendTo[all,Append[s,First[s]]];
                                    If [SameQ[flag,All],
                                        s=Drop[s,-1],
                                        all = Flatten[all]; s={}
                                    ],
                                    s = Drop[s,-1]
                                ]
                        ]
                ];
                all
        ]

Does that look familiar to anyone? Any guesses to Big-O for this kind of input?

OR – say you wanted to provide an example of real running exponential function. What would you use instead of my Hamiltonian Cycle hack?

There are still quite a few problems here.

Also, I’m not sure that allowing me to do re-takes on my introductions is a good thing. I just never feel like I’ve done it properly.

So those of you who have been chatting with me recently know I’ve had my eye out for a layperson level introduction to what P/NP is. Why do I care? Well, this is something high school students have heard of and occasionally ask me about. I feel like the idea isn’t really THAT hard but almost every explanation I’ve looked at tends to require knowledge about things like nondeterminstic Turing machines.

So I ran across what seems like the best intro I’ve read thus far. It’s a little light on the exact details and tends to assume you understand what “polynomial time” is, but it does make things sound cool.

If you are aware of a better explanation, I’d love to hear it:

http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext

So I just passed my qualifying exams. These are a traditionally significant hurdle in the Ph.D. process. The point of qualifying exams is to ensure you’re familiar with your area’s literature and can do research. Every Ph.D. program is different but for me the quals consist of:

1. A 8 hour written exam where you answer 4/7 essay questions, drawing on the quals reading list
2. A 4 hour written exam where you answer a personal question, drawing on the quals reading list and ~20 selections you worked out with your advisor
3. A 1.5 hour oral exam where you present your research to a committee of 4 faculty and respond to their questions

I just finished my oral and officially passed (the professors were actually less aggressive than I thought they would be…it wasn’t too bad). Yay! Now time for some slacking…