Tuesday, November 29, 2011

An Update from the Void

I've been a bit quiet lately, I know. I find it's hard to talk about anything when I'm not allowed to talk about work, and I've been working hard on an unreleased project. It's been wonderfully exciting and interestingly hard, and we launched today so I can finally say (a little) about what I've been spending all my time doing.

I'm part of the indoor maps / location team. Some of you may remember that I'm somewhat obsessed with maps. Now I get to work with lots of other people who are also obsessed with maps. (Did you know that for a long time California was thought to be an island?) Surprisingly to me, there's only a small amount of Computational Geometry being used in all of this, so I've been getting a crash course in Machine Learning, which has been enjoyably educational. I am, of course, planning to inject geometry wherever I can... perhaps eventually I'll be able to give an update on that as well. Until then, I'll have to make do with telling you to download Maps 6.0 and give it a try.

Saturday, March 19, 2011

Online Courses

One of the questionable outcomes of the teacher myth has been the increase in online courses at the K-12 and college levels. (Here I mean courses taught entirely online, in which students and teacher never meet face to face and much content is learned by the students on their own by reading through online content.) On the one hand, putting information online is great (if it's open content) - students all over the world who don't have access to formal education can learn from it. Teachers can use it in their own classrooms, thus avoiding reinventing the wheel more than necessary and saving them time. But I worry that it walks a dangerous line inspired by the teacher myth: teachers are unnecessary. What about role models, emotional support, and the ability to ask questions?

Anything perpetuating the idea that teachers are unnecessary also potentially supports other problematic corollaries of the teacher myth, leading to the replacement of tenured unionized teachers with lower paid adjuncts (both at the secondary and college levels). All of this contributes to the de-professionalization of the field. So while we may be pro-online content and generally pro-technology, we should carefully consider the real consequences of being pro-online courses.

Sunday, March 6, 2011

SoCG Accepted Motion/Sensing Papers

Yes, this is somewhat delayed. Better late than never?

Here's the list of exciting-looking motion/sensing papers culled from the SoCG 2011 accepted papers list. Also known as my to-read list.

  • Mark de Berg, Marcel Roeloffzen and Bettina Speckmann. Kinetic Convex Hulls and Delaunay Triangulations in the Black-Box Model
  • Umut Acar, Benoît Hudson and Duru Türkoglu. Kinetic Mesh Refinement in 2D
  • Rishi Gupta, Piotr Indyk, Eric Price and Yaron Rachlin. Compressive sensing with local geometric features

Sadly, none of these seem to have a pdf preprint up yet, providing me with yet another excuse for procrastination...

Wednesday, February 9, 2011

A Full Day of Grading

Teachers, TAs, and professors love to complain about the amount of grading they have. But how much is that, exactly? I've seen studies that say assessments and assessment-related activities (I imagine this includes creation, proctoring, and grading) take up 1/3 - 1/2 of a teacher's time. I certainly believe it. But I thought it might be interesting/useful/fun procrastination to consider a rough estimate of how many hours per week it might be reasonable to expect a teacher (in this case, imagine a high school teacher) to spend just grading. And I found what I came up with to be rather amazing (despite all the time I've personally spent grading).

Here are my basic low-end assumptions:

  • A teacher has about 100 students (imagine 4 classes of 25 students each). These days, many teachers teach 5 classes of 30 each. Some pampered private school teachers (like I was) teach 4 classes of 15 students each. Still, 100 is a reasonable estimate and a nice round number.
  • Each student hands in one page to be graded each day. This will likely be a single sheet of homework. This excludes any tests or quizes, which are generally longer than a sheet, so this is definitely a low-end estimate.
  • Each page takes the teacher 1 minute to grade. Again, this sounds like a short time to me if you're actually grading the work. And if you also consider the time it takes to determine the full-page grade and enter it into the computer system...

These estimates lead to a need to grade 500 pages per week, which I'm estimating could take 500 minutes. That's 8.33 hours, or a full work day. Yes, a teacher could easily spend a full work day each week just grading. I find that astonishing.

Tuesday, February 1, 2011

SODA: Instance Optimality

The highlight of SODA for me was the plenary talk Computational Geometry for Non-Geometers by Timothy Chan, especially the part in which he discussed instance optimality. The basic idea is to consider algorithm analyses that take all inputs into account and operate optimally over all inputs in comparison to an algorithm designed specifically for that input (but not for that input's order). I believe this was first considered in a geometric setting (Instance-Optimal Geometric Algorithms), so you could imagine that the input is a set of points and the algorithm you're competing against doesn't know in advance in what order the points will be given to you. This wonderfully fixes the problem with worst-case analyses in which an algorithm might perform poorly on most input instances but there is some hard instance for which the performance is reasonable. Instead, under an instance-optimal analysis, the algorithm is expected to perform well on all input instances.

In the study of data structures for moving objects, a similar idea known as motion sensitivity was previously introduced under a motion-specific setting. Motion sensitivity generally describes algorithms that perform well under orderly motion and have performance that degrades as the point motion becomes more random. In my own work, I consider entropy-based analyses in order to capture this concept. In fact, the instance-optimal analysis Timothy described also resulted in an entropy-like inequality, so perhaps this relationship is inevitable/necessary for these analyses.

It's an exciting new area that I'm hoping to see a lot more of. It was certainly an excellent talk.

Sunday, January 30, 2011

SODA talks

I'm always a bit more interested in what exciting problems I'm introduced to at a conference than the proof techniques used in the solution (probably partially because the best talks often don't get into the details). So here's my report back from SODA, in the form of exciting problem descriptions.

Implicit Flow Routing on Terrains with Applications to Surface Networks and Drainage Structures by Mark de Berg, Herman Haverkort, and Constantinos Tsirogiannis - This problem was described as the "farmer's problem," the problem of determining what fields upslope might contaminate yours by draining with the flow of the water.

Shortest Non-Crossing Walks in the Plane by Jeff Erickson and Amir Nayyeri - This problem is as the title describes. The authors also consider the version in which there are polygonal obstacles. It was a nice problem and made me wonder if a variation has been solved... For public transportation networks it might be interesting to consider short walks that cross as many times as possible (or some balance of short paths and many crossings). This could probably be a variation of a facility location problem. Obviously, the polygonal obstacles would also translate in the form of neighborhoods that hate public transit and block construction attempts (or, more generously, in the form of existing buildings). Anyone know if a problem of this sort has been considered?

And here's one where I really did just like the solution...
Fast, Precise and Dynamic Distance Queries by Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz, Moshe Lewenstein, and Liam Roditty - This paper relies on a series of other nice ones about dynamic spanners and hierarchies. The first in that immediate group is Deformable Spanners and Applications by Gao, Guilbas, and Nguyen, which set up a tree hierarchy based on local distances between points in which points in the same level of the hierarchy and within some distance of each other are considered neighbors for the purpose of creating a spanner. These authors make the nice observation that the distance between points in the hierarchy whose parents are neighbors are a good approximation for the distance between their descendants. The full algorithm and proof are, of course, much more involved. (For a better description, complete with beautiful pictures, see the slides linked from Lee-Ad's homepage.)

Finally, the award for the best previous work slide goes to Maarten Loffler for his talk on the paper Triangulating the Square and Squaring the Triangle: Quadtrees and Delaunay Triangulations are Equivalent by Maarten Loffler and Wolfgang Mulzer. While I haven't been able to find the incredible slides online, the previous work flow chart can be seen on page 2 of the paper. If I drew cartoons, I'd be able to do a nice parody tribute to this. Instead, all I have is this phd comics strip about references.

Wednesday, January 26, 2011

SODA Business Meeting

I'll have technical stuff up later. For now, a report back from the longest business meeting ever (no, I have no data to support that assertion).

As ever, the highlight of the meeting was the decision on where SODA will be held in 2013. After choosing sides of the room, Miami won over New Orleans 67 to 62 (if I remember the numbers correctly). Despite a lot of yelling from the New Orleans side to clarify that Miami is not the same as Miami Beach, and grim reminders of the last time SODA was in Miami, no one switched sides. Still, it was a close vote. Perhaps the Miami decision will be overruled...

About 20 minutes after the meeting was scheduled to be over, the possibility of merging the associated workshops (ALENEX and ANALCO) with SODA as additional tracks (under the "ESA model") was brought up. There wasn't much discussion at the time, but the main worries seem to be a lowering in paper quality or the gradual dieing out of those submissions leading to a SODA as it is currently but without the associated workshops. Before the suggestion, I had been thinking a lot about why it was I had been so much more excited about ESA this past September than I was about SODA. I think the lack of experimental/practical emphasis had a lot to do with this. ESA, even the theoretical track, seemed a bit more focused on solving interesting problems. I hope SODA follows suit, whatever the method.

Thursday, January 6, 2011

Helping Teachers Helps Students

Apparently I'm doing a short (if somewhat spread out) series on education (previously here, here, and here). In this installment I'll discuss what I see as a replacement axiom to the teacher myth: teachers are the solution or helping teachers helps students.

First, a disclaimer: No one single group of people, no one single act can "fix" education. Students, teachers, administrators, parents, policy makers, and the general public are all responsible for the current state of education. (And the current state of education isn't all that bad, let's remember.) But certainly, if not agreeing that teachers are the most important, we can agree that they're important.

Many of the current educational efforts revolve around the idea of "holding teachers accountable." This often leads to efforts involving test scores and record keeping, only serving to increase the administrative burden on teachers. Teachers have a lot to do. Help them do it faster and they'll be able to spend more time actually teaching. They certainly can't become better teachers without that extra time for training, lesson plans, etc. Give teachers additional training, mentorship, etc. and they'll become better teachers. And that, in turn, will help students.

So, from a computer science point of view, what can we do to help teachers (and thus help students)? What can we automate? What tasks drain teachers' time while not giving them much in return? If you're a teacher, what tedious things do you spend your time doing? Some of these problems will likely be easy to solve, while some will require more creativity. We should tackle both.