HDTenEightyP/NetNews huggingface dataset:
From: dave@cs.arizona.edu (Dave Schaumann)
Newsgroups: comp.programming
Subject: Linking & type safety (was Re: ANSI C, was Re: Teaching the basics)
Date: 23 Aug 92 20:01:21 GMT
Reply-To: dave@cs.arizona.edu (Dave Schaumann)
Organization: University of Arizona

>>Now, a type checking loader would be a fine thing.
>>So just what is the problem here?  Why can't I buy one?

>You can.  It's called a VAX.

Somebody's making a linker called `VAX'?  Just wait'll DEC hears about it...

>However, in Unix, ld (the linker) has lost all
>type information by the time the link occurs.

That's funny.  When I use g++ on this Unix box, it remembers type information
just fine.

The trouble is not "VAX" vs "UNIX" (how could it be?  A VAX is a machine;
UNIX is an OS...).  The trouble is that linker technology remains mired in
the 60's, while computer language has continued to evolve.  So while we
have ANSI giving us prototypes &c for C a few years ago, it also gives us
the "unique in the first 6 characters" rule for external identifiers, and
says nothing at all about type checking at link time.

The trouble is that there are too many people out there with a vested interest
in seeing that C doesn't change too much, so that they can still compile their
old applications; too many people who are unwilling or unable to afford hiring
a programmer to write a modern linker for their pet platform.

The popularity of C is one of its biggest assets when it comes to portability
issues; but it's also its biggest problem when it comes to encorperating new
language technology.  Of course, C has changed and no doubt will continue to
change in the future.  But you have to accept that you'll never be able to
introduce a radical new change again.  Every change will always be incremental,
with all the old obsolete technology held over for an iteration or so to give
the stragglers a chance to catch up.

If you really want to help C, write a system implementation that incorperates
your wonderful new innovation, and then when it comes time to redefine the
standard, you can point to your system and tell ANSI, "See?  Prior art!  Prior
art!".

-- 
Dave Schaumann			dave@cs.arizona.edu
Newsgroups: comp.programming
From: markh@csd4.csd.uwm.edu (Mark)
Subject: Re: AVL trees - Re: Why Are Red-Black Trees Obscure?
Organization: Computing Services Division, University of Wisconsin - Milwaukee
Date: Wed, 2 Sep 1992 13:18:06 GMT

In <1992Sep2.022227.9117@reed.edu> orpheus@reed.edu writes:
>    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.)

In article <1992Sep2.103526.20072@rz.uni-karlsruhe.de> S_TITZ@iravcl.ira.uka.de (Olaf Titz) writes:
>An interesting question, in Germany too: Which *natural* language to
>use? Many people write their comments in English, but there are some
>(esp. in the academic environment) who do everything in German, to
>(allegedly) 'enhance understandability' (which is not true in most
>cases) or just to keep hold on the use of German. But not
>understanding the language is always a problem. If you want to study
>Informatik (Computer Science) in Germany and don't know English,
>you'll get into trouble.
>MfG,
>        Olaf

I personally don't care what language anyone writes their comments in.  Number
one, I don't pay attention to the comments because it gets in the way of
reading and understanding the code and seeing its structure.  Two, if it's any
language from Europe, I'll probably understand the comments.  Three, if I
don't understand it, then that's even better, because then I have a Rosetta
Stone, since I already understand the code.  So then that's yet another
language I get an easy opportunity to learn, using the program itself.
From: tmp16@nuscc.nus.sg (temporary account for courses)
Newsgroups: comp.programming
Subject: clustering algorithm wanted
Date: 27 Aug 92 10:33:32 GMT
Organization: National University of Singapore

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.

Thanks in advance .

-Kenneth Ban
 Dept. of Biochemistry
 National University of Singapore

-- 
-------------------------------------------------------------------------------
Kenneth Ban                       
Dept. of Biochemistry        	    
Faculty of Medicine
From: herman@nosc.mil (John W. Herman)
Newsgroups: comp.programming
Subject: Re: Morphology and Convolution
Keywords: morphology,convolution,aaaaargh
Date: 26 Aug 92 14:44:46 GMT
Organization: Naval Ocean Systems Center, San Diego, CA

