roy@phri.UUCP (05/29/87)
[See end of article if you're wondering why this in news.software.b; if you
followup on the math issue, do it only to sci.math; if you followup on the
inews issue, do it only to news.software.b, and change the title, please.]
In article <1324@mmm.UUCP> cipher@mmm.UUCP (Andre Guirard) writes:
(regarding my vote-counting question)
-> Why is it that everyone is answering this person's question and not
-> commenting, hey, you probably don't want to do this because it'll
-> destroy the democratic process at your co-op.
I would guess they are answering the question because I asked it
and they knew the answer. That's the way it's supposed to work. I can
deal with my own ethics, thank you. Just to salve your conscience, however,
let me point out that the election in question was 6 months ago and far
past the point when any protest would have mattered; this was based on
real-life, but was mostly an academic exercise. Our most recent election
(last week) was uncontested.
Now, let me take this opportunity to explain why I think I should
be elected to the office of ... (oops, wrong speech) ... uh, to thank all
the people who wrote with suggestions and answers to my question. A number
of people posted answers, you all know who they are. In addition,
William C. Bauldry <cmcl2!seismo!mcnc.org!ecsvax!wmcb>
allegra!alice!amo (Andrew Odlyzko)
allegra!uiucdcs!b.cs.uiuc.edu!robison (Arch Robison)
wrote directly to me with suggestions. Numerous people pointed out that
what I described is the knapsack problem which is NP-complete and directed
me to texts on public key cryptology. Arch Robinson, however, gets the
prize for the best, clearest, and most helpful answer. First he sent me a
letter explaining a straight-forward way to enumerate the solution set
without running into the combinatoric problems I feared. To wit:
-> Your problem seems rather straightforward to do by brute-force enumeration.
-> The computationaly complexity would be O(M) space and O(NM) time,
-> where N is the number of apartments and M is the maximum possible V.
->
-> Let S be the set of possible V's. Start out with S = {0}. Now consider
-> each Vi in turn. For each v in S, include v+Vi in S. After considering
-> all Vi's, S will contain all possible sums. In pseudo-Pascal, the
-> algorithm would be:
->
-> var S: array [0..M] of boolean; (* representation of set S *)
-> V[1..N] : integer; (* the Vi's *)
->
-> begin
-> S[0] = 1; (* Let S = {0} *)
-> for k=1 to M do S[k] = 0;
->
-> for i=1 to N do (* consider each Vi *)
-> for k=1 to M do (* Look at each element in S *)
-> if S[k] then
-> S[k+V[i]] := true; (* If v in S, include v+Vi in S *)
-> end
->
-> Even a naive implementation like this is probably sufficient for your
-> problem. (Efficient bit-twiddling can probably speed it up by an order
-> of magnitude.) Its probably not too hard to extend this algorithm to
-> figure out what combinations of Vi produced a given sum.
As if that wasn't enough, he sent me a second letter:
-> Your voter problem was sufficiently interesting for me to code my solution
-> to question (1). For 54 random numbers between 300-700, it takes about
-> a second of CPU time on my PC/RT to run. I doubt that you will be able
-> to prove much, however, unless some of the vote totals were rather low
-> or the shares are not distributed randomly. For my random data, all sums
-> above ~920 were possible, and I suspect this is typical.
->
-> You can have the C-source to the program if you want it.
As I side note, I'm a bit peeved that I had to change all my "> "s
to "-> "s to make inews happy. I really think this was a mis-feature. It
doesn't help in the long run (people just learn to 1,$s/^>/->/) and it
seems to have generated a cult practice of "line-counter pacifier lines",
not unlike those dumb line-eater lines. A worthwhile experiment, but, in
my opinion, an experiment that failed.
--
Roy Smith, {allegra,cmcl2,philabs}!phri!roy
System Administrator, Public Health Research Institute
455 First Avenue, New York, NY 10016woods@hao.UUCP (05/30/87)
In article <2732@phri.UUCP> roy@phri.UUCP (Roy Smith) writes: > As I side note, I'm a bit peeved that I had to change all my "> "s >to "-> "s to make inews happy. I really think this was a mis-feature. And I'm peeved that you made OUR SITE pay to RE-transmit an article that all the math people have ALREADY READ. Do you think they are stupid? Is it *really* necessary to quote 20 lines of old article to make a two-line comment on it? I do not. You may be right in saying that having inews enforce a old/new text ratio is the wrong way to go about it, but we have to do SOMETHING to stop the excessive quoting of old articles. As always, the news software writers (read: Rick Adams) are always open to suggestions on how to do it better; without these, complaints are nothing more than yet more useless flames. --Greg -- UUCP: {hplabs, seismo, nbires, noao}!hao!woods CSNET: woods@ncar.csnet ARPA: woods%ncar@CSNET-RELAY.ARPA INTERNET: woods@hao.ucar.edu
roy@phri.UUCP (06/02/87)
In article <706@hao.UCAR.EDU> woods@hao.UUCP (Greg Woods) writes: > And I'm peeved that you made OUR SITE pay to RE-transmit an article that > all the math people have ALREADY READ. Do you think they are stupid? and I have had a similar opinion expressed in a private letter (from somebody else) to me. Oh come on Greg, you do your good reputation a disservice with talk like that. No, I don't think sci.math readers are stupid. I also don't think you read my article. The 2 long quotes were not from a previous *article*, they were from 2 *letters* somebody sent me. The other people on sci.math had *not* already seen it, which is why I brought it to their attention. I didn't stress that point in my final paragraph (where I semi-flamed inews), but I didn't think I had to because it would have been clear to anybody who read the whole thing. *That's* what I was peeved about in the first place; that inews chided me for over-quoting an article when that's not what I was doing at all. I think everybody agrees that we need to cut down (a lot) on followup quotes. I certainly have no problem with that. A year or so ago (before the Renaming) there was a lot of discussion about new/old line counting. Based on that discussion, I got the impression that most people thought it was a bad idea, for exactly the reasons that seem to have happened; it's too easy to get around when you want to, and it's too easy for it to get fooled when it's not supposed to (as happened to me). I don't think anybody at the time anticipated the rash of .. .. .. this text is to make inews happy .. .. .. stuff I've seen cropping up. This latter plague is the most perverse, and simply demonstrates that you can lower a ratio by decreasing the numerator *or* increasing the denominator. We wanted people to do the former but they surprised us by doing the latter. I was a little surprised after that discussion to see the line counting in the 2.11 release. I'm not upset that it was included; being a scientist I understand the value of running experiments, even if you suspect they won't work out the way you hoped. Sorry, Greg, but I don't know how to solve the volume problem. I have a few suggestions, but most of them have been aired out pretty well already and don't seem to work. User education, in the form of news.announce.newusers postings and etiquette documents handed out by SA's when people get accounts sounds like a fine idea, but doesn't seem to work. Restricting access to the net would certainly cut down on volume but sort of goes contrary to the usenet spirit. Moderation is my favorite, but has met strong opposition from the masses everytime it's brought up. The delay introduced by moderation is certainly a strike against it (witness the sun-spots list, and its irregularly published massive digests). Digests, of course, bring up a whole other can of worms, with religeous zealots on both sides. I happen to dislike digests in general, but there are exceptions (RISKS, I think, works well as a digest, but that's due to the huge amount of effort put in by the moderator). If you want off-the-wall new ideas, try this one. Instead of just doing a count of lines that start with "> ", do a full-fledged diff on the posted and followed-up-to articles, using tail-anchored searches to do line matching (i.e. have a special version of diff that matches lines no matter what initial quoting string you use). That will solve two problems. First, it will stop people who get around the restriction simply by using a "-F->" argument to rn. Second, it will avoid kicking out things that look like quoted articles but aren't really (like my letter quotes). Problems? A few. It eats more CPU cycles than simply doing a count of ">" lines. Inews currently counts the ">" lines on-the-fly; my scheme would (I think) involve a second pass throught the text, possibly even forking a modified diff to do the work. Compared to how much work inews has to do anyway, I don't think it would be significant. Also, it only has to get done once, at the originating site, so it's bearable. Actually, my followups would probably serve as a good argument against my plan. I tend to reformat included text to make it look nicer (trivial in emacs with M-Q and the right Fill Prefix). Even if I don't delete anything, just the refilling would be enough to make the text look different. Another problem is that to do a diff, you need to have the text of the original article handy. You can always grab the Message-Id off the References: line, but you have to trust that it's correct; the user is free to edit the References: line any way he wants, and may have deleted or munged it by accident (or on purpose to defeat inews). On top off all the technical problems, I am basicly distrustful of any AI kind of approach to determining if a person has acted properly or not. That's what (human) moderators are for. -- Roy Smith, {allegra,cmcl2,philabs}!phri!roy System Administrator, Public Health Research Institute 455 First Avenue, New York, NY 10016