HDTenEightyP/NetNews huggingface dataset:
From: tromp@cwi.nl (John Tromp)
Newsgroups: comp.programming
Subject: Re: Teaching the basics
Date: 26 Aug 92 08:39:58 GMT

markh@csd4.csd.uwm.edu (Mark) writes:

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

Maybe I didn't make myself clear enough. I wasn't referring to mere
tree *traversals* but to algorithm that keep some state information at each
node. For instance, the alpha-beta algorithm keeps track of upper and lower
bounds in each call, not globally. In contrast to towers-of-hanoi, this
information does not derive from the current location of the search.

These are the types of problem that recursion is most suited to.

-John Tromp
From: etf@controls.ccd.harris.com (Ed Farrar)
Newsgroups: comp.programming
Subject: Dictionary w/ definations needed
Keywords: dictionary definations
Date: 4 Sep 92 14:20:32 GMT
Organization: Harris Controls
Originator: etf@rs2


Hello,

	I am in need of a dictionary file that has definations in at instead
of just a spelling type dictionary.  Is there any such file existing.  The 
purpose is to search the dictionary and have it display the defination of
the found word and possibly how to pronounce the word.  An electronic Webster's
would be great!

Thanks,
Ed Farrar

--
-- 
Edward T. Farrar
Harris Controls Division                   |    Phone : 407-242-5095
P.O. Box 430                               |    Fax   : 407-242-4268
Melbourne, Florida 32902-0430              |    Email : etf@ccd.harris.com
From: tromp@cwi.nl (John Tromp)
Newsgroups: comp.programming
Subject: Re: Teaching the basics
Date: 26 Aug 92 08:49:20 GMT

markh@csd4.csd.uwm.edu (Mark) writes:

>[ tree traversal code deleted]

Oops, I forgot to say one thing in my last posting.
Your code applies to trees that are explicitly stored and can thus
hold the information that would be on the stack in the case of recursion.
In the case of trees that are not explicitly stored, which is usual for
alpha-beta search of game trees, there is no such possibility, and the
stack is then the only natural place to store it.
Anyway, thanks for the code!

regards,
-John
From: jwl8k@palm.cs.Virginia.EDU (Joseph W. Lavinus)
Newsgroups: comp.programming
Subject: Re: miranda
Date: 4 Sep 92 11:24:43 GMT
Organization: University of Virginia Computer Science Department

In article <1992Sep4.020022.9186@wuecl.wustl.edu> ppc1@cec1.wustl.edu (Peter Pui Tak Chiu) writes:
>can anyone tell me where i can get miranda (a functional programming language)
>through anonymous ftp?

You can't.  Miranda is a commercial product.  However, unless you have a
reason that you specifically need Miranda, there are other good purely
functional languages around: Haskell (nebula.cs.yale.edu) and LML
(research.att.com) [LML isn't *purely* functional, but it's close].

I recommend Haskell.

Joe

-- 
______________________________________________________________________________
 Joseph W. Lavinus, University of Virginia          email: jwl8k@virginia.edu
        "Few NP-hard problems remain difficult when restricted, say,
           to the class of 1-vertex graphs." --- David S. Johnson
From: dougm@titan.cs.rice.edu (Doug Moore)
Newsgroups: comp.programming
Subject: Re: How to decide if a point is inside a polygon?
Date: 29 Aug 1992 05:26:51 GMT
	<1992Aug27.153902@is.morgan.com> <schnitzi.715017774@eola.cs.ucf.edu>
	<1992Aug28.134203@is.morgan.com> <schnitzi.715032142@eola.cs.ucf.edu>
	<thompson.715056569@malthus.econ.umn.edu>
Organization: Rice University Computer Science, Houston, Texas

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?

This is not hard to solve.  From the point, extend a ray infinitely
far in the +x direction.  Count a side of the polygon if it intersects
the ray with one of its endpoints strictly below the ray and the other
on-or-above the ray.  If the ray hits a vertex and both sides
containing that vertex are below the ray, both are counted.  If both
sides are above, neither is counted.  If one is above and one is
below, exactly one is counted.  If the segment lies on the ray, it is
not counted.