atbowler@thinkage.on.ca (Alan Bowler) writes:

>In article <1992Aug25.160119.28049@linus.mitre.org> bdickens@el_padre.mitre.org (Brian Dickens) writes:
>>I am trying to perform convolution on a rectangular matrix of numbers.  

>You want to look at using a Fast Fourier transform.

The convolution operation is more complicated than this.  You might ask
this question in the comp.dsp news group.
Newsgroups: comp.programming
From: roarf@stud.cs.uit.no (Roar Foshaug)
Subject: Re: Help - Contour drawing algorithm needed
Organization: University of Tromsoe, Norway
Date: Thu, 27 Aug 1992 14:33:28 GMT

In article <1992Aug25.165307.21995@tamsun.tamu.edu>, tpradeep@cs.tamu.edu (Pradeep K Tapadiya) writes:
|> 
|> 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


What about using a scan-line technique? You iterate across
the scanline, and if two neighbouring temperature points 
are different (sufficiently different?) then you plot a point. 

This way curves will be built up.


-Roar-


-- 
Roar Foshaug                                      (roarf@stud.cs.uit.no)
Department of Computer Science
University of Tromsoe                             'oe' is '\o{}' in Tex
N-9000 TROMSOE, NORWAY                            'OE' is '\O{}' in Tex
From: vince@eye.com (Vince Mehringer)
Newsgroups: comp.programming
Subject: Point in Polygon
Date: 2 Sep 92 21:01:14 GMT
Distribution: usa
Organization: 3D/EYE, Inc.  Ithaca, NY

For all you point-in-polygon types, make sure to catch the special
issue of _Ray Tracing News_ in comp.graphics -- it's devoted to this
topic.

In fact, further discussion of this topic is more appropriate in that
forum than here.
Newsgroups: comp.programming
From: markh@csd4.csd.uwm.edu (Mark)
Subject: Re: Teaching the basics
Organization: Computing Services Division, University of Wisconsin - Milwaukee
Date: Tue, 25 Aug 1992 17:42:43 GMT

In article <7116@charon.cwi.nl> tromp@cwi.nl (John Tromp) writes:
>>On top of it all, the recursive version does not have an arbitrary
>>limit on the number of disks, and can be easily translated to any
>>language supporting recursion.
>
>Well, nobody in his right mind would ever run hanoi on 32 discs or more:-)
>
>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.

#include <malloc.h>
#include <stdio.h>

typedef struct Tree *Tree;
struct Tree {
   char *S; int Key, State;
   Tree Left, Right;
};
Tree Root;

Tree Find(int Key) {
   Tree Prev, Cur;
   for (Prev = 0, Cur = Root; Cur != Prev; ) {
      if (Cur->Key == Key) return Cur;
      Prev = Cur, Cur = (Cur->Key < Key)? Cur->Left: Cur->Right;
   }
   Cur = (Tree)malloc(sizeof *Cur);      /* Add in your own error checks */
   Cur->Key = Key, Cur->State = 0;
   Cur->Left = Cur->Right = Cur;
   if (Prev == 0) Root = Cur;
   else if (Prev->Key < Key) Prev->Left = Cur; else Prev->Right = Cur;
   return Cur;
}

#define PRE_ORDER  0
#define IN_ORDER   1
#define POST_ORDER 2

#define BACKWARDS 0
#define FORWARDS  1
void Traverse(int Dir, int Order) {
   Tree Prev, Cur;
   for (Prev = 0, Cur = Root; Cur != 0; ) {
      Tree T;
      if (Cur->State == Order) printf(" %s", Cur->S);
      Cur->State = (Cur->State + 1)%3;
      if (Dir == BACKWARDS) {
         T = Cur->Left, Cur->Left = Cur->Right,
         Cur->Right = Prev, Prev = Cur, Cur = T;
      } else {
         T = Cur->Right, Cur->Right = Cur->Left,
         Cur->Left = Prev, Prev = Cur, Cur = T;
      }
   }
}

