Wednesday, November 30, 2011

Conferences and Arxiv. Utilitarian values.

Yesterday I took a look at a few abstracts of papers accepted at STACS 2012. I must have been in a contrarian mind, because two remarks came to my mind, both going against my usual sense of what's desirable.

First, I was struck by the existence of prior publications on Arxiv. It is no longer exciting to look at lists of papers accepted at a conference: that's not where we learn about new results, but on Arxiv. I knew that, but this brought it home for me: conferences no longer serve the purpose of quickly communicating the latest research results. That was a major service they were doing, perhaps the main one, and that is no longer the case.

Then, why bother look at such a list at all? Because, in areas outside my own small subarea, I don't follow and can't judge what's appearing on Arxiv, so the conference committees provide a useful filter. Why do I care what happens outside my own small subarea? Truly, I do not care very much, but if a big result comes out, I would like to hear about it. Why? So that I don't sound stupid at parties when people ask me about it; and because of some guilty feeling that I ought to be broader, even if I don't really feel like it. In addition, I am always interested if some research happens that might provide good teaching material. Finally, there is a little bit of curiosity: a good talk given by a good speaker on a good topic can be enjoyable even if it's not my area. (Then, it does not even have to be Theory, and in fact, not even Computer Science.)

Those reasons suggest that I do not need to look at lists of accepted papers other than STOC and FOCS, and that I would benefit from those lists more if they were even more selective. I do not want STOC and FOCS to be more selective, but I personally might appreciate it if they were a two-tier conference.

Second, I have recently criticized Oded Goldreich's latest essay on Luca Trevisan's blog, but looking at the abstracts of papers accepted at STACS, I could not but recognize the turns of phrase that he lamented. Consider, for example, the paper I mentioned yesterday. Here is the full abstract: The Travelling Salesman Problem is one the most fundamental and most studied problems in approximation algorithms. For more than 30 years, the best algorithm known for general metrics has been Christofides's algorithm with approximation factor of 3/2, even though the so-called Held-Karp LP relaxation of the problem is conjectured to have the integrality gap of only 4/3. Very recently, significant progress has been made for the important special case of graphic metrics, first by Oveis Gharan et al., and then by Momke and Svensson. In this paper, we provide an improved analysis for the approach introduced by Momke and Svensson yielding a bound of 13/9 on the approximation factor, as well as a bound of 19/12+epsilon for any epsilon>0 for a more general Travelling Salesman Path Problem in graphic metrics.

Before I read his essay, I would not have noticed anything special about that abstract. But now, I can see the choice of arguments. Except for the first sentence of the abstract, everything else reads like a list of Olympic race athletic records - an empty race for ever-better approximation factors, with no concern for the underlying structure. The approximation factor has become, not just a (key) indication of the understanding of the problem, but a goal in itself. As I read that, I was a little bit frustrated: I wanted a hint of how the author got that improvement to an important result! What did they learn about the problem, that Moemke and Svensson did not know?

Then I remembered Goldreich's essay.

Strike one for utilitarian instrumental values.

Update: Just to make it clearer. I like the result, I think it's worthwhile, I am interested, I would have been happy to do that research and be an author of that paper. My only quibble is with the style of the abstract.

Tuesday, November 29, 2011

STACS 2012 list of accepted papers

The STACS 2012 accepted papers are out. STACS is in Paris and starts on February 29.

The most noteworthy article for my taste, at first glance, is the 13/9-approximation for Graphic TSP by Marcin Mucha, available here. (In some sense this is old news: the paper will be presented at STACS, but was published on Arxiv in August.) They improve the analysis of the Moemke-Svensson paper from last Spring (presented last month at FOCS; was published on Arxiv in April).

Here's a quote: We present an improved analysis of the cost of the circulation used in the construction of the TSP tour/path. [...] The circulation used [by Moemke and Svensson] consists of two parts: the ”core” part based on an extreme optimal solution to the Held-Karp relaxation of TSP, and the ”correction” part that adds enough flow to the core part to make it feasible. We improve bounds on costs of both part; in particular we show that the second part is in a sense free. As for the first part, similarly to the original proof of Moemke and Svensson, our proof exploits its knapsack-like structure. However, we use the 2-dimensional knapsack problem in our analysis, instead of the standard knapsack problem.

