HDTenEightyP/NetNews huggingface dataset:
From: brnstnd@nyu.edu (Dan Bernstein)
Newsgroups: comp.programming
Subject: --- comp.programming charter: read before you post (weekly notice)
Date: 30 Aug 92 04:00:10 GMT
Organization: IR

comp.programming	Programming issues that transcend languages and OSs.

It is a matter of courtesy to read a USENET group for at least a month
before posting anything to it. You should be familiar with this article
and with all the regular announcements in news.announce.newusers. A
newsgroup is like a crowded meeting hall filled with people who want to
talk about similar subjects. Chances are that if you just stick your
head in and shout, you'll be saying something totally inappropriate or
asking a question which someone else asked last week, and everyone will
be angry at you. To avoid this, _read_ before you post.

What you _should_ post here (the charter):

	comp.programming is an unmoderated group for discussions of
	programming issues which are not limited to a specific machine,
	operating system, or language: in particular, algorithms of all
	types. ``Programming issues'' means _practical_ programming
	issues: it is considered very bad form here to discuss issues
	with which you do not have direct programming experience.

What you _should not_ post here:

	Any issue which is limited to a specific machine, operating
	system, or language is completely inappropriate for this group.
	If you are programming under UNIX, use comp.unix.programmer. If
	you are programming a PC, use comp.os.msdos.programmer. If you
	are programming a Mac, use comp.sys.mac.programmer. If you are
	programming an Amiga, use comp.sys.amiga.programmer. If you are
	programming a game and think that your question is of interest
	to other game programmers, use rec.games.programmer. If you're
	absolutely sure that your question is on the use of the C
	language---it wouldn't make sense if you were using a different
	language---try comp.lang.c. If your question is a meta-question
	which has to do with features of various programming languages,
	use comp.lang.misc. If your question has to do with theoretical
	results which have to do with computer science rather than
	programming, try comp.theory. Finally, if you're sure that your
	question would make sense under a variety of operating systems,
	running on a variety of machines, and in a wide variety of
	programming languages, then comp.programming is probably right.

	Note added 3/9/92: If you want source code for something, you'll
	get better response in comp.sources.wanted, which was created to
	handle such requests.

Other comp.programming conventions:

	It's often difficult to talk about programming without quoting
	the results of that programming---i.e., code. There is nothing
	wrong with using a particular language to present code samples,
	as long as they _could_ have been expressed in various other
	languages. However, you are less likely to have your question
	understood if you illustrate it with a choice segment of APL
	than if you use pseudo-code, Algol, C, etc.

For future reference, comp.programming passed by a vote of 403-47. It
was created 3/1/92.

---Dan
Newsgroups: comp.programming
From: schnitzi@cs.ucf.edu (Mark Schnitzius)
Subject: Deciding point-in-polygon: A new idea.
Organization: University of Central Florida
Distribution: comp
Date: Sun, 30 Aug 1992 23:59:53 GMT

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
Newsgroups: comp.programming
From: markh@csd4.csd.uwm.edu (Mark)
Subject: Re: clustering algorithm wanted
Organization: Computing Services Division, University of Wisconsin - Milwaukee
Date: Thu, 27 Aug 1992 16:46:56 GMT

In article <1992Aug27.103332.16604@nuscc.nus.sg> tmp16@nuscc.nus.sg (temporary account for courses) writes:
>I am working on some numerical data and I wish to obtain an algorithm
>for clustering these data into discrete groups ( i.e a pattern ). I've
>considered using multivariate analysis but can't get a workable method.
>So if anyone knows of such an algorithm or has a reference, I would
>appreciate it if one could post it to me.

Well, here's an idea.  Suppose you want to cluster the objects into a pre-
determined number of clusters (N).  For a given clustering, define the
cluster error to be the sum of the square deviations of each item from it's
cluster's average.  The task is to minimize this -- which defines the optimum
clustering.

So start with all objects in one cluster, and with N - 1 empty clusters.  At
each step choose a random object and random cluster.  Move the object to this
cluster if and only if the error value mentioned above decreases as a result.

Stop when the error value become stationary long enough.  The result should be
a good approximation of the optimal clustering.

Do obvious things to minimize the computation, such as maintaining cluster
sums and sum-of-squares for each cluster.  Then when an object is moved,
you only need to update 4 items and you only need to perform a test to see if
the total square deviation of those two clusters decreases, instead of
computing the square deviation for all the clusters.
From: bevan@cs.man.ac.uk (Stephen J Bevan)
Newsgroups: comp.programming
Subject: Re: AVL trees - Re: Why Are Red-Black Trees Obscure?
Date: 1 Sep 92 14:22:51 GMT
	<1992Aug28.154713.3125@rz.uni-karlsruhe.de>
	<14298@goanna.cs.rmit.oz.au>
