HDTenEightyP/NetNews huggingface dataset:
From: rainer@ruble.fml.tuwien.ac.at (Rainer Staringer)
Subject: How to find vectors with minimum Hamming-distance?
Reply-To: rainer@eimoni.tuwien.ac.at
Organization: Technical University of Vienna
Date: Thu, 3 Sep 1992 13:29:31 GMT

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.

Thanks for any ideas, references, etc.

	Rainer
--
Rainer Staringer                   | rainer@fml.tuwien.ac.at
Financial Markets Lab, TU Vienna   | +43 (1) 58801/8138
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.programming
Subject: Re: Teaching the basics
Date: 26 Aug 92 11:02:17 GMT
Organization: Comp Sci, RMIT, Melbourne, Australia

In article <1992Aug25.174243.10436@uwm.edu>, markh@csd4.csd.uwm.edu (Mark) writes:
> In article <7116@charon.cwi.nl> tromp@cwi.nl (John Tromp) writes:
> >One of the prime applications of recursion, IMHO,
> >and where you cannot hope to replace it by anything else,
> >is in a tree search algorithm like alpha beta or plain old minimax.

> Wrong.  In fact, the non-recursive version (tree search) is far smaller and
> simpler.  No stacks either.

The trouble is that (Mark) gives code for a BINARY SEARCH TREE (like
UNIX "tsearch()), which doesn't even faintly resemble the problems that
(John Tromp) explicitly named, which are ALPHA-BETA SEARCH and MINIMAX.
Not the least of the difference is that alpha-beta and minimax are
algorithms for searching a _game_ tree which is in practice either infinite
in size or so very much larger than even virtual memory that one just does
_not_ have (Mark)'s kind of tree stored in memory to walk around.

-- 
You can lie with statistics ... but not to a statistician.
Newsgroups: comp.programming
From: crawford@church.mitre.org (Randy Crawford)
Subject: Re: Teaching the basics
Organization: The MITRE Corporation, McLean, VA
Date: Thu, 27 Aug 1992 17:42:56 GMT

In article <PSU.92Aug26091352@ptero.cs.duke.edu>, psu@cs.duke.edu (Peter Su) writes:
> In article <1992Aug26.111240.8239@ITcorp.com> geoff@ITcorp.com (Geoff Kuenning) writes:
> 
> Learn to use indent, or Emacs C-mode.
> 
> Code formatting is irrelevant, because programs like indent let you
> format the code anyway you like.
> 
> It's amazing to me that universities waste so much time and effort
> teaching people how to format code.

Either you don't comment your code, or you don't use indent.  Indent
plays havoc with comments.  For that very reason, no one I know uses 
indent. 
-- 

| Randy Crawford        crawford@mitre.org        The MITRE Corporation
|                                                 7525 Colshire Dr., MS Z421
| N=1 -> P=NP           703 883-7940              McLean, VA  22102
Newsgroups: comp.programming
From: tpradeep@cs.tamu.edu (Pradeep K Tapadiya)
Subject: Help - Contour drawing algorithm needed
Organization: Computer Science Department, Texas A&M University
Date: Tue, 25 Aug 1992 16:53:07 GMT


Howdy netters,

Given a set of (x,y,t) points where (x,y) represent the cooridinate and
(t) represents the associated temperature, I need to draw temperature
contours over a specified region. Can someone suggest me an algorithm
to do this, or refer me to the right book(s).

Thank you for your help.

Pradeep
tpradeep@cs.tamu.edu
Newsgroups: comp.programming
From: markh@csd4.csd.uwm.edu (Mark)
Subject: Re: Teaching the basics
Organization: Computing Services Division, University of Wisconsin - Milwaukee
Date: Wed, 26 Aug 1992 17:52:53 GMT

In article <14194@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:
>Please get your attribution straight.  That _wasn't_ me.  I'm the one who
>said that if you don't understand recursion, you don't understand programming.
>
>>  void hanoi(n)
>> {
>>   for (x = 1; x < (1<<n); x++)
>>     printf("move a disc from %d to %d\n", (x&x-1)%3, ((x|x-1)+1)%3);
>> }
>> 
>Besides, the simple recursive version is not as limited by the size of
>integers.  The machine I'm using as a _terminal_emulator_ can go through
>hanoi(32) in under an hour, so don't think that 32-bit integers are enough...

It's easy enough to extend it to arbitrary precision integers since the
operations involved (decrement, logical shifts, logical or) are easily
extended, especially if you're doing it in assembly.

You could even bring these operations out to the source level in a language
like C++, using the same operator symbols (+, <<, >>, etc).

Generally a recursion with N essential entry points has its entry-point stack
coded as follows:

long_word X;
CLEAR()     { X = 0; }
PUSH(int N) { X = N*X + 1; }
EMPTY()     { return X == 0; }
POP()       { int Top; X--, Top = X%N, X /= N; return Top; }

A recursion with a single entry point therefore uses a counter.
From: mps@sparc68.hri.com (Mark Stockley)
Newsgroups: comp.programming
Subject: How to decide if a point is inside a polygon?
Date: 26 Aug 92 18:11:25 GMT
Reply-To: mps@hri.com
Organization: Horizon Research, Inc.

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?
------------------------------------------------------------------------------
From: ppc1@cec1.wustl.edu (Peter Pui Tak Chiu)
Subject: miranda
Organization: Washington University, St. Louis MO
Date: Fri, 4 Sep 1992 02:00:22 GMT

hi,

can anyone tell me where i can get miranda (a functional programming language)
through anonymous ftp?

thanks
Newsgroups: comp.programming
Subject: Re: Deciding point-in-polygon: A new idea.
From: dave@cs.arizona.edu (Dave Schaumann)
Date: 31 Aug 92 05:01:18 GMT
Reply-To: dave@cs.arizona.edu (Dave Schaumann)
Distribution: comp
Organization: University of Arizona

In article <schnitzi.715219193@eola.cs.ucf.edu>, schnitzi@cs (Mark Schnitzius) writes:
>Compute the area of the polygon in question (this is a well
>known and simple procedure).

Well, so is an easy algorithm for finding out if a point is inside
a polygon, but never mind...

>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.  Here's an example where you will get the wrong answer:

                       A (placed just outside the B-C line)
                       .
            B.---------------------.C
             |                     |
             |                     |
             |                     |
             |                     |
            D.---------------------.E

Since I can choose which vertices to insert A between, I choose D and E.
Although the object is no longer a simple polygon, it clearly encloses
less area than the original, and thus your algorithm would say that A
is inside, even though it is not.

To fix this, you need to add A between the vertices whose edge it is
nearest to.  I haven't checked it, but I wouldn't be surprised to find
that you're now doing as much (if not more) work as the traditional
"shoot a ray and count the intersections" method.

-- 
Dave Schaumann			dave@cs.arizona.edu
From: gcr8829@aw2.fsl.ca.boeing.com (Gustav C. Rettke)
Newsgroups: comp.programming
Subject: Re: Help - Contour drawing algorithm needed
Date: 27 Aug 92 21:03:08 GMT
Organization: fsl

From article <1992Aug25.165307.21995@tamsun.tamu.edu>, by tpradeep@cs.tamu.edu (Pradeep K Tapadiya):
> 
> Howdy netters,
> 
> Given a set of (x,y,t) points where (x,y) represent the cooridinate and
> (t) represents the associated temperature, I need to draw temperature
> contours over a specified region. Can someone suggest me an algorithm
> to do this, or refer me to the right book(s).
> 
> Thank you for your help.
> 
> Pradeep
> tpradeep@cs.tamu.edu

Here's a simple alogrithm:

	For y = y1 to y2

	  For x = x1 to x2

	    Calculate t

	    Set xplot = x

	    Set yplot = t + k * y

	    Plot xplot, yplot

          Next x

        Next y

Where k is an obliqueness factor.

This will produce a view as if you were standing above the x,y-plane.  The
factor k affects the degree of above (or below) the plane.  Play with k to get
a good perspective.

Another enhancement might be to connect line segments to produce 'lines of
constant x'.  Here's the algorithm with the slight modifications.

	For y = y1 to y2

	  For x = x1 to x2-1

	    Calculate t1 @ x

            Calculate t2 @ x+1

	    Set xp1 = x

	    Set xp2 = x+1

	    Set yp1 = t1 + k * y

            Set yp2 = t2 + k * y

	    Line   xp1, yp1   to   xp2, yp2

          Next x

        Next y

Of course you will have to massage the scaling and resolution.

Hope this helps.


G Rettke
From: orpheus@reed.edu (P. Hawthorne)
Newsgroups: comp.programming
Subject: Why Are Red-Black Trees Obscure?
Date: 26 Aug 92 18:38:17 GMT
Article-I.D.: reed.1992Aug26.183817.7371
Organization: Reed College, Portland OR

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?

Theus (orpheus@reed.edu)
From: dave@cs.arizona.edu (Dave Schaumann)
Newsgroups: comp.programming
Subject: Re: Balanced Trees (Re: Why Are Red-Black Trees Obscure?)
Date: 28 Aug 92 18:08:54 GMT
Reply-To: dave@cs.arizona.edu (Dave Schaumann)
Organization: University of Arizona

In article <neuhaus.715007061@vier>, neuhaus@vier (Stephan Neuhaus (HiWi Mattern)) writes:
>orpheus@reed.edu (P. Hawthorne) writes:
>
>>  Has anyone used frequency of node access data to bias the tree balancing
>>rotation operations toward shorter paths?
>
>Not quite, but I have used self-organizing linear lists in a program
>that spent almost 90% of its time doing lookups, with startling
>results.
>
[...]
>1.  When an element is successfully found in the list, move it to the
>front of the list so that it may be found faster in subsequent
>searches.
>
>2.  When an element is successfully found in the list, exchange it
>with its predecessor.

>[...]I managed to get a speedup by a factor of 15 (roughly) for shallow
>tries. [keys access probability had exponential distribution]

It seems reasonable that this would also work well for equal probability
of key access if you have a situation where the access of a key means it
will likely be accessed again soon.  (for example, variables in programs
generally have this property: you have an access in the declaration, then
several more accesses following as the variable is used.)

-- 
What signature?
From: orpheus@reed.edu (P. Hawthorne)
Newsgroups: comp.programming
Subject: Re: AVL trees - Re: Why Are Red-Black Trees Obscure?
Date: 2 Sep 92 02:22:27 GMT
Article-I.D.: reed.1992Sep2.022227.9117
Organization: Reed College, Portland, OR


  ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:
: There is a curious thing about red-black trees, which is that algorithm
: texts that describe them often leave out the deletion code.

  bevan@cs.man.ac.uk (Stephen J Bevan) writes:
: I don't think this is perculiar to red-black trees. It seems that no
: matter what the tree, many authors leave out deletion code. 

  I'll see your point and raise you a point. Deletion, when implementations
are given, seem to be efficient largely because of a particularly
simplistic representation, like heap allocation. One of the things I want
most from a given data structure is containment within a single memory
block (size proportional to the number of elements) which can grow, shrink
and move around when the structure isn't looking. Hence, my implementations
demand offsets rather than pointers, double links, interleaved binary and
interpolation search operations, and so on.

  Deletion is the thorn in my side. I guess that's half the challenge! And
who knows, maybe it's not just my eccentricity, but all data structures
should have explicit "insert multiple elements" and "delete multiple
elements" operations!

  I'll admit to being dumbstruck by wise data structures sometimes. That
is, I am so impressed at the design, analysis and insight that has been put
into a structure, I am totally humbled when I try to develop alternative
representations, make up operations, or analyze the performance of my own
experimental structures. For instance, I can imagine a deletion on a
Patricia tree, but I seriously doubt whether I have ample understanding of
the subtleties involved to propose an operation that, AFAIK, nobody else
seems to have. 

  Or, say I think I've got a representation for graphs that is as new under
the sun as it is well suited for particular problems. Who am I to suggest
such a thing when Knuth has never mentioned it and it's not in BSD?

  Another good example is trying to reverse engineer the Fibonacci priority
queue from LEDA, which I seem to remember is coded in C++ with commentary
in German. (Why is there so much sexy code out there commented in German?
I've taken a bunch of natural languages, but German just doesn't happen to
be one of them, and it's the only one I have an immediate use for.)


  S_TITZ@iravcl.ira.uka.de (Olaf Titz) writes:
: Another example are Bayer trees, which should be presented to the
: students as thorough as the AVL (or red-black, if you want it) trees just
: because they are the tree structure that suits best to a block-structured
: storage device.

  Never heard of them before, but I like what I hear so far. Are these
significantly different from the B-tree?

  Theus (orpheus@reed.edu)
From: orpheus@reed.edu (P. Hawthorne)
Newsgroups: comp.programming
Subject: Balanced Trees (Re: Why Are Red-Black Trees Obscure?)
Date: 27 Aug 92 21:59:24 GMT
Organization: Reed College, Portland, OR


  psu@cs.duke.edu (Peter Su) laments:
: All of the following are easier than AVL trees: splay trees, red-black
: trees, skip-lists, randomized binary trees, etc. Why do people insist on
: teaching AVL trees?

 (If I reveal some of my profound ignorance here, be gentle with me, huh?
I've never had the pleasure of discussing data structures with others
before, and some of my isolation may show through.)

  Maybe it's because AVL trees are always watching out for and correcting
imbalance. The structures you mention are probabilistic solutions, not hard
and fast guarantees. If you are particularly neurotic about computational
cost and the cost of key compares outweighs the cost of path bookkeeping
and tree rotations, I could see using AVL trees rather than the many "sure
thing" alternatives. Plus, they're exotic Cold War souvenirs!

  I'll agree though, there isn't enough material available on those
structures for the many circumstances in which they are the better
alternatives. Ever tried to find an introduction to Fibonacci heaps or
source for them that isn't in a mishmash of C++ and German?

  Is it a flaw in my implementation, or are top-down splay trees supposed
to revert to a linked list when keys are inserted in order? Does a
bottom-up splay operation solve that problem? I've always wondered.

  I'm partial to Patricia trees, from what I've read. Their balance and
completeness look relatively good. I haven't seen any mention of a deletion
operation on them however, and haven't ever really thought of them as
dynamic structures that one could use where you might use other trees. Is
that just a misconception of mine?

  Has anyone used frequency of node access data to bias the tree balancing
rotation operations toward shorter paths?

  Given an ordered list of keys, what is the fastest way to tell whether or
not they have a uniform probability distribution and just for good measure,
where in the list it breaks down if at all?

  Theus (orpheus@reed.edu)
From: jake@diku.dk (Jacob Bay Hansen)
Newsgroups: comp.programming
Subject: ML or Miranda (PD)
Date: 2 Sep 92 12:21:43 GMT
Organization: Department of Computer Science, U of Copenhagen

Hello,

  Does anyone know if there exists a PD ML- or Miranda-compiler. If
so, I would like a copy (c-source if non-amiga).

Thanks in advance

--JAKE (Jacob Bay Hansen)

#=-=#=-=#=-=#=-=#=-=#=-=#=-=#=-=#=-=#=-=#=-=#=-=#=-=#=-=#=-=#=-=#
|	jake@freja.diku.dk	|	There is something	|
#=-=#=-=#=-=#=-=#=-=#=-=#=-=#=-=#	rotten in the state	#
|     //ONLY	-  Just me and 	|	of Denmark.		|
# \\ // AMIGA	-  my Amiga!!	#		 - Shakespeare	#
|  \X/	CAN    <= NOT Trashcan! |  (What's he talking about?)	|
#=-=#=-=#=-=#=-=#=-=#=-=#=-=#=-=#=-=#=-=#=-=#=-=#=-=#=-=#=-=#=-=#
From: dave@cs.arizona.edu (Dave Schaumann)
Newsgroups: comp.programming
Subject: Re: keyword searching algorithm needed
Date: 26 Aug 92 00:51:59 GMT
Reply-To: dave@cs.arizona.edu (Dave Schaumann)
Distribution: usa
Organization: University of Arizona

In article <25AUG199207313527@quark2.aero.org>, lee@quark2 writes:
>Hi!
>
>I am in desperate need of an algorithm that will search a group of character
>strings for a given substring that I specify.  The catch is that if a match
>isn't found, I need to find "close" or "almost" matches.  How close, I don't
>know yet, but if it is a parameter that I can adjust, it would be great.  Does
>such a beast exist?

Sounds like you want `agrep', which allows searching for close matches.
Check the comp.sources.misc (? maybe .unix) for full details at your
favorite archive site (ftp.uu.net is a good one in the US).

-- 
Dave Schaumann			dave@cs.arizona.edu
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.programming
Subject: Re: AVL trees - Re: Why Are Red-Black Trees Obscure?
Date: 1 Sep 92 10:39:13 GMT
Organization: Comp Sci, RMIT, Melbourne, Australia

In article <1992Aug28.154713.3125@rz.uni-karlsruhe.de>, S_TITZ@iravcl.ira.uka.de (Olaf Titz) writes:
> Because AVL trees are really a wonderful non-trivial example for
> teaching data structures and algorithm design, which has the advantage
> that it is of use in the Real World too.

> Other examples of this useful teaching stuff are Quicksort and the
> classic FFT.

Thank you.  You just convinced me to switch to red-black trees or splay
trees as soon as I understand the relative merits of each.  Quicksort is
_not_ good for teaching because students learn "use Quicksort", which is
not a lesson I hope any competent teacher would _want_ them to learn.
(Merge sort is easier to explain, easier to code correctly, easier to
analyse, and significantly faster.)

There is a curious thing about red-black trees, which is that algorithm
texts that describe them often leave out the deletion code.
-- 
You can lie with statistics ... but not to a statistician.
Newsgroups: comp.programming
From: hermann@uran.informatik.uni-bonn.de (Hermann Stamm)
Subject: Re: Deciding point-in-polygon: A new idea
Reply-To: hermann@uran.informatik.uni-bonn.de (Hermann Stamm)
Organization: Praktische Informatik III
Date: Mon, 31 Aug 1992 08:35:43 GMT

| 
| Article: 1696 of comp.programming
| Path: olymp!Sirius.dfn.de!darwin.sura.net!wupost!cs.utexas.edu!sun-barr!olivea!uunet!peora!tarpit!cs.ucf.edu!schnitzi
| From: schnitzi@cs.ucf.edu (Mark Schnitzius)
| Newsgroups: comp.programming
| Subject: Deciding point-in-polygon: A new idea.
| Message-ID: <schnitzi.715219193@eola.cs.ucf.edu>
| Date: 30 Aug 92 23:59:53 GMT
| Sender: news@cs.ucf.edu (News system)
| Distribution: comp
| Organization: University of Central Florida
| Lines: 15
| 
| 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?
| 
| 
| Mark Schnitzius
| schnitzi@eola.csu.ucf.edu
| Univ. of Central Florida
| 

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!

Here the example to the first proposition:

   P4    P3 Q
             

   P1    P2
   --------
      x

The area of Square P1,P2,P3,P4 is x*x, the area of polygon
P1,Q,P2,P3,P4 is roughly x*x/2 !


Hermann. 
Newsgroups: comp.programming
From: wieser@acs.ucalgary.ca (Bernie Wieser)
Subject: Wanted: algorithms
Date: Fri, 04 Sep 92 18:18:43 GMT
Organization: The University of Calgary, Alberta

I would like to start collecting amazingly simple and refined
algorithms.

Any algorithm will do, so long as it is of great utility.
Things like one-liners, brilliant hacks, etc.  GCD, primes,
RNGs, anything!

I.e. I once heard of a one line test to see if a number was
prime.

So anyone interested, please send me something.  I will
compile them and post.

Thanks.
  
-- 
Bernie Wieser
wieser@acs.ucalgary.ca
HYPROTECH.BW@applelink.apple.com
Newsgroups: comp.programming
From: S_TITZ@iravcl.ira.uka.de (Olaf Titz)
Subject: Re: AVL trees - Re: Why Are Red-Black Trees Obscure?
Organization: Fachschaft Informatik, Uni Karlsruhe
Date: Tue, 1 Sep 1992 14:29:04 GMT
X-News-Reader: VMS NEWS 1.23

In <14298@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au writes:

>  Thank you.  You just convinced me to switch to red-black trees or splay
>  trees as soon as I understand the relative merits of each.  Quicksort is
>  _not_ good for teaching because students learn "use Quicksort", which is
>  not a lesson I hope any competent teacher would _want_ them to learn.
>  (Merge sort is easier to explain, easier to code correctly, easier to
>  analyse, and significantly faster.)

Depends on *how* it's taught. If students learn a number of algorithms
to do the same thing, they can judge which one to use if a real
application is under construction. IMO Heapsort is often neglected
because of its being 'hard to understand' but it has efficiency
advantages over Quicksort, most notably it can *cleanly* be
implemented without recursion.

Another example are Bayer trees, which should be presented to the
students as thorough as the AVL (or red-black, if you want it) trees
just because they are the tree structure that suits best to a
block-structured storage device.

>  There is a curious thing about red-black trees, which is that algorithm
>  texts that describe them often leave out the deletion code.

And Bayer tree descriptions leave out deletion either, as do AVL tree
descriptions, for the reason that it were 'too complicated' :-(


MfG,
        Olaf
-- 
Olaf Titz - comp.sc.student - Univ of Karlsruhe - s_titz@iravcl.ira.uka.de -
uknf@dkauni2.bitnet - praetorius@irc - +49-721-60439 - did i forget something?
The only use I can find for vi is editing the emacs sources
 while porting them to a new machine. - Larry Campbell