HDTenEightyP/NetNews huggingface dataset:
From: thompson@atlas.socsci.umn.edu (T. Scott Thompson)
Subject: Re: How to find vectors with minimum Hamming-distance?
Reply-To: thompson@atlas.socsci.umn.edu
Organization: Economics Department, University of Minnesota
Date: Thu, 3 Sep 1992 16:29:12 GMT

rainer@ruble.fml.tuwien.ac.at (Rainer Staringer) writes:

>I stumbled over the following problem recently, and I wonder if there
>is a clever algorithm for it: I have a set of n m-dimensional vectors
>(vector elements are from a finite set, but not necessarily binary),
>and I want to find the 2 vectors with the minimum Hamming-distance
>(i.e. those which have the most elements in common). Is there any
>way you can find them using less than O(n^2) vector comparisons?
>I know there is a clever algorithm for the equivalent problem with
>Euclidean metric, but I could not find any for the Hamming-metric
>variant.

How about this (off the top of my head): If the vectors are drawn from
a finite set then the problem can be transformed into a finite
collection of sorting problems, each of which can be solved faster
than O(n^2).  Here is what I have in mind.

min-dist := m+1;
<initialize vector-array>;
for <every permutation of the coordinate system> do
   begin
   <sort vector-array according to the lexicographic ordering induced by the
    current labelling of the coordinates>
   min-this-time := m+1
   for i := 1 to n-1 do
      begin
      current-dist := m - #zeros( vector-array(i) - vector-array(i+1) );
      if current-dist < min-this-time then
         begin
         v1 := vector-list(i);
         v2 := vector-list(i+1);
         min-this-time := current-dist;
         end;
      end;
   if min-this-time < min-dist then
      begin
      p1 := <inverse-of-current-permutation>(v1);
      p2 := <inverse-of-current-permutation>(v2);
      min-dist := min-this-time;
      end;
   end;

At the end the vectors p1 and p2 will hold two points achieving the
minimum distance.  The distance itself is in min-dist.

The time, considered as a function of n, will be dominated by the
"sort" statment, which can be done faster than O(n^2) if you do it
right.  The main drawback is that the outer loop must be executed
O(m!) times.  Some improvement on this is clearly possible (e.g. never
check both a given permutation and its reverse-ordering), but I
wouldn't use this for m! big relative to n.  How big is m in your
application?
--
T. Scott Thompson              email:  thompson@atlas.socsci.umn.edu
Department of Economics        phone:  (612) 625-0119
University of Minnesota        fax:    (612) 624-0209
From: ardtlong@adam.adelaide.edu.au (Dale T. Long)
Newsgroups: comp.programming
Subject: Help needed with Qbasic
Date: 31 Aug 92 05:07:22 GMT


        I am using Qbasic, the one that comes with Microsoft DOS 5.00 for the
IBM PC. I have a problem in that the space allocated for strings is only
8000 bytes. In the old GWbasic I would have done a CLEAR xxx to free up xxx
amount of bytes. However Qbasic only has the ability to clear the stack using
CLEAR ,,xxx . Paramaters before the first two commas don't do a thing. Is there
a way to allocate more string space? I am using a two dimensional dynamic
string array. Help indicates that individual strings can be up to 32767 bytes
long but I can't even have a single string longer than the 8000 byte limit.
Help also says that a string array can be up to 64K in size. Is there any way
to over come this problem? Is the Qbasic (interpreter) just a sales pitch
that makes people need to buy the full Quick Basic (compiler) out of neccesity?
Has anyone else had this problem? How do I increase the amount of string space
from 8000 bytes?

Dale Long.
ardtlong@adam.adelaide.edu.au
Newsgroups: comp.programming
From: geert@cs.ruu.nl (Geert-Jan Giezeman)
Subject: Re: Why Are Red-Black Trees Obscure?
Date: Thu, 27 Aug 1992 11:14:22 GMT
Organization: Utrecht University, Dept. of Computer Science

In <1992Aug26.183817.7371@reed.edu> orpheus@reed.edu (P. Hawthorne) writes:

>Sedgewick, for the chapter on balanced trees in his book "Algorithms," uses
>the red-black tree. As a data structure, the red-black tree seems simple
>and well balanced. He convincingly suggests that they are better than AVL
>trees and yet, I've never seen them mentioned by anyone else. Why not?
>