This algorithm is O(n), for an n-sided polygon.  With O(n)
preprocessing, inside/outside queries can be answered in O(log n) time
per query.

Doug Moore
(dougm@cs.rice.edu)
Newsgroups: comp.programming
From: tsmaster@media.mit.edu (David LeCompte)
Subject: Re: Teaching by Value (was Re: Teaching the Basics)
Organization: MIT Media Laboratory
Date: Wed, 26 Aug 1992 15:55:57 GMT

In article <1992Aug26.105222.8034@ITcorp.com> geoff@ITcorp.com (Geoff Kuenning) writes:
>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 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.)

I took a very similar class, and our prof. told us up front that there
was going to be a feature that we would have to add to our project. It
would be announced sometime before the project was due. I don't recall
if the date that the surprise feature would be announced was announced,
but I think that it shouldn't have been.

(As it turns out, we were writing a game, and the feature was UNDO,
which my group had already implemented.)

			-David LeCompte
-- 
Your Mom!       The Carburator!         |I'm not paid to HAVE opinions.
Your Shoes!     A gardenhose!           |
You got to got to got to got to ...     |This sig can be yours; send $15 to
SCUD MISSILE!!!	-"Scud Missile", Grunge |tsmaster@athena.mit.edu
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.programming
Subject: Re: Teaching the basics
Date: 26 Aug 92 10:56:56 GMT
Organization: Comp Sci, RMIT, Melbourne, Australia

In article <7116@charon.cwi.nl>, tromp@cwi.nl (John Tromp) writes:
> mjn@pseudo.uucp (Murray Nesbitt) writes:
> >markh@csd4.csd.uwm.edu (Hunk) writes:
> >>In article <14066@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:
> >>I think recursion is a farce.  And just to rub it in, here's the Towers of
> >>Hanoi (up to N = 31, I'm assuming long integers are 32 bits) without it (in C)

> Ok, maybe Richard meant something like this:

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);
> }
> 
<some one else>
> >Beauty is in the eye of the beholder, but in my opinion the recursive
> >version is a little easier to follow, to say the least.
> 
> Hmmm, guess I'll have to agree to that:-)
> But efficient it's not, particularly in its use of (stack) space.

The recursive version of Towers of Hanoi for N disks takes o(N) stack
frames; a typical stack frame (assuming a good compiler) would be two or
three words of memory.  Using ~2N words of memory for a program that takes
O(2**N) time doesn't strike _me_ as grossly inefficient.

From my perspective (heavily influenced by Lisp/Scheme/T, NPL/Hope/ML,
Prolog, and similar languages), the only differences between C's "for"
and Scheme's "named-LET" are (a) punctuation & spelling and (b) C's
"for" loop is less expressive for iterations that Scheme's nominally
recursive (but actually iterative) notation.

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

-- 
You can lie with statistics ... but not to a statistician.
Newsgroups: comp.programming
From: geoff@ITcorp.com (Geoff Kuenning)
Subject: Re: Teaching the basics
Organization: Interrupt Technology Corporation, Manhattan Beach, CA
Date: Wed, 26 Aug 92 11:12:40 GMT