main() {
   Tree T0, T1, T2, T3, T4, T5, T6, T7;
   Root = 0;
   T3 = Find(3), T0 = Find(0), T4 = Find(4), T6 = Find(6),
   T5 = Find(5), T1 = Find(1), T7 = Find(7), T2 = Find(2);
   T0->S = "This", T1->S = "is", T2->S = "a", T3->S = "non",
   T4->S = "recursive", T5->S = "tree", T6->S = "traversal",
   T7->S = "routine";
   printf("Backwards,  pre order:"); Traverse(BACKWARDS, PRE_ORDER);
   putchar('\n');
   printf("Backwards, post order:"); Traverse(BACKWARDS, POST_ORDER);
   putchar('\n');
   printf("Backwards,   in order:"); Traverse(BACKWARDS, IN_ORDER);
   putchar('\n');
   printf("Forwards,   pre order:"); Traverse(FORWARDS,  PRE_ORDER);
   putchar('\n');
   printf("Forwards,  post order:"); Traverse(FORWARDS,  POST_ORDER);
   putchar('\n');
   printf("Forwards,    in order:"); Traverse(FORWARDS,  IN_ORDER);
   putchar('\n');
}
Newsgroups: comp.programming
From: berlin@is.morgan.com (Alexander Berlin)
Subject: Re: How to decide if a point is inside a polygon?
Organization: Morgan Stanley - IS
Date: Thu, 27 Aug 1992 19:39:02 GMT

In article <schnitzi.714934670@eola.cs.ucf.edu>, schnitzi@cs.ucf.edu (Mark Schnitzius) writes:
|> 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.

Correct, but a word of caution should be said.
When drawind the line in any direction, you want to avoid
crossing corners of the polygon. So, make sure no one of the given points
(that make polygon) belongs to the line.

        A           B
        .___________.
         \         /
          \  Y.   /
           \  |  /
    X       \ | /
    .________\|/___________________
              |
              | C
              |

In the above example X is outside triangle ABC, Y is inside it. Their lines
exactly the same crossings whith the edge. So instead of coming up with
additional complicated rules just make sure you don't hit the corners. 

|> 
|> Mark Schnitzius
|> schnitzi@eola.cs.ucf.edu
|> University of Central Florida
---
Alex Berlin                     
berlin@is.morgan.com
Newsgroups: comp.programming
From: irving@casbah.acns.nwu.edu (Thomas Myers)
Subject: Assembly Alogrithm Needed
Summary: Help with DIVIDE routine
Organization: Northwestern University, Evanston, Illinois, USA
Date: Fri, 4 Sep 1992 12:52:55 GMT


We have a hardware circuit which needs to divide integers using a Motorola
68HC05 chip.  The instruction set contains only a limited complement of
instructions, notable missing is a divide instuction.  It is an 8 bit chip with
stack, Accumulator, Index Register and Flags.

What we need to do is to divide two 8 bit integers with a precision of two
(2) decimal places (ie 246/127 = 1.94).  It also must be as fast as possible.

The algorithm I devised seems too brute force:

	1.  Loop:  Subtract  Den from Num incrementing Quot
	2.         Multiply  Num and Quot by 10
	3.  Etc. for two decimal places...

In order to accomplish this, more than 8 bits need to be used to represent the
Numerator (ie Remainder times 10 exceeds 255).  The algortihm to force a 16
bit representation of the numerator is pretty wretched.

I'm sure that there must be tried and true mechanisms to accomplish this.

Please contact me if you have suggestions or need further information.

Thanks
From: S_TITZ@iravcl.ira.uka.de (Olaf Titz)
Newsgroups: comp.programming
Subject: AVL trees - Re: Why Are Red-Black Trees Obscure?
Date: 28 Aug 92 15:47:13 GMT
Organization: Fachschaft Informatik, Uni Karlsruhe
X-News-Reader: VMS NEWS 1.23