Perhaps obscure, but not unused. For example the public domain library LEDA
uses red-black trees for the implementation of dictionaries.
From: jtien@venice.eng.uci.edu (Joe Tien)
Newsgroups: comp.programming
Subject: Re: How to decide if a point is inside a polygon?
Date: 26 Aug 92 23:44:42 GMT
Reply-To: jtien@venice.eng.uci.edu (Joe Tien)
Organization: University of California, Irvine

In article <7121@bigbird.hri.com.hri.com>, mps@sparc68.hri.com (Mark Stockley) writes:
|> I am in need of an algorithm to compute whether or not a given
|> point exists within or without a polygon. Any help or pointers to
|> where to look would be much appreciated.
|> 
|> ------------------------------------------------------------------------------
|> Mark P. Stockley    |   INET: mps@hri.com    | But I don't like Spam!!!
|> Horizon Research    |  Voice: (617) 466-8300 | 
|> 1432 Main St.,      |   		     | Is the alphabet in that order
|> Waltham MA 02154    |    FAX: (617) 466-8323 | or is it because of that song?
|> ------------------------------------------------------------------------------
|> 

Look at the book "Algorithms in C" by Sedgewick. I don't have the book with me
but I'm pretty sure it's in there.

Joe Tien
From: Marc.Ringuette@daisy.learning.cs.cmu.edu
Newsgroups: comp.programming
Subject: Re: How to find vectors with minimum Hamming-distance?
Date: 4 Sep 92 20:56:00 GMT
Article-I.D.: news.9209042121.AA00144
Organization: The Ohio State University Department of Computer and Information Science

rainer@ruble.fml.tuwien.ac.at (Rainer Staringer) writes,
> I stumbled over the following problem recently, and I wonder if there
> is a clever algorithm for it: I have a set of n m-dimensional vectors
> (vector elements are from a finite set, but not necessarily binary),
> and I want to find the 2 vectors with the minimum Hamming-distance
> (i.e. those which have the most elements in common). Is there any
> way you can find them using less than O(n^2) vector comparisons?
> I know there is a clever algorithm for the equivalent problem with
> Euclidean metric, but I could not find any for the Hamming-metric
> variant.

Good problem!  Some friends and I tried to come up with something
better, but couldn't.  We were thinking along the lines of geometric
algorithms (but couldn't manage to extend a 2-d closest-pair-of-points
algorithm) or something based on sorting or divide-and-conquer.  I like
the other poster's n*log(n)*m! answer -- deliciously crazy and good for
minuscule m.

----

If you expect the distribution to be skewed, with a small number of
very well matched pairs of vectors, then you might adopt a method with
better average-case behavior at the expense of worst-case running time.

You could use a hashing technique to see if you might luck out and find
two duplicate vectors.

With an extra log n factor, you can compare the n^2 candidate
vector-pairs in a best-first fashion, comparing elements in each pair
only until you have seen more mismatches than the best so far.  This
means that if b is the number of total mismatches for the best pair,
p_ij is the number of elements in the largest prefix of vectors i and j
which has fewer than b mismatches, and P is the sum of all p_ij, then
the algorithm runs in time O(P log n), where n*b+m <= P <= n^2*m.

----

Other ideas, anyone?  If not, how about a lower bound on the worst case 
running time?


[ Marc Ringuette | Cranberry Melon University, Cucumber Science Department  ]
[ mnr@cs.cmu.edu | 412-268-3728 |      ".surivorter erutangis a ma I"       ]
Newsgroups: comp.programming
From: bdickens@el_padre.mitre.org (Brian Dickens)
Subject: Morphology and Convolution 
Keywords: morphology,convolution,aaaaargh
Organization: The MITRE Corporation, Bedford, MA 01730
Date: Tue, 25 Aug 1992 16:01:19 GMT

I am trying to perform convolution on a rectangular matrix of numbers.  I have a program
which does basically what I want to do, but it does it 20 times faster than my program.  There
is a rather straightforward brute force algorithm to do it, which I'm using, but I think there
might be a better way.

I have two input matrices... one of bytes, and one of floating point numbers.  The floating
point numbers are used as a sliding window over the data, and for each square on the data,
the corresponding number on the floating point window is multiplied by the data value, and
the results of all these multiplications are summed up and stored in the output matrix.