Organization: Department of Computer Science, University of Manchester
In-reply-to: ok@goanna.cs.rmit.oz.au's message of 1 Sep 92 10:39:13 GMT

In article <14298@goanna.cs.rmit.oz.au> 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.

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 have _purely_functional_ AVL and red-black code but neither has
an efficient delete operation :-<

bevan
Newsgroups: comp.programming
From: draper@ais.org (Patrick Draper)
Subject: Re: Why Are Red-Black Trees Obscure?
Organization: UMCC
Date: Thu, 27 Aug 1992 15:54:57 GMT

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.


------------------////////////////////\\\\\\\\\\\\\\\\\\\\------------------
| Patrick Draper           Disclaimer:  I can't control my fingers,        |
| draper@umcc.ais.org                   I can't control my toes! - Ramones |
| University of Michigan                                                   |
| Computer Club                We are a nation of laws, not people         |
------------------\\\\\\\\\\\\\\\\\\\\////////////////////------------------
From: psu@cs.duke.edu (Peter Su)
Newsgroups: comp.programming
Subject: Re: Teaching the basics
Date: 26 Aug 92 13:13:52 GMT
	<1992Aug25.174243.10436@uwm.edu> <1992Aug26.111240.8239@ITcorp.com>
Organization: Duke University CS Dept., Durham, NC
In-reply-to: geoff@ITcorp.com's message of 26 Aug 92 11:12:40 GMT

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, 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.

Pete
--
Department of Computer Science, Duke University, Durham, NC 27706
Internet:	psu@cs.duke.edu
UUCP:		mcnc!duke!psu
From: dsb@osustat.mps.ohio-state.edu (David S. Blumenthal)
Newsgroups: comp.programming
Subject: Request for Curve Description Algorithms
Date: 27 Aug 1992 19:19:47 GMT
Organization: OSU Statistical Computing Laboratory
Distribution: world
NNTP-Posting-Host: osustat.mps.ohio-state.edu

In a program I have been working on, I have come across the need for an
eficient way to describe curves in a two dimensional space.  The curves may
range in complexity from a straight line to something on the order of a
figure eight symbol.

    I need to store a description of the curve in a data file with just
enough description for another program to plot an object moving along the
curve as a function of time - i.e. plot x and y as functions of t.

    To give a more clear idea of what I need to do, the program I am writing
will create a graphical animation of ball paths in juggling patterns.  When
a ball in the air, I can describe its path during a known time interval as
the parabola with given endpoints and a known acceleration.  When the ball
is in a hand, however, it may have a very complex path (known as flairs in
juggling :-).

    I originally thought of using something based on besier curves (about
which I know almost nothing), but it has also occured to me that a low order
fourier series may be more efficient.  I would greatly appreciate any hints,
suggestions, algorithms, insites, descriptions, references, suggested readings,
etc. for curve description methods or any other related topics.

    Please reply via email, and I will post to this group a summary of what
I receive.  Thank you very much for your time and effort.

   Walnuts and good cheer,
   Dave Blumenthal
   dsb@osustat.mps.ohio-state.edu

-----------------------------------------------------------------------
| Dave Blumenthal                  | The Ohio State University        |
| dsb@osustat.mps.ohio-state.edu   | Statistical Computing Laboratory |
------ There is a fine difference between insight and insanity. -------

The above post is not intended to represent my employer in any way.
-- 
-----------------------------------------------------------------------
| Dave Blumenthal                  | The Ohio State University        |
| dsb@osustat.mps.ohio-state.edu   | Statistical Computing Laboratory |
------ There is a fine difference between insight and insanity. -------
From: moose@svcdudes.com
Newsgroups: comp.programming
Subject: Re: How to decide if a point is inside a polygon?
Date: 27 Aug 92 16:24:41 GMT
Reply-To: moose@svcdudes.com
Distribution: na
Organization: Software Ventures, Inc.

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.
> 

Draw a line from the point to anywhere definately outside the polygon.  Count  
the number of times the line crosses the polygon border.  If it's odd, the  
original point is inside the polygon, if it's even, it was outside.


--
Michael Rutman			|	moose@svcdudes.com
Cubist				|	makes me a NeXT programmer
Software Ventures		|	maker of MicroPhone Pro
#include <std.disclaimer>	|	really offesive political statement
Newsgroups: comp.programming
From: as629@cleveland.Freenet.Edu (Larry Schillig, Jr.)
Subject: Selling Shareware
Organization: Case Western Reserve University, Cleveland, Ohio, (USA)
Date: Thu, 27 Aug 92 17:02:06 GMT


      I've seen in the malls and at computer shows people who sell
shareware or freeware for one to three dollars. Is this legal? 
     I was thinking of doing this myself but don't want to step