In <PSU.92Aug27104235@ptero.cs.duke.edu> psu@cs.duke.edu writes:

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

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. The same holds for Bayer
trees, but AVL are even more beautiful. The operations to perform on
AVL trees are not *that* complicated; they achieve good (well,
asymptotically optimal) performance results; they are yet used in many
places (not really an argument, but...); and they show the principles
of recursion and induction. (Have I left out any advantages?) On the
other hand, I see no real disadvantages of AVL trees.

Other examples of this useful teaching stuff are Quicksort and the
classic FFT. There are many, many other algorithms around equally well
suited for teaching, but you have to choose which ones you use, and
if AVL trees suit your needs and taste, why not?


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?
OS/360 devotes 26 bytes of the permanently resident date-turnover routine
 to the proper handling of Dec.31 on leap years. That might have been
 left to the operator. - Fred Brooks (1975)
From: atbowler@thinkage.on.ca (Alan Bowler)
Newsgroups: comp.programming
Subject: Re: Morphology and Convolution
Keywords: morphology,convolution,aaaaargh
Date: 26 Aug 92 00:20:16 GMT
Organization: /etc/organization

In article <1992Aug25.160119.28049@linus.mitre.org> bdickens@el_padre.mitre.org (Brian Dickens) writes:
>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.

You want to look at using a Fast Fourier transform.  You do a forward
transform on both the input, and the fixed numbers.  do a point by
point multiply (N operations) and then do a reverse transform.  Since
the fixed numbers are constant, you only need to do the forward
transform on them.  I once worked on a integer version of this,
but given the speed of modern floating point hardware, and all integer
version is not worth the hassles it intoduces.  A good time time
series analysis library may have all the stuff you need.
Newsgroups: comp.programming
From: schwartz@roke.cs.psu.edu (Scott Schwartz)
Subject: Re: Teaching the basics
	<7116@charon.cwi.nl> <1992Aug25.174243.10436@uwm.edu>
Date: Tue, 25 Aug 1992 19:35:00 GMT

markh@csd4.csd.uwm.edu (Mark) writes:
   Wrong.  In fact, the non-recursive version (tree search) is far smaller and
   simpler.  No stacks either.

Actually, the search algorithm is tail recursive, so you can code it
in the straightforward (recursive) way and let the compiler generate
the iterative code.  Gcc and Sun's CC do this.
Newsgroups: comp.programming
From: mjs@hubcap.clemson.edu (M. J. Saltzman)
Subject: Re: Detecting Integer Overflow/Underflow
Organization: Clemson University, Clemson SC
Date: Sun, 23 Aug 1992 19:25:31 GMT

In article <51147@seismo.CSS.GOV> black@seismo.CSS.GOV (Mike Black) writes:
>In article <1992Aug21.182206.15853@progress.com> erf@progress.com writes:
>>
>>Given: Two numbers (integers) of the same bit-width (e.g., they're
>>both stored as 16-bit integers), and writing in "C" (with no access to
>>the assembly language of the machine; it must be portable!) is it
>>possible to write code to detect whether the result of adding,
>>substracting or multiplying the two numbers will result in overflow or
>>underflow?  The detection can be done either before or after the
>>operation.  It should, of course, be as efficient as possible, but any
>>solutions are welcome.
>>
>
>I already mailed a reply to this, but after seeing the postings thought
>I should add it here:
>
>Since the person wants a solution that is portable, in C, and addresses
>addition, subtraction, and multiplication a solution is quite 
>straightforward.  USE LONGS!  Simply caste the operands into longs,
>perform the math, and check the answer.  If the answer is within 16-bit
>limits (signed or unsigned) return the answer else set overflow.

Well, the original poster did ask for a *portable* solution.  You have
assumed that longs are always larger than ints (or shorts), which is
not true in general.

Another point is that for full portability, the test for overflow must
be done *before* the operation, since some machines will trap on
integer overflow.  On a two's complement machine, you could do the
addition in *unsigned* arithmetic, cast the result back to int, then
check the sign of the result (if both operands are positive).  If you
want to allow the possibility of a result equal to INT_MIN (from
limits.h) on such a machine, the test is slightly more complicated.
-- 
		Matthew Saltzman
		Clemson University Math Sciences
		mjs@clemson.edu