Monday, November 28, 2011

Who is in the computer science building at 11pm?

Today I came by the computer science building at Brown around 11pm. There were a dozen undergraduate students in the atrium, taking a short break from work or eating a late dinner, and each of the computer labs had about 10 undergraduate students working.

That's a lot of students.

They work there. They study there. They debug there. They go to class there. The eat there. Sometimes they take a nap on a couch there. That's the computer science subculture at its most extreme!

Maybe one of the classrooms should be converted into a dorm with bunk beds, Appalachian-hut style. That would save the students some money.

Sunday, November 27, 2011

The Khan academy on the foundations of computational complexity

The other day i watched some Khan academy videos about substraction and about multiplication.

The ones about subtraction said something along the following lines:
"How do you compute 5-3? Here is one way. Say that you have 5 lemons. Here I am drawing 5 lemons. Minus 3 means that you remove 3 lemons. Here I cross them out. How many are left? Let me count: 1,2. There are two lemons left, so 5-3=2." After presenting some other methods based on the number line, he then moves on to the next step: "How do you compute 67 - 34? You could do the same method as before: draw 67 lemons, cross out 34 lemons, and count how many lemons are left. That would work. It would give you the correct answer, but it would take a really long time. So, now I am going to give you a way to do it faster." He then moves on to explaining how to substract the ones digits and the tens digits separately.

The one about multiplications went along the following lines:
"How do you compute 4*3? Here is one way. 3 is 3 cherries. Let me draw 3 cherries on a row. I do this 4 times, so I draw 4 rows that each have 3 cherries. Then I can count: 3+3+3+3 equals 12, so 4*3=12." After presenting equivalent methods, he then moves on: "But what happens if your numbers are really big? For example, if you have 100 lemons, drawing 100 lemons on a row would take a really long time. And if you wanted to compute 100*100 with this method, you'd have to draw 100 rows that each have 100 lemons, and then add them all up: that would take forever. Here, I am going to show you a way to do it fast, even with really big numbers."

One might say: what's the big deal? Of course, when I teach the multiplication algorithm in class, I remark that doing the computation in unary is inefficient, but I always thought: "Why bother mentioning that? Who in their right mind would work in unary?" it hadn't crossed my mind before that there was a natural reason to bring that up, and so my remark goes by unnoticed.

The narrative in those videos is amazing. I am so impressed with this man! He is laying the foundations of asymptotic analysis of algorithms, explained to first graders.

Friday, November 25, 2011

Teaching deterministic linear time median

When I teach Algorithms, one challenging lecture is the one where I present the deterministic linear-time algorithm for median-finding. The big challenge is: How can we present the algorithmic design so that it is natural? I had an idea: I could simply watch online videos and see how others do it! So, I found and watched videos of lectures at Stanford (by Tim Roughgarden) and at MIT (by Erik Demaine) on that topic. For a teacher, it is fascinating to watch how others go about teaching the same material as you!

I have picked up a couple of ideas from Erik's lecture.

First, the runtime analysis involves some quantities with floors and ceilings. I always sweep the floors and ceilings under the carpet (with a vacuum cleaner). Erik, on the other hand, gave a short, relatively polished analysis, that managed to take those into account rigorously without making a mess of the analysis (well, except that he is assuming without saying it that T(n) is a monotone function of n, but none of the students noticed that gap in the proof). I may try to copy his approach when I get to that point.

Second, like me, in the design phase Erik highlights the use of transitivity of ordering: if a < b and b < c then a < c. I realized while watching him that I could highlight that already when I teach Quicksort: why does Quicksort give a correct output? Because of transitivity: if a < pivot and pivot < b, then a < b. That explains why we are doing the correct thing when in Quicksort we commit to placing a to the left of b. For Quicksort, that part of correctness is obvious and usually goes without saying. For linear-time medians, it comes up much less naturally and is actually a "creative" step. But if I have taken a minute to bring it out while teaching Quicksort, then it will seem more natural when I bring it out while teaching linear-time median.

