Women in CS

By the definitions of many people I'm probably a very good example of racism and sexism. The thing is, for me most of this "political correctness" sounds like marketing bullshit. I don't see how avoiding certain words or not telling certain truths can make things better. My beliefs are not going to change just because I use a different vocabulary. Alas, it seems that many people are superficial enough to think that the two are the same. This is the only merit I see in political correctness.

Anyway, here's a story from ETAPS that I heard from a female researcher in compilers: "I was in charge with making sure that females are well-represented in our University. I distributed a questionnaire in which I asked (1) what is the percentage of female students? and (2) what can be done to improve the situation? The Physics Department replied to the second question by asking what do I mean by 'improve'. This is such a typical attitude, exactly what we need to change." I can't even discuss with such people. The Physics department was obviously right. If she would have said 'increase' then there is little room for interpretation. But it is not at all obvious that sex is not correlated with how much one enjoys different fields of activity. (I suspect the correlation is weaker than many think but I don't think it's zero as some people would like to force us believe without scientific evidence. Anyway, my point, as you will see later, is that this is irrelevant.)

My wife, Claudia Grigore, studied psychology. Every day when I go home, and every time we go to a walk in the park I tell her what I have been doing for work. I select only portions of what I do that she can understand. For other parts there just isn't time for me to present all the required background. It helps me a lot. First, it makes me aware what are the elementary parts and what are the parts that require a lot of background. Second, quite often it happens that I have an Aha! moment because explaining to someone else forces you to understand well what you are talking about. More importantly, I try to focus on the parts that transmit the excitement and joy of playing in computer science. (I usually say 'play' instead of 'work'.) The result? She liked so much my stories that she did an HDip in CS. (I must say I was a little worried when she said that she wants to do this: I was afraid I might have painted a too-rosy picture for her.) She finished with very good grades, she picked up a job as a research assistant doing things like this report, and now she started a PhD in CS. I am very proud of her; I wouldn't be able to switch now to a different field and do that well.

I'm quite happy how things turned out. So here is my advice: If you think a bigger percentage of women in CS is a good thing then you'd better act on it instead of criticizing what words others use. Go out and spread the excitement. Who knows, if you are a guy, that might even contribute to demolishing the myth that CS guys don't have girlfriends.

Garbage collection problem

Background: In separation logic we can make the assertion x → a, meaning “the variable x contains the address of a heap cell that contains the value a and that’s the only cell in the heap,” P ⋆ Q, meaning “we can partition the heap into a part where P holds and one where Q holds,” and emp, meaning “the heap is empty.” Just as we have rules that tell us how to manipulate formulas that contain ∧, ∨, and so on, we also have rules that tell us how to manipulate formulas that contain → and ⋆ without necessarily thinking about the meaning.

• x → _ ⋆ x → _ = ⊥, in other words x can’t point to two locations
• (P ∧ Q) ⋆ R = P ∧ (Q ⋆ R) if P is a pure assertion; an assertion is pure when it doesn’t say anything about the heap; that is, it does not contain ⋆, →, or emp.

We say that P is an intuitionistic assertion when P ⋆ ⊤ ⇒ P. In other words, if it is true for a heap, then it is also true for extended heaps. We say that P is a supported assertion when P ∧ (P ⋆ Q) ∧ (P ⋆ Q′) only if there exist R and R′ such that Q = P ⋆ R and Q′ = P ⋆ R′. In other words, if it holds in the current heap then there is a smallest subheap in which it holds. (A heap h is smaller than a heap h′ when h ⊆ h′.)

Conjecture [Matthew Parkinson, FIRST fall school on logics and semantics of state, 2008]: Show that if an assertion is intuitionistic and supported and holds in the current heap then it also holds in the garbage collected heap. (The garbage collected heap retains only the cells reachable from the stack.)

Problem: True or false?

Intuitionistic and supported properties P obey:

((P ∧ ¬(P ⋆ ¬emp)) ⋆ ⊤) ⇒ P

The lecture notes of Reynolds provide a more precise presentation of separation logic and many properties that may be useful in answering the problem.

Segments on a plane: solution

The problem was solved by: Cosmin Negruseri, Eugene Kenny, Filip Buruiana. Cosmin pointed out that this problem appears in CLRS where they give a O(n²lg n) algorithm for finding the segments. I got it from problem ANTS in NEERC 2007.

Solution 1:The dumbest possible thing I could think of is to try some random segments between white and black points and if two intersect then fix the problem by swapping their endpoints. (This could introduce other intersections, though.). So if it happens that you pick first AC and BD, you notice that they intersect, you swap them and you get AD and BC.

The problem is: If you keep doing this, are you guaranteed to terminate? Whenever you try to solve a termination problem the first thing that comes to mind is "Can I find a measure that changes monotonically and is bounded?" And, by starring at the figure you notice that the two new segments are shorter than the old ones: |AD|+|BC|<|AC|+|BD|. Is this always true? The triangle inequality in AED is |AE|+|ED|>|AD| and in BEC it is |BE|+|EC|>|BC|. If we add these two we get that indeed the new segments are always shorter. Since the sum of the lengths of all students is nonnegative the process described earlier must terminate. We are done.

What would be an algorithm to find these segments? See weighted bipartite matching. The Hungarian algorithm works in O(n³).

Solution 2: Eugene and CLRS give another solution. If you draw a few examples it becomes apparent that you can always find a segment which splits the problem in two smaller ones: on the left of it (viewed as a line) you have an equal number of whites and blacks and the same for the right, of course. Does this always happen? I'm going to give a very informal argument. Pick the left-most point and then sweep the other points with a line starting from this point. Is it possible that the first and the last points you sweep are of the same color and whenever you have an equal number of blacks and whites on the right you are sweeping thru a point of the same color? Not really. Keep track of the difference |whites on the left|-|blacks on the left|. This changes with +/-1 at each step. Suppose the first time it goes thru zero you are swapping a point of the same color. Draw this! Then you must have many points of the opposite color "to go" and therefore you'll pass again thru zero.

OK, this is not really a good explanation but I'm sick and tired (literally).

Anyway, this suggests an O(n²lg n) algorithm: Pick leftmost, sort the others by angle, sweep and keep track of the difference on the left, find a proper segment to split the problem in two. Repeat. In the worst case you do the main loop n times and the sorting takes O(n lg n). If you are lucky and you always split the problem in half then you have T(n)=2T(n/2)+O(n lg n) which, by the Master theorem, is O(n lg n) [edit, see below: actually, O(n lg²n)].

Segments on a plane: problem

There are n white points and n black points on a plane. All are distinct and no three are on the same line. You must draw n segments, each between points of different colors. Segments must not intersect. (This also means they can't have a common endpoint.) Show that it's always possible to complete the task.

Send solutions to radugrigore at gmail. I'll post the list of solvers and a solution in a week. Please use the comments only to ask for clarifications, not to give the solution.