on any buddys toe's.
     Is there any way to tell if a piece of software from a 
bulletin board can be sold this way.
    Also could someone define the terms shareware vs. freeware
or other terms that may apply.
      Thanks.
			Larry Schillig
Newsgroups: comp.programming,comp.theory.cell-automata,misc.books.technical,misc.wanted
From: toma@romulus.cray.com (Thomas Arneberg)
Subject: BOOK WANTED: _Elements of Theory of Computation_
Organization: Cray Research, Inc.
Distribution: usa
Date: 2 Sep 92 09:55:40 CDT

I would like to BUY the following book, if anyone has one for sale:

         TITLE:      _Elements of Theory of Computation_
         AUTHORS:    Lewis & Papadimitrou
         Publisher:  Prentice-Hall

Please include shipping costs in your offer to sell.

Thanks,
  - Tom A.
---------------------------------------------+------------------------------
;-) I'd rather be ____  Thomas R. Arneberg   | Inet: toma@cray.com
:-) singing in a |____| Senior IC Design Eng.| UUCP: ...!uunet!cray!toma
:-) Barbershop  _|   _| Cray Research, Inc.  | CLAIM TO FAME: Loni Anderson 
:-) Quartet!   (_)  (_) Chippewa Falls, Wisc.|   went to my high school 
---------------------------------------------+------------------------------
From: protonen@daimi.aau.dk (Lars J|dal)
Newsgroups: comp.programming
Subject: Re: Why Are Red-Black Trees Obscure?
Date: 27 Aug 92 11:55:51 GMT
Organization: DAIMI: Computer Science Department, Aarhus University, Denmark

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?

>Theus (orpheus@reed.edu)

Probably because the AVL trees are easier to implement. I'm no expert in
the field, but I have seen the source code for at program using AVL trees.
The balancing was farely simple, something like "if I have put a new
element in the biggest part of the current (sub)tree then I should
rearrange my two subtrees a bit."
Balancing the red-black trees, on the other hand, involves recognizing
the near pattern of the tree, including going up the tree and down another
branch. This means you need a more complicated datastructure (e.g. a list
of pointers to some nodes above the current), and you need code for
recognition of all the different patterns. Although the number of such
patterns is farely small it is bigger than the number of possibilities
in an AVL tree, and the code needed for each possibility is smaller in
an AVL tree. 
So, although the red-black tree may seem simple on paper, it is not as
simple to program. This is probably because humans are much better than
computers at pattern recognition.

Lars (protonen@daimi.aau.dk)
Newsgroups: comp.programming
From: thompson@atlas.socsci.umn.edu (T. Scott Thompson)
Subject: Re: How to decide if a point is inside a polygon?
Reply-To: thompson@atlas.socsci.umn.edu
Organization: Economics Department, University of Minnesota
Date: Sat, 29 Aug 1992 02:49:29 GMT

schnitzi@cs.ucf.edu (Mark Schnitzius) writes:

>You are right; sorry, I misunderstod your earlier point.  So how can we
>get this to work for all cases?  Just find a direction to extend the
>infinite line that doesn't intersect any vertices?

Not a good idea.  Choosing a new direction means starting over and
wasting your previous calculations.  There are ways to fix up the
"vertex" and "colinear edge" problems without having to choose a new
direction.

For details, look at the thread on this same topic on the newsgroup
sci.math that gives specific references to some methods that deal with
the various things that can go wrong.  (The original question was also
posted to that group.)
--
T. Scott Thompson              email:  thompson@atlas.socsci.umn.edu
Department of Economics        phone:  (612) 625-0119
University of Minnesota        fax:    (612) 624-0209
Newsgroups: comp.programming
From: schnitzi@cs.ucf.edu (Mark Schnitzius)
Subject: Re: How to decide if a point is inside a polygon?
Organization: University of Central Florida
Date: Fri, 28 Aug 1992 20:02:22 GMT

berlin@is.morgan.com (Alexander Berlin) writes:
>| I write:
>|> Well, one solution to this problem is this: consider each vertice of the
>|> polygon as belonging to only _one_ of the line segments it is connected to.
>|> So in the above example,  only consider point C to be on the line segment
>|> BC and not on AC.  Then if the line you're drawing goes through point C,
>|> it is only considered to have gone through line segment BC and not AC.
>|> This simple fix should clear up any problems.

>No, it doesn't. I didn't say that the line drawn from point X has one or two
>crossings. My point is that X-line and Y-line have the same number of crossings
>(be it 1 or 2) while X is outside and Y is inside. The fix you suggest doesn't
>distinguish X- and Y- cases in my example.
>The rule that would work is to check if AC and CB segments are on the same 
>side of the line (2 or 0 crossings, case X) or on the different sides 
>(1 crossing, case Y). But I think it is much better to just avoid these
>confusing cases. 