The concept is much like local averaging, but more flexible, because the priorities of each
square can be adjusted.

Is there any way to perform the multiplication of a byte value (a la 15) by a floating point
value (a la 0.2112) in a fast manner?  i.e. conversion of the floating point number into a fraction,
and then merely perform integer multiplication and division?

-bdickens

Sorry if this doesn't make sense... but I've really hit a brick wall here.  The speed of the
existing code is far too superior to mine... it's frustrating.
From: amitp@rice.edu (Amit J. Patel)
Newsgroups: comp.programming
Subject: Re: Why Are Red-Black Trees Obscure?
Date: 2 Sep 1992 12:56:57 GMT
Reply-To: amitp@owlnet.rice.edu
Organization: Rice University
Originator: amitp@aten.cs.rice.edu


In article <BtnG7n.2o1@ais.org>, draper@ais.org (Patrick Draper) writes:
|> Dr. Dobbs had a good article on Red-Black Trees a couple months ago. I don't
|> know the exact issue, but it is between March and July of 1992.
|> 
|> It was perhaps the most interesting (to me) article in that magazine this
|> entire year.
|> 

But the picture they had of a tree colored red and black was wrong!  
(According to the coloring rules they gave)

	Amit
From: dave@cs.arizona.edu (Dave Schaumann)
Newsgroups: comp.programming
Subject: Re: Teaching the basics
Date: 26 Aug 92 17:28:30 GMT
Reply-To: dave@cs.arizona.edu (Dave Schaumann)
Organization: University of Arizona

In article <PSU.92Aug26091352@ptero.cs.duke.edu>, psu@cs (Peter Su) writes:
>In article <1992Aug26.111240.8239@ITcorp.com> geoff@ITcorp.com (Geoff Kuenning) writes:
>
>   >...
>   >    else if (Prev->Key < Key) Prev->Left = Cur; else Prev->Right = Cur;
>
>   I find it sourly this code was on a thread named "Teaching the
>   basics", since the author obviously hasn't even learned the basics of
>   readable code formatting.
>
>Learn to use indent, or Emacs C-mode.
>
>Code formatting is irrelevant

No it isn't.  Unlike computers, humans understand the code they look at
largely through visual cues offered by the layout of the code.  This is
no doubt why flame wars about indentation style can be so hot: reading
code in an unfamiliar style is more difficult because the visual cues
are different, and probably misleading (at least to the unfamiliar reader).

>because programs like indent let you format the code anyway you like.

But what about the author of the code?  Good writing has always been about
the clear presentation of ideas, and I submit that this is as true of code
as it is of human languages.  Moreover, the clear presentation of algorithms
in code is more than just choosing the right data structures and good
variable names.  It is also presenting the code so that it can be easily
understood.