Newsgroups: comp.programming
From: gillies@m.cs.uiuc.edu (Don Gillies)
Subject: Re: Balanced Trees (Re: Why Are Red-Black Trees Obscure?)
Organization: University of Illinois, Dept. of Comp. Sci., Urbana, IL
Date: Fri, 28 Aug 1992 07:51:02 GMT

orpheus@reed.edu (P. Hawthorne) writes:

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

No, there are many ways to get a linked list when inserting keys into
a splay tree.  The key is, if you continue to use splay(), the linked
list quickly becomes a near-balanced-binary-tree.  There are obscure
access patterns to get the structure back to a linked list, but then
from that organization, most access patterns will tend to rebalance
the tree rather quickly.

>  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

What are patricia trees?  Please respond via email.

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

compute the entropy (see an information-theory textbook).  For
sequentially degeneracy (a repetitive sequence of keys), if they are
8-bit or 16-bit keys, you might try running them through "compress".
If they compress well, the key ordering is probably degenerate.



-- 



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:11:34 GMT

In article <1992Aug27.170349.13453@uwm.edu> markh@csd4.csd.uwm.edu (Mark) writes:
>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.

It won't be zero if the point lies outside the polygon.  It will be some
multiple of 360 larger than 360.
From: adrian@mti.mti.com (Adrian McCarthy)
Newsgroups: comp.programming
Subject: Re: Spell checking routine
Date: 2 Sep 92 23:08:24 GMT
Organization: Micro Technology, Inc., Anaheim, CA

In article <la5rkvINN9vr@aludra.usc.edu> joseph@aludra.usc.edu (Jeff Lawson) writes:
>I need a routine that will suggest words for a mispelled word from a
>large dictionary.  I'd like something that could produce words with
>totally different spellings, like WordPerfect's.  It doesn't really
>matter what code it's written in, but C is preferable.  Thanks

One of my favorite techniques that I use in my toy spell checker is to use
multiple hash indexes into the dictionary.  Each has index is generated with
a different type of hash function.  The main hash function is the usual sort,
designed for efficient lookup.

The additional hash functions are designed to cause words that are alike
in some way to collide.  Thus, once you look up the incorrect word,
you don't have to do any more work to guess at correct spellings; a list
of guesses is already computed and stored as the collision list.  Precomputing
the index when the dictionary is built means that guessing is blindingly fast.

For example, a hash function based on a Soundex-type of algorithm will
automatically give you a list of words which sound like the word you tried to
look up (within the limits of the Soundex algorithm).

I have another hash function which maps characters to the finger a touch typist
would use.  This quickly finds mistakes where you used the right finger, but
missed the key you aimed at.

Yet another hash function is bitmask of characters, so words that are anagrams
of each other map to the same index.  This is very useful for quickly solving
word-jumble puzzles or making a program to play Scrabble.  (It's also not too
bad at finding transposed characters, but it tends to find a lot of other words
as well.)

This technique has worked pretty well for me.  I've found it's quicker to
try to sort a precomputed list of guesses based on similarity to the original
word than to work the other direction.  Of course, there is a big space
trade-off because the hash indexes may be large for a big dictionary.

Using the more traditional approach of generating guesses, it's pretty
straightforward to transpose adjacent characters, delete characters, and
substitute characters.  To quickly make reasonable guesses for inserting
characters, compute the frequency of all of the trigraphs (3-letter
combinations) in your dictionary.  Build a sparse 2-d table indexed by the
first and last letter whose values are a sorted list of the most common
interceding letters.  (If memory requirements are very limiting, you could
try a simpler but similar approach using digraphs instead of trigraphs.)

Aid.  (adrian@lexcel.com)
Newsgroups: comp.programming
From: ap@jyu.fi (Patric Aalto)
Subject: Re: How to decide if a point is inside a polygon?
Organization: University of Jyvaskyla, Finland
Date: Tue, 1 Sep 1992 06:18:20 GMT

What's wrong with the method (or was there three different methods?)
mentioned in the FAQ of comp.graphics? I had thought those methods were
the correct ones.

Patrick Aalto
ap@tukki.jyu.fi