Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #164733

on legal definitions of a certain algorithm (Was: Re: **********@b*****.uk)

Show all headers | View raw

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

> Richard Damon <Richard@Damon-Family.org> writes:
>> On 1/23/22 10:48 AM, Kaz Kylheku wrote:

[...]

>>> Your teacher is an ignoramus, or else you are trolling.
>>>
>>> The above termination test is part of the definition of Bubble Sort.
>>>
>>> https://en.wikipedia.org/wiki/Bubble_sort
>>
>> To my knowledge, there is no official legal definition of Bubble
>> Sort.  

[...]

> I agree on all points.  Any algorithm that does repeated swapping
> scans may reasonably be called a bubble sort, even the horribly
> naive algorithm that starts again from the bottom whenver an out
> of order pair is found (and so typically has O( n*n*n ) runtime).

[...]

This thread is reminding me of an event I went through once.  I took a
data structures course once and there was a written test that asked me
to sort a list of numbers using quicksort.  The question was totally
vague like that.  Sort [a, b, c, d, e] using quicksort.

How did I do it?  First I determined that I was going to use a random
number generator that was myself --- I chose the pivot-elements so as to
keep the number of iterations in the algorithm smallest.  (I thought I
was being elegant that way.)  Then using a functional implementation of
quicksort in my head --- my favorite ones --- I explained the steps I
took and how the list was sorted.

I was marked completely off because what I was using ``was not
quicksort''.  Then the question became what is quicksort.  Effectively
the teacher claimed quicksort is some imperative implementation of the
method that runs in O(n log n) on the average case.  (No publication was
offered to back up this claim.)

Upon the teacher's own request, I uselessly showed him various important
publications that called various versions of quicksort as ``quicksort''
--- all of which were totally compatiable with my step by step
illustration of how I sorted the list showed on the test --- without any
sort of footnote-remark to the effect that they were abusing language or
something like that.  (Also by his own request, I implemented in the C
language the version I described on the test.  For the curious, no, I
did not get any points for the question, despite showing how I could
implemented the strategy in more than one way in the language
requested.)

I came out of that experience with the conclusion that one cannot
identify an algorithm with a runtime class.  A functional language is
able to imitate an imperative one with a maximum loss of O(ln n) steps.
For example, given an algorithm that runs in O(n) time, the same
algorithm can be implemented in a functional machine in time O(n ln n).
That's theorem 3.1 of the following paper.

--8<---------------cut here---------------start------------->8---
Nicholas Pippenger. “Pure versus impure Lisp”. Em: ACM Transactions on
Programming Languages and Systems (TOPLAS) 19.2 (1997), pp. 223–238.
--8<---------------cut here---------------end--------------->8---

In the context of where we were --- English-language descriptions of
algorithms ---, there was no possibility for the distinction of
algorithms by way of their expressions.  Not even the typical
programming language is able to do that, much less English.  The paper
below makes that point.

--8<---------------cut here---------------start------------->8---
Andreas Blass, Nachum Dershowitz e Yuri Gurevich. “When are two
algorithms the same?”  Em: Bulletin of Symbolic Logic 15.2 (2009),
pp. 145–168.
--8<---------------cut here---------------end--------------->8---

I'll appreciate hearing what you guys have to say about any of this.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

ben.usenet@bsb.me.uk Arslan RK <itsarslanfiverr@gmail.com> - 2022-01-17 10:08 -0800
  Re: ben.usenet@bsb.me.uk scott@slp53.sl.home (Scott Lurndal) - 2022-01-17 18:15 +0000
  Re: ben.usenet@bsb.me.uk Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2022-01-17 18:24 +0000
  Re: ben.usenet@bsb.me.uk Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-01-17 10:45 -0800
  Re: ben.usenet@bsb.me.uk Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-17 20:43 +0000
    Re: ben.usenet@bsb.me.uk "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2022-01-17 14:03 -0800
  Re: **********@b*****.uk Kaz Kylheku <480-992-1380@kylheku.com> - 2022-01-23 15:48 +0000
    Re: **********@b*****.uk Richard Damon <Richard@Damon-Family.org> - 2022-01-23 13:13 -0500
      Re: **********@b*****.uk Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-23 19:10 -0800
        on legal definitions of a certain algorithm (Was: Re: **********@b*****.uk) Meredith Montgomery <mmontgomery@levado.to> - 2022-01-30 10:00 -0300
          Re: on legal definitions of a certain algorithm Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-30 21:34 +0000
            Re: on legal definitions of a certain algorithm Meredith Montgomery <mmontgomery@levado.to> - 2022-01-30 23:34 -0300
              Re: on legal definitions of a certain algorithm Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-30 20:58 -0800
              Re: on legal definitions of a certain algorithm Meredith Montgomery <mmontgomery@levado.to> - 2022-02-02 11:10 -0300
          Re: on legal definitions of a certain algorithm Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-30 21:04 -0800
    Re: **********@b*****.uk Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-01-23 11:15 -0800
      This newsgroup (Was: for some totally inexplicable reason, **********@b*****.uk) gazelle@shell.xmission.com (Kenny McCormack) - 2022-01-23 20:09 +0000

csiph-web