> typedef struct Tree *Tree;
> struct Tree {
>    char *S; int Key, State;
>...
>    Cur->Key = Key, Cur->State = 0;
>...
>    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.

Code like this would be grounds for censure at most established,
respected companies that care about customer support (insert your
favorite quality software supplier here).  This stuff will only fly at
the 2-person shops founded by hackers who slapped together a
barely-working system and shipped it as soon as possible, before they
could find any bugs.

Kids, don't try this kind of stuff at home.  Like I've always told my
students, whitespace is free.  Use it liberally.
-- 
	Geoff Kuenning   geoff@ITcorp.com   uunet!desint!geoff
Newsgroups: comp.programming
From: neuhaus@vier.informatik.uni-kl.de (Stephan Neuhaus (HiWi Mattern))
Subject: Re: Balanced Trees (Re: Why Are Red-Black Trees Obscure?)
Organization: University of Kaiserslautern, Germany
Date: Fri, 28 Aug 1992 13:04:21 GMT

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.

The main data structure was a trie, with the brethren linked together
in a linked list.  The linked lists were about 20--30 elements long,
and the trie was 8--10 levels deep. I have tried both common forms of
self-organizing lists in my program, with roughly the same speedup
compared to unorganized or sorted lists:

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.

The probability distribution for my keys was such that I rarely needed
more than one pointer traversal per list to find the proper element.
With sorted lists, the situation became more complex and hard to
analyze, since the relative ordering of a particular item in a list
was not connected to its frequency in retrievals.  Anyway, I managed
to get a speedup by a factor of 15 (roughly) for shallow tries.

Observation: The longer the lists, the more speedup was obtained.
This is quite natural when you think about it for a minute.

The probability distribution of my keys was roughly exponential, i.e.,
in a list sorted by frequency of access, item i+1 was p% less likely
to appear in a retrieval operation than item i, where p is independent
of i.

Have fun.
-- 
Stephan <neuhaus@informatik.uni-kl.de>
sig closed for inventory.  Please leave your pickaxe outside.
Newsgroups: comp.programming
From: johnm@cory.Berkeley.EDU (John D. Mitchell)
Subject: Re: Balanced Trees (Re: Why Are Red-Black Trees Obscure?)
Organization: University of California, at Berkeley
Date: Fri, 28 Aug 1992 00:58:49 GMT

In article <1992Aug27.215924.24525@reed.edu> orpheus@reed.edu (P. Hawthorne) writes:
>  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?
[...]
>  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!

Nope.  AVL, splay and red-black trees are *not* probabilistic.  Skip-lists
are probabilistic.

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

That's what 'splaying' is for.

John D. Mitchell
johnm@cory.Berkeley.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 22:48:41 GMT
Organization: fsl

From article <1992Aug27.210308.9621@aw2.fsl.ca.boeing.com>, by gcr8829@aw2.fsl.ca.boeing.com (Gustav C. Rettke):
> 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                  Correction, that should be lines
>                                           of constant y.
> 	  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: bkottmann@falcon.aamrl.wpafb.af.mil (Brett Kottmann)
Newsgroups: comp.programming
Subject: Re: Indentation/brackets
Date: 27 Aug 92 14:21:58 EST
Followup-To: alt.folklore.computers
Organization: Logicon Technical Services, Inc.

In article <1606@anagld.analytics.com>, sammy@anagld.analytics.com (Sam Blackburn) writes:
...
> I wrote the coding standards for my current project and they are pretty strict
> by most programmers values.  TABS ARE ILLEGAL!  Since we've outlawed them all
> source code looks identical on all editors.
> 
> Since our software was meant to be maintained by other programmers (as all
> software should be) we came up with some pretty basic rules like:
> 
> Open and close braces are MANDATORY:
> Illegal: if ( x != 0 ) x++;
> Legal: if ( x != 0 )
>        {
>           x++;
>        }

	Excellent!  This becomes second nature after a while.  It *eliminates*
the else-without-bracket errors and makes the code more readable.
	Except you should indent the brackets to match the code... :)

> Abbreviating variable names is discouraged.
> Illegal: ce = 1;
> Legal: communications_error = 1;
> 
> Again, these rules are meant to produce code that will be maintainable for
> years to come.  Maintenance programmers spend way too much time figuring out
> what variable names really mean or what the original programmer was TRYING to
> do.  Programmers all too often code like e.e.cummings wrote poetry.  If you
> have to figure out the meaning of a line of code then it is wasted time (from
> a financial point of view).  CODE SHOULD BE WRITTEN TO BE MAINTAINED!

	100% agreement.

	This should also be taught in college!!