So, watching those videos was mildly useful. Unfortunately I did not find what I was looking for: the challenge of presenting the algorithm in a natural manner is still open, as far as I know.

Thursday, November 24, 2011

The Khan academy on insertion sort

The Khan academy puts 8-minute youtube video lectures (and a few exercises) on the internet to teach all sorts of topics in an online fashion. I just realized that there are some lectures on computer science, and I have watched a few with great interest. I was mesmerized by the lectures on insertion sort - I taught that in class just a few weeks ago. My thinking was: could I borrow some ideas from that renowned teaching style?

The instructor is careful, thorough, and incredibly patient. He follows a well-trodden path to communicate, but does not announce signposts explicitly as a general paradigm for problem-solving.

Signpost 1. Define the problem: he does that in a very concrete way, using an example. For sorting, there is only one possible ambiguity in the problem definition: what about duplicates? He deals with that without explicitly drawing the student's attention to it, just by checking his program with an example that has duplicates.

Although I would also use an example, I am more explicit and state the problem definition in terms of a pair (input, output). Why? Because I don't want students to only learn about sorting: I also want to inculcate the notion of computational problem, that they will see later in many more advanced Theory courses.

Signpost 2. Explain the algorithm by executing it slowly on an example.

I would also do that if it was the beginning of the semester, but in addition to what he wrote on his electronic blackboard, I would write down comparisons as I perform them: instead of just saying "we compare 3 to 7", I would write down "3<7" on the side. Why? Because I will at some later point want to analyze the runtime, and for that, I might want to focus on the number of comparisons: highlighting the comparisons is a good preliminary perspective that will come in handy later.

One minor thing I really did not like was that he kept calling elements "the zeroth element" for the first element, "the first element" for the second element, and so on. I am resolutely opposed to molding the English language after conventions used in programming languages.

One major thing is that the instructor explains how the algorithm works, but not how one would come up with that algorithm in the first place. In his place, I might try to ask a leading question to get my unknown audience to come up with the algorithm. Why? Because I try to teach, not so much specific algorithms, but how to design algorithms. For example: "One way to go about it could be called "sort as you go": scan the entire list, and, at every step of the scan, try to make sure that everything you have scanned so far is sorted." Then I can show intermediate steps in the execution - the desired state of the list after processing the first item, the first two items, the first three items, etc. And only then would I discuss how to fill in by processing each additional item scanned. That's a modular approach, and hopefully after I have stated the "sort as you go" idea, many students can figure out the rest of the algorithm. It would, maybe, stimulate the students' creativity a little bit more.

Signpost 3. Write code for insertion sort in Python.

Before that, in his place I would first have written some high-level pseudo-code. Why? As a preparation, I suppose, for more difficult problems, settings when it is imperative to lay out the algorithm before starting to code.

The way in which he explained his code was slow and very intuitive. However, I noticed that he wrote and explained the code in a very linear fashion, line by line. That's not the way we do it: we always go for a modular presentation, starting with incomplete code that contains some "..." in places, and filling in the details during a second pass. For insertion sort, the difference is not huge, but that bothered me slightly.

He then ran it on an example in the end, as a way to implicitly suggest the need for testing. I would have been more explicit about that need.

Signpost 4.Execute the code step-by-step on a small example.

I skipped much of that presentation, but he did exactly what I do in class after I have presented an algorithm, when I am not 100 percent sure that the students understood it. Fortunately it's automated in our scheme (Racket) environment: one of the options when running a procedure in our programming environment is to do it not all at once but step by step, with highlights showing what parts of the code are being executed and what the current values of interest are.

Signpost 5. Do some small code optimization.

I really liked that short explanation. He replaced "While A: if B: ... else break" by "While (A and not B) ...". That was quite natural, and his last few words indicated that it was a general pattern. I had never thought it through quite so explicitly, so I was happy to learn that.

No video about runtime, but maybe that'll come some day.

My main reservation was that he taught one particular algorithm, but did not take that opportunity to teach how to design algorithms. One could present insertion sort as an example of problem-solving by reducing to an easier subproblem (namely, inserting a single element in an already sorted list). Making that explicit introduces the idea of reductions.

