Mike Hewner's Homepage

So after finally figuring out a way to get things appropriately transcoded, I had videos of me using Prezi to talk about P/NP.

Overall, I’m not sure that the zoomable interface really worked for me. What I wanted was for my discussion to be embedded in a concrete document you could take with you after the presentation was through.

I still think the idea of linking the presentation to the document is a good one. Here is the pdf that goes with the presentation.

But trying to layout everything in a small space made the visuals very busy. I don’t like that.

Having this terse version of your presentation in your field of view also I think encouraged me to be be terse and formal. As a result I feel like this presentation was a lot less fun, which is a particularly bad thing for this whole P/NP business.

When I have slides by contrast, many of them reference prepared jokes and force me to keep re-engaging the audience. Things like jokes won’t ever really be able to appear on the “one page” version of a talk.

But then again, things are always different on the other side of the podium. Anyone else willing to watch a hour long talk to tell me what you think?

P/NP Practice Talk Part 1 from Michael Hewner on Vimeo.

P/NP Practice Talk Part 2 from Michael Hewner on Vimeo.

P/NP Practice Talk Part 3 from Michael Hewner on Vimeo.

So the TAs in the class I’m observing have a problem. They’ve got some material they want to present about (briefly), but because students have a lab assignment the presentations tend to get drowned out. Students are busily trying to get started and get out as quickly as they can.

Of course, one solution is to just not post the assignment until the presentation is complete. But in an assignment with multiple parts, this tends to make for long boring lecturing. And who remembers how problem 5 was presented after doing problems 1-4 anyways?

I’ve also been encouraging the TAs to stop work every now and again and have students pair up or something to check their answers. An hour practicing the wrong technique is not gonna help anybody. But as long as the students are just trying to get done at max speed, they’re not going to be particularly reflective as they compare answers.

OK, solution-time. I wanted a way to post a static page with encrypted sections. That way the TAs can just write the password on the board – they don’t have to have multiple files, or login anyplace to “enable” stuff.

So I built a library using jQuery and Gibberish-AES to do that. The main thing was trying to make it easy to write these homework pages. Here’s my instructions:

1. Write your webpage with the various sections you want to hide
   surrounded by div tags with a password attribute. Like so:

   
   This is a question.  But I don't want it revealed till 
   you enter 'foo' in the password box.
   
   

   Of course the password should be whatever you want the password for that section to be.

   The webpage can be just about as fancy as you need it to be. But you must have a

   and tag pairs. Certian kinds of tricky javascript may also have some problems.
2. 2. Include my javascript library in your page, by adding this to the head:

   or, you know, copy that javascript to wherever you want to and point the page there.

3. When you load your page now, every div that you marked with a password should now be invisible. For double checking purposes a label should be there pointing it out and indicating what the password is. To make sure everything is working properly, type your passwords into the box at the upper left and be sure everything is appearing like you think it should be.
4. Click the link on the bottom of the page to show code. You should see all the div contents has been replaced with encrypted strings. Sanity check to make sure the HTML looks fine…the replace mechanisms aren’t 100% bulletproof.
5. Cut and paste that code into a new HTML file you distribute. That’s all you need to do!

You can see a page in action as well as the student view.

What do you think? Is this the easiest way? For the curious, here is the source code.

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?