Problem Solving

Finding Community

sdenton4

I attended a really nice talk by Arash Amini yesterday about detecting ‘communities’ in sparse graphs.  The basic problem is: In a big graph (like the Facebook graph, or the graph of scientific papers citations) you have clusters of friends/associates, and you want to pick out those clusters. Dr. Amini and his collaborators have been working on methods to solve this problem in particularly noisy cases.  The methods presented were developed for cases where you know the specific number of clusters you are seeking to find.  It was a fascinating talk, and I came away wondering if there are good methods to use when you aren’t sure of how many clusters there are.

communities
At the left is a randomly generated block-diagonal adjacency matrix (using a stochiastic block model). The center is the same matrix with the rows randomly shuffled; you can’t “see” that it has block diagonal structure. The right is the matrix with blocks recovered using the techniques outlined in this post. Note the noise in the lower-right corner; these correspond to individual, isolated vertices that ended up in their own clusters.

Continue reading →

Escape From the Box Factory: Better Single Variable Optimization Problems

sdenton41 Comment

I’m teaching an intro calculus class this year (specifically, ‘Math for Life and Social Science’), and came a while ago to the section on optimization.  It’s a really important subject, and yet the optimization problems one finds in Calculus books (even good ones) tend to be contrived examples which I refer to as ‘box factory problems.’  Things along the lines of ‘minimize the surface area of a rectangular box with volume 1000 cm^3‘.

Hey, kids! Let's take a field trip to the box factory!
Hey, kids! Let’s take a field trip to the box factory!

These are fine for a problem or two: There’s a useful skill in taking a real-sounding problem and translating it into the mathematics you’re learning.  We use the constraints (in this case, on the volume) to reduce the number of dimensions, turn the problem into a one-variable calculus problem, and then solve.  All well and good, but these problems somehow completely miss the impact of optimization on society at large.  Largely because the optimization problems that occur most commonly in the wild have a slightly different flavour.

Problem: In Boston, we observe that the monthly rent for three one-bedroom apartments are $1300, $1150, and $950.  Rent on three two-bedroom apartments were $1500, $1700, and $1200.  Assuming that the cost of a 0-bedroom apartment is $500, find the best possible line describing the rent as a function of the number of bedrooms. Continue reading →

LakeHub Game Design Workshop

sdenton43 Comments
Ligretto is a fast-paced game of breaking glass. (That one in the upper-left corder exploded about ten seconds after this picture was taken.)
Ligretto is an awesome fast-paced game of breaking glass. (That one in the upper-left corder exploded about ten seconds after this picture was taken.)

LakeHub has been churning steadily along; we had our third event on Saturday, and it was quite successful according to me and everyone else I’ve talked to.  We’ve settled on a basic format for the time being, with an event happening every Saturday from 1-5pm.  Half of the time these are big group-oriented events with demos and big inclusive activities, and the other half of the time they’re ‘hang-outs’ where people get together to work with other tech-oriented people nearby, and to check in with ongoing study groups.

There are three study groups started already: one on microcontroller programming, hosted by Peter Mbari of Access Energy, one on javascript and web development hosted by Simeon Obwogo from IPA and James Odede of the Maseno ICT Guild, and finally a group doing game design, run by yours truly.  We wanted a less-technical group to complement the other two programming-heavy study groups; luckily I know some things about games, and game design is actually really useful in thinking about business and web technologies.  Especially with ‘gamification’ as a big buzz word.  So this week I’ll talk a bit about games, to get my mind going on the subject!

Continue reading →

Towards a Sage Problem Server

sdenton4
Layout of resources for a hypothetical Sage problem server.
Layout of resources for a hypothetical Sage problem server.Django

Problem Statement.

I’ve finally been making some progress towards building a Sage-based ‘problem server,’ as we were talking about way back in January.  It’s clear that the tools developed have a wide scope of use.  Before building something that gives open questions and reacts in really interesting ways to input, a stepping-stone is to build something that serves up individual math problems and asks for an answer.  In some sense, such things are already done by Webwork and Moodle with varying degrees of success, but building a nice implementation would allow some new directions.

Now, I should stress that I think WeBWorK is pretty awesome, and has some really transformative potential.  I’ve been encouraging its use in Kenya, and it’s been extremely interesting seeing it used in service courses in Strathmore University and now Maseno.  These are places with ever-increasing class sizes, and a well-designed online homework tool promises to greatly improve student comprehension of the course material.  The big database of existing problems in WeBWorK is also really helpful; there are over 26,000 problems in the Open Problem Library.  There are three issues with WeBWorK that a new implementation could/should address:

  1. Modularity: WeBWorK is a pretty monolithic piece of software.  It includes three essential components: a problem server, a problem database, and a learner management system (LMS).  Basically, these should be busted out into three genuinely separate components.  Breaking out the problem server allows easy integration into Moodle or another well-thought-out LMS, or else integration directly into things like online textbooks.
  2. Modernization: The WeBWorK codebase was mainly developed some time ago, and new versions are slow to come out.  (The last stable release is from December, 2010, over two years ago.)  The interface is also decidedly…  Clunky.  There’s a natural question of how one could improve the system using modern AJAX-type tools.  Better interactivity will lead to a much better user experience.  Things like one-button signup with Google or Facebook accounts is one thing I can think of off the top of my head that would greatly improve the user experience.
  3. Ease of Writing Problems:  Currently, WeBWorK problems are written in a highly idiomatic version of Perl.  I was interested in writing problems a couple years ago and got the feeling that it was, in the end, a bit of a black art.  The documentation is a bit scant, and most mathematical objects have their own idiomatic libraries.  Switching to a python/sage framework would mean that writing problems should become much easier: Sage already recognizes all of these mathematical structures.  And if the problem definitions are in python, we’re really using the same syntax as our Sage work.  This should make it much, much simpler to pick up a bit of Sage and then start writing problems.

Continue reading →

Looking Forward

sdenton4
Most projects seem to involve staring quizzically at a computer screen.

As the term gets underway, I’m working on a number of projects trying to address some of the issues that I discussed in the Looking Backwards post…  I was chatting with Thomas Mawora yesterday, listed off all the ongoing projects I could think of, and came up with five.  (Or up to seven, depending on how you count it…)  It’s a lot, but luckily there’s a good deal of overlap, so work in one place often helps another project move forward.  If you’re going to spread yourself thin, you might as well be maximally efficient about it.

Continue reading →