Overall, if it is a way to teach insertion sort for the sake of teaching insertion sort, it is great. If it is a way to introduce students to algorithmic design through the example of insertion sort as a stepping stone, it is less impressive. Obviously, he is targeting a lower level than my students, but I would still have liked him to embed some deeper level of understanding in his presentation (even if it's done in an implicit manner), like sowing seeds of knowledge, just to prepare students, so that, when they meet more advanced material, that material will seem natural to them. They would be ready without even knowing that they have been prepared for it!

In short: very pedagogical, very engaging, superbly clear, but there is a little bit of a lack of vision.

Wednesday, November 23, 2011

Which textbook to use when teaching Algorithms?

Which textbook should one use when teaching Algorithms?

Let me start with the winner. For the past couple of years I have been using the textbook written by Dasgupta, Papadimitriou and Vazirani. Here is what I think of it.

-Its first quality is that it is softcover and therefore relatively inexpensive. Some preliminary version is available for free on the authors' web pages.
-Its second quality is that it is relatively small and therefore light to carry around.
-Its third quality is that it is written in good English. The style is crisp, and the authors occasionally inject emotions in their descriptions, giving more texture to the book. "Now the time has come to meet the quest’s most embarrassing and persistent failures. "
-Its fourth quality is that for each problem, the textbook goes straight to the heart of the difficulty. It does not waste space on secondary notes, avoids redundancy, and gives the gist of an argument in just a few lines. The proofs are often beautiful because they are direct and minimal, with no unnecessary detours. They are a pleasure to read.
-Its fifth quality is that it is short enough that a student could aim to read it in its entirety.

However, the book is not perfect.
-Its first fault is that it contains mistakes. The authors obviously did not implement their algorithms. Special cases may be overlooked in the problem specifications. Base cases may be done in a hurry, or barely mentioned when they contain nothing of interest. Calculations can be slightly off where the constants are concerned. The authors are keen on communicating the central ideas, but there is a certain carelessness about details. In that sense, the presentation is not up to the standards that we expect from our own students.
-Its second fault is a lack of examples. For me, designing algorithms is first done by working through examples, and a student who wishes to study the course material has to supplement the book with more examples. In that case, the tradeoff between size of book and content comes out in favor of examples, in my opinion.
-Its third fault is the choice of topics with which to start the book: the first chapter talks about arithmetic operations. That's natural because students learned algorithms for those at a young age, but that immediately raises problems that should be swept under the carpet until much later: when we talk about an input of size n, what is n? Starting by numbers creates problems that spoil the beginning of the semester: when we sort by comparisons, why do we assume that comparing two numbers can be done in constant time? What if the numbers are really large? Those concerns are valid, but they should come up at the end of the semester, when the student is comfortable with runtime analysis and ready to revisit his assumptions. This textbook's approach naturally leads students to raise those questions early on, and at that stage they only create confusion.
-Its fourth fault is a lack of exercises. There are not enough exercises for students to practice what they are learning.
-Its fifth fault is the choice of topics to be covered, that does not correspond one hundred per cent to my own taste; it is more of a reflection of the authors' tastes; however that is natural for any book.

Overall, I like this book very much. It is the one that comes closest to my taste. A cleaned up and slightly expanded version of that book would be ideal for me.

Tuesday, November 22, 2011

Workers' rights, students' training

Thanksgiving is the most respected holiday in the US. It is the one day on which every non-vital service is closed in the afternoon. It is the main family holiday in this country. For many people it is part of a 4-day weekend from Thursday to Sunday. The next day is traditionally devoted to shopping at heavily discounted prices. Because of the crowds in the stores, it is called Black Friday.

Some retail store employees have complained that for Black Friday (the day of frenetic shopping that follows Thanksgiving Thursday), they are required to start a full day's work beginning at 11pm on Thursday evening. Indeed, stores open as early as 1am on Friday morning.

I have been shocked to see the public reaction to employees' complaints. A typical reaction is: "If they don't like it, they can quit, and there will be plenty of people ready to take their job!". In other words, the market economy rules. It dictates what's right. At a time of high unemployment, workers have no rights. This is one of the situations when, in spite of having lived here for many years, I still feel that there is something alien about this country.

Sometimes I wonder if the students' training is a little bit similar. They cram a perhaps excessive workload, then they become highly marketable and get good jobs: not just because they know a lot and are well trained, but also because they have demonstrated their compliance with the demands made of them, even if those demands are unreasonable. They'll be good software engineers, always willing to put in long hours without counting, and the occasional all-nighter when a deadline is coming up. They are being trained for a way of life in which, in exchange for a good salary, they will basically belong to their employer.

Monday, November 21, 2011

How to make students fail

Here is a simple recipe to make students fail: create assignments densely packed throughout the quarter, and where each assignment relies on the previous one completely, so that it requires prior completion of the previous assignments before it can be started.

Then, consider the case of a student who has a bit of trouble with the course and who can only manage to do 90% of the work assignment in a given week.
On the first week, he will turn in 90% of the work.
On the second week, he will first need to complete the remaining 10% of the first assignment (for no credit), so he will only be able to turn in 80% of the work.
On the third week, he will first need to complete the remaining 20% of the second assignment (for no credit), so he will only be able to turn in 70% of the work.
and so on until the 10th week, when he will first need to complete the remaining 90% of the previous assignment (for no credit) and will then have no time left to work on the 10th assignment.
On average, for a 10-week quarter, his grade will be 50%, or a bit less if end-of-quarter assignments are weighed more heavily; that, in spite of having done 90% of the work overall.
Note that giving the option of turning in assignments a couple of days late does not help. The student is doomed.

Now, consider a student who only just manages to do the entire assignment in the time allocated, and imagine that after three or four weeks, there is one week when he is sick, or tired, or something, and only does 50% of the work.
Then, from that point on, each week he'll spend half the time catching up on the previous assignment and half the time on the current assignment, so all of his grades will be 50% from then on, and at the end of the semester his average grade will be 60% or so.

Saturday, November 19, 2011

Two goals of teaching

There are two goals accomplished by teachings university level students.

One is to educate the people who will, in a few years, be professors in academia, or entrepreneurs in innovative businesses, or CEOs of large companies whose decisions have significant impact on society. The idea of shaping the knowledge of tomorrow's leaders was very present when I taught at Ecole Polytechnique in France.

The other one is to educate people in general, forming the minds of our the new adult citizens who will be voting and holding jobs everywhere in society. That idea was very present when I taught at Universite Paris-Sud in France.

For the first goal, the focus of attention are the best students in the class. The instructor tries to constantly challenge them, stretching their mental agility and pushing them to learn as much, as deeply, and as fast as possible. The students who are in difficulty are not on the radar. For the second goal, the focus of attention is the majority. The instructor tries to reach as many students as possible and is focused on the fringe students who are struggling to learn the course material. The students who are effortlessly cruising through the course are mostly ignored and are sometimes even considered to have an unfair advantage. So, to some extent the two goals are in tension.

It's one of the difficulties of teaching at a large public university. For example, if you teach a class of 100 undergraduates at UC Berkeley: are you going to spend effort on the two or three students who are shining in class and who might, with encouragement, continue on to a PhD, or on the thirty students who seem to have overreached slightly by taking the course?

At a selective institution such as Ecole Polytechnique or Stanford, the problem is largely solved by the filtering that happens beforehand.

Teaching with both goals in mind is taken to its limit this semester Stanford, with an online course being taught on introduction to AI. The course material is taught to the Stanford students, a selective group if there ever was one, but also, in an online manner (including automatic online grading of homeworks and exams), to the entire world, with no filtering whatsoever. How can that be?

There must some self-selection, so that the unknown crowd of students taking the course online are each, individually, a student who is highly motivated, smart, hard-working, and who, in different circumstances, might have ended up in Stanford anyway. It's an idea very much aligned with the American Dream: offering an opportunity for all to better their education, regardless of social class or circumstances of birth. That makes the project an idealistic and, if even half-way successful, exciting endeavor.