If the author of a piece of code can't format the code clearly, one begins
to wonder what other skills s/he lacks.  Just like poor spelling in human
languages, nothing says `amateur' louder than poor code formatting in
programming languages.

>It's amazing to me that universities waste so much time and effort
>teaching people how to format code.

Maybe they know something you don't.

-- 
Dave Schaumann			dave@cs.arizona.edu
Newsgroups: comp.programming
From: schnitzi@cs.ucf.edu (Mark Schnitzius)
Subject: Re: Deciding point-in-polygon: A new idea
Organization: University of Central Florida
Date: Mon, 31 Aug 1992 16:52:50 GMT

hermann@uran.informatik.uni-bonn.de (Hermann Stamm) writes:
>| 
>| Compute the area of the polygon in question (this is a well
>| known and simple procedure).  Now consider the polygon formed
>| by adding the point in question as another vertice, anywhere
>| in the original list of vertices.  If the area of this new
>| polygon is greater than the original, the point is outside
>| the polygon.  If less, it is inside.
>| 
>| My question:  will it work?
>| 
>This will not work! The area can be smaller even if the added
>point lies outside the polygon, but there is a more simple 
>proof, that this can't be right:

>The area of Polygon (x1,y1),(x2,y2), ... , (xn,yn) is given by

>   A=x[n]*y[1]-y[n]*x[1];
>   for(i=1; i<n; i++)
>     A+=(x[i]*y[i+1]-y[i]*x[i+1]);
>   A/=2;

>If you are allowed to insert the new point (x,y) where you like, then
>insert (x,y) always between (x1,y1) and (x2,y2).

>The only change in the above sum will then depend only on 
>(x1,y1), (x2,y2) and (x,y), and thus will be computable in constant time,
>but you can't look at the whole input in constant time, and the rest of the
>lines can either force (x,y) to lie inside or not.       contradiction!

Confession:  I knew it wouldn't work when I posted it, but I wanted to
see if anyone could come up with a way to make it work.  Since then, I
came to the realization that this idea WILL work if you add the stipulation
that the point must be added in such a way that it will not make any new
line crossings, and I believe it is always possible to do so.  Like you
said, the only change in sum will depend on (x1,y1), (x2,y2), and (x,y),
so after you find the place to add the point (which is where the complex-
ity comes in), you only need to check to see if

  (x1*y2-x2*y1) > (x1*y-x*y1)+(x*y2-x2*y)

If this inequality is true, the point is inside the polygon.

Mark Schnitzius
schnitzi@eola.cs.ucf.edu
Univ. of Central Florida
From: desj@ccr-p.ida.org (David desJardins)
Newsgroups: comp.programming
Subject: Re: Detecting Integer Overflow/Underflow
Date: 23 Aug 92 18:30:13 GMT
Organization: IDA Center for Communications Research, Princeton

Steve Coile <scoile@gmuvax2.gmu.edu> writes:
>Could someone please, PLEASE explain what is going on with
>
>	((a ^ sum) & (a ^ b)) ^ b
>
>What is the justification for doing this (i.e. how in the WORLD would someone
>figure this out that THIS is the way to do it?????)

It's close to being trial and error.  You know what boolean function you
want, and you try different sequences of operations to find a minimal-
cost representation.  As I said, I think this is in general NP-hard, so
it's not going to be possible to state a simple algorithm.

It does help to use boolean logic; i.e.,

   F = (a & b) | ((a | b) & ~sum)
           ; Start with the "obvious" representation of the carry
           ; function in terms of {a, b, sum}.  Carry if a and b are
           ; both 1, or if at least one of them is 1 and the sum is 0.

     = (a & b) | ((a ^ b) & ~sum)
           ; We want to replace | operations by & and ^, which are the
           ; basic addition and multiplication of mod-2 arithmetic.
           ; This expression is equivalent to the first, because when a
           ; and b are both 1, (a & b) makes the whole expression 1, so
           ; it doesn't matter that we have changed the second term.

     = (a & b) ^ ((a ^ b) & ~sum)
           ; Continue replacing.  The two operands of | are never both
           ; 1, so we can replace | by ^.

     = (a & b) ^ ((a ^ b) & (one ^ sum))
           ; ~x is the same as (one ^ x), where one is a word of all 1s.

     = (a & b) ^ (a & one) ^ (b & one) ^ (a & sum) ^ (b & sum)
           ; Now we can use the ordinary distributive law to expand the
           ; product fully.

     = (a & b) ^ a ^ b ^ (a & sum) ^ (b & sum)
           ; (x & one) is the same as x.

     = a ^ (a & b) ^ (sum & a) ^ (sum & b) ^ b
           ; Write the terms in a different order.

     = (a ^ sum) & (a ^ b) ^ b
           ; Now recognize that the first four terms can be factored
           ; into a product. 

Then you look for a while for a representation with three terms and fail
to find one.  So you conclude that this is the best you can do.

                                        David desJardins
Newsgroups: comp.programming
From: berlin@is.morgan.com (Alexander Berlin)
Subject: Re: Deciding point-in-polygon: A new idea.
Organization: Morgan Stanley - IS
Distribution: comp
Date: Mon, 31 Aug 1992 13:22:05 GMT

In article <schnitzi.715219193@eola.cs.ucf.edu>, schnitzi@cs.ucf.edu (Mark Schnitzius) writes:
|> How about this:
|> 
|> Compute the area of the polygon in question (this is a well
|> known and simple procedure).  Now consider the polygon formed
|> by adding the point in question as another vertice, anywhere
|> in the original list of vertices.  If the area of this new
|> polygon is greater than the original, the point is outside
|> the polygon.  If less, it is inside.
|> 
|> My question:  will it work?
|> 

  No, it won't.

    A                  B
     +----------------+         See what happens when you go from ABCD to
     |                |         ABXCD. 
     |                |
  X  |                |
  .  |                |
     |                |
     |                |
     |                |
     |                |
     |                |
     +----------------+    
     D                C



|> 
|> Mark Schnitzius
|> schnitzi@eola.csu.ucf.edu
|> Univ. of Central Florida

---
Alex Berlin                     
berlin@is.morgan.com
Newsgroups: comp.programming
From: hns@ldv.e-technik.tu-muenchen.de (Hans Nikolaus Schaller)
Subject: Re: How to decide if a point is inside a polygon?
Organization: Leibniz-Rechenzentrum, Muenchen (Germany)
Distribution: all
Date: Thu, 27 Aug 1992 14:35:38 GMT

The following idea for an algorithm should work if the corners of 
your polygon are sorted clockwise (or counterclockwise) and the
polygon is convex:

    check if the point is on the "left" side of every line
    going through the vertices of your polygon.

To check, if a point (x,y) is on the "left" side of the oriented line 
from (xa,ya) to (xb,yb),

    calculate the angle between (x-xa,y-ya) and the left rotated 
    perpendicular vector to (xb-xa,yb-ya).

If the angle is between -90 and 90 degrees, x is on the left side.

To simplify the calculation: x is on the left side, if the cosine
of the angle is positive. The sign of the cosine can be calculated
by a scalar product. and the perpendicular vector to (x,y) is (-y,x).

To summarize (let's hope, there is no mistake...):

(x,y) is on the left side if

    (x-xa)*(ya-yb)+(y-ya)*(xb-xa) > 0.
    or
    (x-xa)*(ya-yb) > (y-ya)*(xa-xb)

If the first term vanishes, the point is on the line.

By the way, there are many good books about computer graphics that
describe this problem (and I think, I got the idea described above 
from one of them but don't remember which).

H. Nikolaus Schaller
Newsgroups: comp.programming
From: geoff@ITcorp.com (Geoff Kuenning)
Subject: Re: what skills does a programmer need
Organization: Interrupt Technology Corporation, Manhattan Beach, CA
Date: Wed, 26 Aug 92 10:56:22 GMT

In article <23312D@erik.naggum.no> enag@ifi.uio.no (Erik Naggum) writes:

> On a related note, is correct spelling and grammar in natural languages
> correlated with proficiency in the syntax of programming languages, or
> is the latter correlated to the ability to manipulate symbols, as in
> mathematics?  (My own experience suggests that it's both, and the best
> programmers are those whose good language skills are augmented by good
> mathematical skills, but I've heard otherwise.)

I've known lots of excellent programmers who couldn't spell worth a
damn.  Drives me nuts.  (I blame it on TV:  modern kids, even smart
ones, learn their language by hearing rather than reading, so they
have terrible trouble with homonyms.)  On the other hand, most really
good (native-English-speaking) programmers understand English grammar
very well once you've corrected their spelling.
-- 
	Geoff Kuenning   geoff@ITcorp.com   uunet!desint!geoff
Newsgroups: comp.programming
From: geoff@ITcorp.com (Geoff Kuenning)
Subject: Re: Teaching by Value (was Re: Teaching the Basics)
Organization: Interrupt Technology Corporation, Manhattan Beach, CA
Date: Wed, 26 Aug 92 10:52:22 GMT

In article <9208241338.AA01262@golf.visix.com> eric@golf (Eric
Wiseblatt) writes:

> I dont like the idea of a "Maintainability" grade.  Rather, I think
> the labs with the course should be planned to *excersize the need
> for* maintainability.  I think learning to write maintainable code
> comes more from hindsight experience with your own and other
> people's code than upfront with the original assignment.  Especially
> in a beginning type of course with simple assignments.

I agree most strongly.  A couple of years ago, I was the TA for a
software engineering course in which the prof assigned a group-written
project for which he deliberately changed the specs as the course went
along.  Being a fair sort of guy, he made a point of announcing up
front that he was going to do this.  Nevertheless, when evaluation
time came, a number of students complained about the capriciousness of
the spec changes.  Boy, are they going to be annoyed when they get a
job and find out what *real* customers are like!  (BTW, the most
talented students took the warning to heart and had little trouble
keeping up with things.)
-- 
	Geoff Kuenning   geoff@ITcorp.com   uunet!desint!geoff