Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!utgpu!water!watmath!clyde!rutgers!husc6!cmcl2!phri!roy From: roy@phri.UUCP Newsgroups: sci.math,news.software.b Subject: Re: Ethics in Mathematics (and summary of responses to my vote query) Message-ID: <2732@phri.UUCP> Date: Fri, 29-May-87 12:39:38 EDT Article-I.D.: phri.2732 Posted: Fri May 29 12:39:38 1987 Date-Received: Sat, 30-May-87 11:11:31 EDT References: <1211@cullvax.UUCP> <1324@mmm.UUCP> Reply-To: roy@phri.UUCP (Roy Smith) Organization: Public Health Research Inst. (NY, NY) Lines: 83 Xref: utgpu sci.math:1151 news.software.b:606 [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 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 10016