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 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

The madness continues. A overall description of this new chording keyboard I’ve been working on. Includes the complete circut diagram including some very fancy 3D models: http://www.technofetish.net/mike/btwiddler/ubcomp1-composite.pdf

What do I do when I’m not buiding bizarre input devices? Perparing to survey CS students to find out why some of them are such nerds (and why some of them aren’t)! You can check out my survey (it’s mostly 1 big essay question though)…enter bogus data if you’d like it won’t actually affect things:

Click Here to take survey

Oh and here’s a jucy tidbit – it looks like I’m going to Sweden for a week to interview people about why they’re dropping out of Computer Science. Crazy, eh?

If it has ever crossed your mind to wonder why I haven’t been posting lately, the image above is your answer. You’re looking at the BC419143B, a microprocessor designed to output Bluetooth. In theory I will be building a chording keyboard that uses this device, but before that I had to design a circutboard for that purpose. You have no idea how long I have spent on this 1×3 inches – I do not want to think about it much myself.

Look at a slightly more complete version of the board here. And expect more information, including some details about the firmware and case, in the coming days.