Brett--------------------------------------------------------------------------
	"Why the courts don't tell a husband who has been living off his wife
to go out and get a job is beyond my comprehension."--Joan Lunden
-------------------------------------------------------------------------------
Newsgroups: comp.programming
From: zgma04@trc.amoco.com (Guy M. Argo)
Subject: Re: miranda
Organization: Amoco Production Company, Tulsa Research
X-Checksum-Snefru: b40c460f fad9703d 7888f056 7229ca8d
Date: Fri, 4 Sep 1992 14:04:21 GMT

In article <1992Sep4.112443.9047@murdoch.acc.Virginia.EDU> jwl8k@palm.cs.Virginia.EDU (Joseph W. Lavinus) writes:
>In article <1992Sep4.020022.9186@wuecl.wustl.edu> ppc1@cec1.wustl.edu (Peter Pui Tak Chiu) writes:
>>can anyone tell me where i can get miranda (a functional programming language)
>>through anonymous ftp?
>
>You can't.  Miranda is a commercial product.  However, unless you have a
>reason that you specifically need Miranda, there are other good purely
>functional languages around: Haskell (nebula.cs.yale.edu) and LML
>(research.att.com) [LML isn't *purely* functional, but it's close].
>
>I recommend Haskell.
>
>Joe
>
>-- 
>______________________________________________________________________________
> Joseph W. Lavinus, University of Virginia          email: jwl8k@virginia.edu
>        "Few NP-hard problems remain difficult when restricted, say,
>           to the class of 1-vertex graphs." --- David S. Johnson



        I wouldn't under any circumstances recommend Miranda - it's
        expensive and 20 times slower than the public domain functional
        programming languages. It's only redeeming feature is a syntax
        which is aesthetically pleasing to the mathematically-inclined.

        LML is a pure functional language and has nothing to do with
        att.research.com - I believe the poster is confusing it with
        SML which is an impure strict functional language.

        You can get LML and Haskell by anonymous ftp from animal.chalmers.se
        The LML implementation has been under development for 5-10 years
        so it's efficient and very robust. The Haskell implementation
        is a different front-end to the same compiler.
                                Guy


-- 
E-mail:	zgma04@trc.amoco.com		Phone: +44 (918) 660 3398
S-mail:	Guy Argo, Amoco Production Company, Tulsa Research Center, 4502 East 41st Street, P.O. Box 3385, Tulsa OK 74102.

	"He sure looks like plant food to me", Audrey II, LSOH
Newsgroups: comp.programming
From: ceblair@ux1.cso.uiuc.edu (Charles Blair)
Subject: Re: Spell checking routine
Organization: University of Illinois at Urbana
Date: Thu, 3 Sep 1992 01:54:14 GMT

   I think this is discussed in Bentley's MORE PROGRAMMING PEARLS
Newsgroups: comp.programming
From: mchung@ee.tamu.edu (Maranatha Chung)
Subject: Why?
Organization: Texas A&M University
Distribution: usa
Date: Tue, 1 Sep 1992 17:27:59 GMT

Hi, I have a question here may be some of you may know the answer.
I am working on s Sun SPARCstation 1.
I was compiling a C program with some Fortran subroutines. I compile
the files individually using the UNIX make utility and I got the
following message:

cc -O3 -o fgui <some *.o files> <some paths for libraries>
ld: Undefined symbol
   _MAIN_
*** Error code 2
make: Fatal error: Command failed for target 'fgui'

Despite of the error message, the executable is created and is running
perfectly OK. I wonder why there is such a message and how to fix it?

Thanks in advance. Private email welcomed.

Maranatha
mchung@ee.tamu.edu
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:35:26 GMT
X-News-Reader: VMS NEWS 1.23

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

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
-- 
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?
One frequently hears horror expressed that a 2M byte machine may have 400K
 devoted to its operating system. - Fred Brooks (1975)
Newsgroups: comp.programming