You are right; sorry, I misunderstod your earlier point.  So how can we
get this to work for all cases?  Just find a direction to extend the
infinite line that doesn't intersect any vertices?

Mark Schnitzius
schnitzi@eola.cs.ucf.edu
University of Central Florida
Newsgroups: comp.programming
From: tada@athena.mit.edu (Michael J Zehr)
Subject: Re: How to decide if a point is inside a polygon?
Organization: Massachusetts Institute of Technology
Date: Wed, 2 Sep 1992 01:05:12 GMT

In article <17n15nINNehp@agate.berkeley.edu> bsmith@mickey.NoSubdomain.NoDomain (Brian Smith) writes:
>I got this off the net a while ago.  The original poster was Michael J.
>Zehr, from MIT at the time.  It uses a clever version of the "scan in any
>direction any see how many times the point crosses the polygon" test that, as
>far as I know, handles the special cases correctly.
>[...]
>Brian C. Smith				arpa:  bsmith@cs.Berkeley.EDU
>University of California, Berkeley	uucp: uunet!ucbvax!postgres!bsmith
>Computer Sciences Department		phone: (510)642-9585

Thank you Brian!  I was about to post something similar again.  I wonder
if this should go in some FAQ someplace considering that number of times
I've seen this question raised and the wrong answers posted....

-michael j zehr
From: psu@cs.duke.edu (Peter Su)
Newsgroups: comp.programming
Subject: Re: Why Are Red-Black Trees Obscure?
Date: 27 Aug 92 14:42:35 GMT
Organization: Duke University CS Dept., Durham, NC
In-reply-to: protonen@daimi.aau.dk's message of 27 Aug 92 11:55:51 GMT

Pet Peeve Time:

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?

Pete
--
Department of Computer Science, Duke University, Durham, NC 27706
Internet:	psu@cs.duke.edu
UUCP:		mcnc!duke!psu
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 18:30:42 GMT

In article <1992Aug26.172830.21172@organpipe.uug.arizona.edu> dave@cs.arizona.edu (Dave Schaumann) writes:
>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.

You're right.  It isn't.  And that illustrated (in part) above is not only a
very readible style of formating -- but in fact one of the most.  Having it
criticized by someone who even seriously brings up mention of utilities like
indent, or Emacs only serves to reinforce that assessment of its readibility.
From: schnitzi@cs.ucf.edu (Mark Schnitzius)
Newsgroups: comp.programming
Subject: Re: How to decide if a point is inside a polygon?
Date: 27 Aug 92 16:57:50 GMT
Organization: University of Central Florida

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.

If I remember right the trick is to extend a line from the point
infinitely in any direction (say, up).  Count how many of the
polygon's edges this line passes through.  If it passes through
an even number of polygon edges (including zero) the point is
outside of the polygon.  An odd number indicates the point is
inside the polygon.

Mark Schnitzius
schnitzi@eola.cs.ucf.edu
University of Central Florida
Newsgroups: comp.programming
From: markh@csd4.csd.uwm.edu (Mark)
Subject: Re: How to decide if a point is inside a polygon?
Organization: Computing Services Division, University of Wisconsin - Milwaukee
Date: Thu, 27 Aug 1992 17:03:49 GMT

In article <7121@bigbird.hri.com.hri.com> mps@hri.com 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.

Implement a polygon by putting its vertices in counter-clockwise order in a
circular list.  A line drawn from a point inside to each of the vertices of
the list will move in a counter clockwise direction as you go through each
vertex in the list.  In other words, the sum of the angles AVB where V is the
point in question and A and B are adjacent items in the circular list, where
each angle is measured in a counterclockwise direction, will be 360 degrees.
If the point lies outside the polygon, this sum will be 0.  If the point, V,
lies ON the polygon, the sum will be 360.

So, this algorithm is linear in the number of vertices in the polygon.

In order to verify that you properly implemented the polygon, you have to
perform a one-time check to make sure that the sum of all the angles ABC,
where A, B, and C are adjacent items in the circular list, is 180*(N - 2)
degrees, where N is the number of points in the polygon.  Again, the angles
are measured in a counterclockwise direction.
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: Wed, 2 Sep 1992 10:06:56 GMT
X-News-Reader: VMS NEWS 1.23

In <1992Sep2.022227.9117@reed.edu> orpheus@reed.edu writes:

>    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?

B-tree == Bayer tree (seems to be an abbreviation, but maybe 'Bayer'
isn't used much outside German textbooks :-)



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?
In hardware engineering, Ohm's law and Maxwell's equations pale in
  importance and influence next to Murphy's law. - Gordon Bell
Newsgroups: comp.society.development