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

Groups > comp.lang.c > #402780 > unrolled thread

AVL tree insertion - programming exercise

Back to article view | Back to comp.lang.c

Contents

  AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-06 23:08 -0700
    Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-07 15:25 +0200
      Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-07 12:13 -0700
        Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-07 21:28 +0200
          Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-08 05:31 -0700
            Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-09 11:12 +0200
              Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-09 11:12 +0200
        Re: AVL tree insertion - programming exercise BGB <cr88192@gmail.com> - 2026-10-07 20:10 -0500
          Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-08 05:56 -0700
            Re: AVL tree insertion - programming exercise BGB <cr88192@gmail.com> - 2026-10-08 15:09 -0500
              Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-08 22:56 +0200
                Re: AVL tree insertion - programming exercise BGB <cr88192@gmail.com> - 2026-10-08 17:29 -0500
                  Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-09 09:56 +0200
              Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-09 01:39 +0200
                Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-09 00:03 -0700
              Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-08 23:53 -0700
                Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 10:34 +0200
                  Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-09 12:27 +0200
                    Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 12:59 +0200
                  Re: AVL tree insertion - programming exercise bart <bc@freeuk.com> - 2026-10-09 11:43 +0100
                    Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 13:20 +0200
                      Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-09 12:38 +0000
                        Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 16:05 +0200
                          Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-09 17:54 +0200
                            Re: AVL tree insertion - programming exercise Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-10-10 10:38 +0800
                              Re: AVL tree insertion - programming exercise ram@zedat.fu-berlin.de (Stefan Ram) - 2026-10-10 03:12 +0000
                                Re: AVL tree insertion - programming exercise Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-10-10 04:44 +0000
                                  Re: AVL tree insertion - programming exercise "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-10-10 14:12 -0700
                          Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-09 19:48 +0000
                            Re: AVL tree insertion - programming exercise scott@slp53.sl.home (Scott Lurndal) - 2026-10-09 23:18 +0000
                            Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-10 15:27 +0200
                        Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-09 17:47 +0300
                          Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-09 16:48 +0000
                            Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 19:08 +0300
                              Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-10 18:29 +0200
                                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 17:44 +0000
                                  Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-10 23:22 +0200
                              Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 17:43 +0000
                              Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-10 20:35 +0200
                                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 19:36 +0000
                                  Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-10 22:08 +0200
                                  Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 23:21 +0300
                                    Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 20:55 +0000
                              Re: AVL tree insertion - programming exercise scott@slp53.sl.home (Scott Lurndal) - 2026-10-10 20:22 +0000
                                Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 23:32 +0300
    Re: AVL tree insertion - programming exercise Bonita Montero <Bonita.Montero@gmail.com> - 2026-10-10 19:40 +0200
    Re: AVL tree insertion - programming exercise Andrey Tarasevich <noone@noone.net> - 2026-10-10 12:39 -0700
      Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 23:00 +0300
      Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-10 22:28 +0200
      Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-10 19:02 -0700

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#402849

On 09/10/2026 12:43, bart wrote:
> On 09/10/2026 09:34, David Brown wrote:

>> And like "The C Programming Language", it suffers from age - you can't 
>> learn modern C from a 50 year old book, and you can't learn modern 
>> coding from a 60 year old book.
> 
> When I first looked at it wasn't quite that old!

I have the second edition from 1972 - the first edition was published in 
1968, but started in 1962.  I believe it would have been 1991 when I 
bought my copy - it was considered old-fashioned by then and not usable 
as course textbook.  But having won a bookshop voucher as an academic 
prize, it seemed appropriate to spend some on the nearest computer 
science has to a bible.  (I think I also bought a complete Shakespeare, 
which I still have, and from which I have actually read three or four 
plays.)

> 
>> Far and away the biggest mistake of the books - IMHO - is the use of a 
>> mythical assembly as the language for the programs instead of a high- 
>> level pseudo-code that made the interesting stuff clear instead of 
>> bogging it down in irrelevant detail.
> 
> This 'MIX' language was something that astonished me even then. Not only 
> was it assembly that would totally obscure whatever algorithm was being 
> expressed, but it was a weird made-up assembly with unusual byte and 
> word sizes.

Indeed.  When I first saw it, I was familiar with several 8-bit 
assemblies (6502, Z80, 8085) and some 32-bit ARM assembly, and had read 
books on the 68000 family and MIPS.  MIX was, to me, absurd.  To be 
fair, the computer world was not nearly as consolidated in 1962, but I'm 
sure it looked fairly odd even by the standards of the time.

> I understand that more recent editions use an updated 'MMIX' language: 
> now the registers are 64 bits, and there's a lot more of them. This is 
> still like publishing a book of algorithms using ARM64 assembly to 
> express them.

Yes, this strikes me as even more absurd.  It's just re-doing the 
previous mistake in a slightly less bad way.

> 
> It's not clear what he had against HLLs; perhaps he thought an actual 
> HLL would soon be superseded? Then pseudo-code should have been used.

Real HLL's were around at the time - FORTRAN and ALGOL, or possibly 
LISP, would have been appropriate choices in the days before small 
letters were invented.  Or he could have made a simple HLL pseudo-code 
for the purpose - things like unlimited sized integers and unlimited 
memory sizes would have made sense.

[toc] | [prev] | [next] | [standalone]

#402850

In article <11aaimc$n0f0$2@dont-email.me>,
David Brown  <david.brown@hesbynett.no> wrote:
>On 09/10/2026 12:43, bart wrote:
>> [snip]
>> This 'MIX' language was something that astonished me even then. Not only 
>> was it assembly that would totally obscure whatever algorithm was being 
>> expressed, but it was a weird made-up assembly with unusual byte and 
>> word sizes.
>
>Indeed.  When I first saw it, I was familiar with several 8-bit 
>assemblies (6502, Z80, 8085) and some 32-bit ARM assembly, and had read 
>books on the 68000 family and MIPS.  MIX was, to me, absurd.  To be 
>fair, the computer world was not nearly as consolidated in 1962, but I'm 
>sure it looked fairly odd even by the standards of the time.

If one were coming from the world of early 1960s mainframes, it
would perhaps be less astonishing.

>> I understand that more recent editions use an updated 'MMIX' language: 
>> now the registers are 64 bits, and there's a lot more of them. This is 
>> still like publishing a book of algorithms using ARM64 assembly to 
>> express them.
>
>Yes, this strikes me as even more absurd.  It's just re-doing the 
>previous mistake in a slightly less bad way.

Unfortunately, he is quite adamant about this.  He truly
believes that the best way to understand how an algorithm works
on a computer is to see it at the instruction level.

>> It's not clear what he had against HLLs; perhaps he thought an actual 
>> HLL would soon be superseded? Then pseudo-code should have been used.
>
>Real HLL's were around at the time - FORTRAN and ALGOL, or possibly 
>LISP, would have been appropriate choices in the days before small 
>letters were invented.  Or he could have made a simple HLL pseudo-code 
>for the purpose - things like unlimited sized integers and unlimited 
>memory sizes would have made sense.

The criticism of TAOCP is valid.  It is not a book for workaday
programmers; it is an academic reference.  The real value is in
the mathematical treatment and historical/bibliographic notes,
not the presentation of code in assembler.

Other books exist that are better references for most people;
certainly for most programmers:

* "Introduction to Algorithms" by Cormen, Leiserson, Rivest,
  and Stein is a standard.
* Sedgewick's books in C, simply titled, "Algorithms" are pretty
  good, though his code style is slightly idiosyncratic.  Now in
  its 4th Edition, he has switched to Java and taken on a
  coauthor (Kevin Wayne).
* "Algorithms", by Dasgupta, Papadimitriou, and Vazirani is a
  wonderful book that, I think, strikes a nice balance between
  formality and utility.
* I am rather partial to Skiena's work, "The Algorithm Design
  Manual."
* "Data Structures and Their Algorithms" by Lewis and Denenberg
  is a bit dated, but very accessible; examples are presented in
  a Pascal-like pseudocode.
* "Data Structures and Algorithms" by Aho, Hopcroft, and Ullman
  is a nice book.  Be careful not to confuse it with Aho and
  Ullman's, "The Design and Analysis of Computer Algorithms",
  however; the latter is far denser and intended for academics
  studying the fundamental properties of algorithms.
* "Algorithms + Data Structures = Programs" and the later
  revision, "Algorithms & Data Structures", by Wirth, are
  similarly dated, but still very nice.
* "Purely Functional Data Structures", by Okasaki; I include
  this just because I think that it is fun.

Of course, more specialized texts exist for specific problem
domains, programming paradigms, etc; books on string algorithms,
mutual exclusion protocols for concurrent programs, etc, are all
available, though not general.

Did Knuth err using MIX and then MMIX for TAOCP?  Perhaps; I do
think that neither Fortran nor Lisp would have been appropriate
choices; Algol perhaps.  Other authors around that time or
slightly later either adopt a more mathematics-inspired
pseudonotation (Dijkstra; Hoare) algolish pseudo-code (Aho et
al), or a language of their own design (Wirth).

Knuth is a wonderful object of study, but I do not recommend it.

	- Dan C.

[toc] | [prev] | [next] | [standalone]

#402852

On 09/10/2026 14:38, Dan Cross wrote:
> In article <11aaimc$n0f0$2@dont-email.me>,
> David Brown  <david.brown@hesbynett.no> wrote:
>> On 09/10/2026 12:43, bart wrote:
>>> [snip]
>>> This 'MIX' language was something that astonished me even then. Not only
>>> was it assembly that would totally obscure whatever algorithm was being
>>> expressed, but it was a weird made-up assembly with unusual byte and
>>> word sizes.
>>
>> Indeed.  When I first saw it, I was familiar with several 8-bit
>> assemblies (6502, Z80, 8085) and some 32-bit ARM assembly, and had read
>> books on the 68000 family and MIPS.  MIX was, to me, absurd.  To be
>> fair, the computer world was not nearly as consolidated in 1962, but I'm
>> sure it looked fairly odd even by the standards of the time.
> 
> If one were coming from the world of early 1960s mainframes, it
> would perhaps be less astonishing.

It would undoubtedly have been less astonishing in 1968 (when the first 
book was published) than in 1991 (when I first saw it), but I would have 
thought that even people familiar with 1960's mainframes would see it as 
strange to use a limited and highly specific artificial assembly that 
matched poorly with existing systems.  I am sure people were already 
familiar with the pain of converting code written in assembly for one 
system into assembly for a very different system - the only advantage of 
the MIX code was that it was equally useless to everyone, and favoured 
no one!

> 
>>> I understand that more recent editions use an updated 'MMIX' language:
>>> now the registers are 64 bits, and there's a lot more of them. This is
>>> still like publishing a book of algorithms using ARM64 assembly to
>>> express them.
>>
>> Yes, this strikes me as even more absurd.  It's just re-doing the
>> previous mistake in a slightly less bad way.
> 
> Unfortunately, he is quite adamant about this.  He truly
> believes that the best way to understand how an algorithm works
> on a computer is to see it at the instruction level.
> 

Then he could easily have invented a machine that is powerful enough for 
the details not to matter, and not need describing.  The number and size 
of registers should not matter in any way for understanding algorithms.

>>> It's not clear what he had against HLLs; perhaps he thought an actual
>>> HLL would soon be superseded? Then pseudo-code should have been used.
>>
>> Real HLL's were around at the time - FORTRAN and ALGOL, or possibly
>> LISP, would have been appropriate choices in the days before small
>> letters were invented.  Or he could have made a simple HLL pseudo-code
>> for the purpose - things like unlimited sized integers and unlimited
>> memory sizes would have made sense.
> 
> The criticism of TAOCP is valid.  It is not a book for workaday
> programmers; it is an academic reference.  The real value is in
> the mathematical treatment and historical/bibliographic notes,
> not the presentation of code in assembler.

Agreed.

> 
> Other books exist that are better references for most people;
> certainly for most programmers:
> 
> * "Introduction to Algorithms" by Cormen, Leiserson, Rivest,
>    and Stein is a standard.
> * Sedgewick's books in C, simply titled, "Algorithms" are pretty
>    good, though his code style is slightly idiosyncratic.  Now in
>    its 4th Edition, he has switched to Java and taken on a
>    coauthor (Kevin Wayne).
> * "Algorithms", by Dasgupta, Papadimitriou, and Vazirani is a
>    wonderful book that, I think, strikes a nice balance between
>    formality and utility.
> * I am rather partial to Skiena's work, "The Algorithm Design
>    Manual."
> * "Data Structures and Their Algorithms" by Lewis and Denenberg
>    is a bit dated, but very accessible; examples are presented in
>    a Pascal-like pseudocode.
> * "Data Structures and Algorithms" by Aho, Hopcroft, and Ullman
>    is a nice book.  Be careful not to confuse it with Aho and
>    Ullman's, "The Design and Analysis of Computer Algorithms",
>    however; the latter is far denser and intended for academics
>    studying the fundamental properties of algorithms.
> * "Algorithms + Data Structures = Programs" and the later
>    revision, "Algorithms & Data Structures", by Wirth, are
>    similarly dated, but still very nice.
> * "Purely Functional Data Structures", by Okasaki; I include
>    this just because I think that it is fun.
> 

My bookshelves are too scattered for me to easily see what I have.  But 
I am not convinced that books are good references at all these days, for 
most purposes.  They are, however, still good for study if you are doing 
courses or really learning a subject.

> Of course, more specialized texts exist for specific problem
> domains, programming paradigms, etc; books on string algorithms,
> mutual exclusion protocols for concurrent programs, etc, are all
> available, though not general.

Yes.

> 
> Did Knuth err using MIX and then MMIX for TAOCP?  Perhaps; I do
> think that neither Fortran nor Lisp would have been appropriate
> choices; Algol perhaps.  Other authors around that time or
> slightly later either adopt a more mathematics-inspired
> pseudonotation (Dijkstra; Hoare) algolish pseudo-code (Aho et
> al), or a language of their own design (Wirth).
> 

As Hoare was the head of department when I was at university, and 
therefore very influential in how we were taught, I am of course partial 
to his style of notation and think that would have been the best choice!

> Knuth is a wonderful object of study, but I do not recommend it.
> 

Agreed.

[toc] | [prev] | [next] | [standalone]

#402855

On 2026-10-09 16:05, David Brown wrote:
> On 09/10/2026 14:38, Dan Cross wrote:
>> In article <11aaimc$n0f0$2@dont-email.me>,
>> David Brown  <david.brown@hesbynett.no> wrote:
>>> On 09/10/2026 12:43, bart wrote:
>>>> [snip]
>>>> This 'MIX' language was something that astonished me even then. Not 
>>>> only
>>>> was it assembly that would totally obscure whatever algorithm was being
>>>> expressed, but it was a weird made-up assembly with unusual byte and
>>>> word sizes.
>>>
>>> Indeed.  When I first saw it, I was familiar with several 8-bit
>>> assemblies (6502, Z80, 8085) and some 32-bit ARM assembly, and had read
>>> books on the 68000 family and MIPS.  MIX was, to me, absurd.  To be
>>> fair, the computer world was not nearly as consolidated in 1962, but I'm
>>> sure it looked fairly odd even by the standards of the time.
>>
>> If one were coming from the world of early 1960s mainframes, it
>> would perhaps be less astonishing.
> 
> It would undoubtedly have been less astonishing in 1968 (when the first 
> book was published) than in 1991 (when I first saw it), but I would have 
> thought that even people familiar with 1960's mainframes would see it as 
> strange to use a limited and highly specific artificial assembly that 
> matched poorly with existing systems.  I am sure people were already 
> familiar with the pain of converting code written in assembly for one 
> system into assembly for a very different system - the only advantage of 
> the MIX code was that it was equally useless to everyone, and favoured 
> no one!

I have no recollection on MIX. (Never engaged with it.)

Incidentally, our own folks had an own set of abstract machines
and respective machine languages (M1, M2, M3). (I'm not sure who
actually invented them; I associated G. Seegmüller with those.)

But their purpose was to teach system programming, and to teach
about the (back these days) typical CPU addressing facilities,
and about their utility to support HLLs.

I think it makes sense to learn these things, the concepts, not
on any specific commercial assembly language but on an abstract
machine. YMMV.

Using some hypothetical assembly to learn programming complex
algorithms might be useful for case studies, but I think it's
otherwise not a good idea. Our teachers uphold all due respect
but clearly suggested more sensible representations.

To represent high-level algorithms a clear notation is sensible,
ideally without any ballast; it need not even be an existing HLL.

Janis

> [...]

[toc] | [prev] | [next] | [standalone]

#402869

On 10/9/2026 11:54 PM, Janis Papanagnou wrote:
> Using some hypothetical assembly to learn programming complex
> algorithms might be useful for case studies, but I think it's
> otherwise not a good idea. Our teachers uphold all due respect
> but clearly suggested more sensible representations.
> 
> To represent high-level algorithms a clear notation is sensible,
> ideally without any ballast; it need not even be an existing HLL.

That's what several books an algorithms do, including the venerable
C.L.R.S., which I admit not to have read yet, but keep a copy on my
shelf due to a recommendation.  After all, it isn't Sedgewick, and the
coverage is different.

On Knuth, I forgot why he chose assembly language, but in the times he
first started to write, that was the normal programming language of the
day.  Just, there were a lot more varieties out there, than today.  Now-
adays, you get by with x86, amd64, ARM, and Aaarch64, SPIM compatible
cores in 32 and 64bit varieties, and the RISC-V variants.

Really, nothing worth worrying about, and it's reasonable to expect any
proficient programmer is fluent in any or all of these.  I myself lack
knowledge of the ARMatures, but dabble with the rest.  At least, so far,
I do have plans to dabble with an Aarch64 in the near-ish future.

Other programmers have chosen a specific real world programming language
to teach algorithms, and not just generally like C.L.R.S. and Sedgewick,
but Mailund chose C for his /String Algorithms in C/ book, and /The Joys
of Hashing/; then most game programming books have used C++.

I personally like to learn this stuff in the concrete, rather than some
abstract representation, and a lot of books from ages past were written
in C -- only worth mentioning because we're talking about this stuff in
comp.lang.c -- though nowadays it's Python, Java, Rust, C#, C++, Common
Lisp, -- yes, I believe I mentioned that book before -- and even OCaml
if we count /Handbook of Practical Logic and Automated Reasoning/ (2009)
by John Harrison as worthy of a shelf space.  Then I have books in ML,
Pascal, Ada, and Modula-2.  Those hardly ever show up as something
written this century, so don't need to be studied by a student of the
art.

Personally, I'm not sure what I'd write in -- meaning the programming
language -- if I were to write a book on the craft today, so let's just
see if I publish something in the near-ish future.


Best wishes, and happy writing books on the craft!
-- 
Johann | email: invalid -> com | http://www.myrkraverk.com/blog/
I'm not from the Internet, I just work there. | via Easynews.com
https://bsky.app/profile/myrkraverk.bsky.social | for ( ;; ) _:;
Federated at https://fed.brid.gy/bsky/myrkraverk.bsky.social

[toc] | [prev] | [next] | [standalone]

#402870

Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> wrote or quoted:
>On Knuth, I forgot why he chose assembly language

  Assembly language is more readable. For example,

LDA $3120,X

  is more readable than

BD 20 31

  .

[toc] | [prev] | [next] | [standalone]

#402871

On 10 Oct 2026 03:12:37 GMT, Stefan Ram wrote:

> Assembly language is more readable. For example,
>
>   LDA $3120,X
>
> is more readable than
>
>   BD 20 31
>
> .

All the best CPUs disagree.

“Puny humans! We spit on your weak computational capabilities!”

[toc] | [prev] | [next] | [standalone]

#402910

On 10/9/2026 9:44 PM, Lawrence D’Oliveiro wrote:
> On 10 Oct 2026 03:12:37 GMT, Stefan Ram wrote:
> 
>> Assembly language is more readable. For example,
>>
>>    LDA $3120,X
>>
>> is more readable than
>>
>>    BD 20 31
>>
>> .
> 
> All the best CPUs disagree.
> 
> “Puny humans! We spit on your weak computational capabilities!”

Fwiw, check this out when you get some free time to burn:

(Making an SNES Game the Way Nintendo Intended)
https://youtu.be/kYLJLJkVfLk

[toc] | [prev] | [next] | [standalone]

#402858

In article <11aasbg$r60s$1@dont-email.me>,
David Brown  <david.brown@hesbynett.no> wrote:
>On 09/10/2026 14:38, Dan Cross wrote:
>> In article <11aaimc$n0f0$2@dont-email.me>,
>> David Brown  <david.brown@hesbynett.no> wrote:
>>> On 09/10/2026 12:43, bart wrote:
>>>> [snip]
>>>> This 'MIX' language was something that astonished me even then. Not only
>>>> was it assembly that would totally obscure whatever algorithm was being
>>>> expressed, but it was a weird made-up assembly with unusual byte and
>>>> word sizes.
>>>
>>> Indeed.  When I first saw it, I was familiar with several 8-bit
>>> assemblies (6502, Z80, 8085) and some 32-bit ARM assembly, and had read
>>> books on the 68000 family and MIPS.  MIX was, to me, absurd.  To be
>>> fair, the computer world was not nearly as consolidated in 1962, but I'm
>>> sure it looked fairly odd even by the standards of the time.
>> 
>> If one were coming from the world of early 1960s mainframes, it
>> would perhaps be less astonishing.
>
>It would undoubtedly have been less astonishing in 1968 (when the first 
>book was published) than in 1991 (when I first saw it), but I would have 
>thought that even people familiar with 1960's mainframes would see it as 
>strange to use a limited and highly specific artificial assembly that 
>matched poorly with existing systems.

That's the thing: I don't know that it did match poorly against
many of those systems.  Word oriented machines, with word sizes
that were not powers-of-two, abstruse IO instructions; all of
that was fairly common back then.  True, the IBM 360 had bucked
that trend and would set the precedent for what came later, but
that hand't happened yet.

Moreover, assembly language programming for applications was
still common.  Using assembler would have had a lot of reach,
even if it's a fairly opaque way to present algorithms.

>I am sure people were already 
>familiar with the pain of converting code written in assembly for one 
>system into assembly for a very different system - the only advantage of 
>the MIX code was that it was equally useless to everyone, and favoured 
>no one!

Ha; great description.  But had he chosen Burroughs, or IBM 360,
or PDP-6, or the GE-635, or whatever else, it would have been
seen as favoring a particular vendor (and therefore irrelevant
to those using other machines) or too specific to be considered
general.

>> Unfortunately, he is quite adamant about this.  He truly
>> believes that the best way to understand how an algorithm works
>> on a computer is to see it at the instruction level.
>
>Then he could easily have invented a machine that is powerful enough for 
>the details not to matter, and not need describing.  The number and size 
>of registers should not matter in any way for understanding algorithms.

Perhaps?

I suspect that he felt that he _did_ come up with a machine
powerful enough to describe what he wanted, yet not so abstract
that one couldn't see one's way to implementing on the local
CPU.  He wasn't writing for the home computer user or hobby
programmer, as home computers as we know them were yet to be
invented.  He was writing for people working in a computer
center running programs on slow machines that filled a large
room, and likely doing so on punched cards, possibly in
assembler.  We can look at MIX now (or even in the early 1990s)
and say, "huh, that's weird..." but in 1968 it probably would
not have raised so many eyebrows among its intended audience.

>> Other books exist that are better references for most people;
>> certainly for most programmers:
>> 
>> * "Introduction to Algorithms" by Cormen, Leiserson, Rivest,
>>    and Stein is a standard.
>> * Sedgewick's books in C, simply titled, "Algorithms" are pretty
>>    good, though his code style is slightly idiosyncratic.  Now in
>>    its 4th Edition, he has switched to Java and taken on a
>>    coauthor (Kevin Wayne).
>> * "Algorithms", by Dasgupta, Papadimitriou, and Vazirani is a
>>    wonderful book that, I think, strikes a nice balance between
>>    formality and utility.
>> * I am rather partial to Skiena's work, "The Algorithm Design
>>    Manual."
>> * "Data Structures and Their Algorithms" by Lewis and Denenberg
>>    is a bit dated, but very accessible; examples are presented in
>>    a Pascal-like pseudocode.
>> * "Data Structures and Algorithms" by Aho, Hopcroft, and Ullman
>>    is a nice book.  Be careful not to confuse it with Aho and
>>    Ullman's, "The Design and Analysis of Computer Algorithms",
>>    however; the latter is far denser and intended for academics
>>    studying the fundamental properties of algorithms.
>> * "Algorithms + Data Structures = Programs" and the later
>>    revision, "Algorithms & Data Structures", by Wirth, are
>>    similarly dated, but still very nice.
>> * "Purely Functional Data Structures", by Okasaki; I include
>>    this just because I think that it is fun.
>
>My bookshelves are too scattered for me to easily see what I have.  But 
>I am not convinced that books are good references at all these days, for 
>most purposes.  They are, however, still good for study if you are doing 
>courses or really learning a subject.

Oh?  Nowdays we have far more available resources, so I can see
how one wouldn't necessarily reach for a book the way one would
have in days past, but what do you see as the alternative?

>> Did Knuth err using MIX and then MMIX for TAOCP?  Perhaps; I do
>> think that neither Fortran nor Lisp would have been appropriate
>> choices; Algol perhaps.  Other authors around that time or
>> slightly later either adopt a more mathematics-inspired
>> pseudonotation (Dijkstra; Hoare) algolish pseudo-code (Aho et
>> al), or a language of their own design (Wirth).
>
>As Hoare was the head of department when I was at university, and 
>therefore very influential in how we were taught, I am of course partial 
>to his style of notation and think that would have been the best choice!

Could be!  I've always enjoyed the notation he came up with for
CSP, for example.

	- Dan C.

[toc] | [prev] | [next] | [standalone]

#402865

cross@spitfire.i.gajendra.net (Dan Cross) writes:
>In article <11aasbg$r60s$1@dont-email.me>,
>David Brown  <david.brown@hesbynett.no> wrote:

>>As Hoare was the head of department when I was at university, and 
>>therefore very influential in how we were taught, I am of course partial 
>>to his style of notation and think that would have been the best choice!
>
>Could be!  I've always enjoyed the notation he came up with for
>CSP, for example.

Indeed, I still have a copy of that from grad school somewhere
around here.

[toc] | [prev] | [next] | [standalone]

#402877

On 09/10/2026 21:48, Dan Cross wrote:
> In article <11aasbg$r60s$1@dont-email.me>,
> David Brown  <david.brown@hesbynett.no> wrote:
>> On 09/10/2026 14:38, Dan Cross wrote:
>>> In article <11aaimc$n0f0$2@dont-email.me>,
>>> David Brown  <david.brown@hesbynett.no> wrote:
>>>> On 09/10/2026 12:43, bart wrote:
>>>>> [snip]
>>>>> This 'MIX' language was something that astonished me even then. Not only
>>>>> was it assembly that would totally obscure whatever algorithm was being
>>>>> expressed, but it was a weird made-up assembly with unusual byte and
>>>>> word sizes.
>>>>
>>>> Indeed.  When I first saw it, I was familiar with several 8-bit
>>>> assemblies (6502, Z80, 8085) and some 32-bit ARM assembly, and had read
>>>> books on the 68000 family and MIPS.  MIX was, to me, absurd.  To be
>>>> fair, the computer world was not nearly as consolidated in 1962, but I'm
>>>> sure it looked fairly odd even by the standards of the time.
>>>
>>> If one were coming from the world of early 1960s mainframes, it
>>> would perhaps be less astonishing.
>>
>> It would undoubtedly have been less astonishing in 1968 (when the first
>> book was published) than in 1991 (when I first saw it), but I would have
>> thought that even people familiar with 1960's mainframes would see it as
>> strange to use a limited and highly specific artificial assembly that
>> matched poorly with existing systems.
> 
> That's the thing: I don't know that it did match poorly against
> many of those systems.  Word oriented machines, with word sizes
> that were not powers-of-two, abstruse IO instructions; all of
> that was fairly common back then.  True, the IBM 360 had bucked
> that trend and would set the precedent for what came later, but
> that hand't happened yet.
> 

You misunderstand me, I think.  Yes, cpus had widely varying 
architectures, word sizes, data representations, etc., and could have 
instructions dedicated to particular hardware devices - and if all else 
failed in your code, a "halt and catch fire" instruction.  It's not so 
much that MIX matched poorly to existing systems - they all matched 
poorly to each other.  Implementing an algorithm on different 
processors' assemblies meant figuring out how to make it work with that 
particular word size, or how to make efficient use of the particular 
indexing registers and addressing modes that the cpu used.  Translating 
from one assembly to another on a radically different architecture means 
two steps - you first have to figure out what the original code is 
really trying to do, and abstract away from the messy implementation 
details.  Then you have to fit it into the new architecture, and add the 
new messy implementation details.

So by using MIX, rather than a higher level, more abstract pseudo-code, 
anyone trying to use the code in the book on a real cpu has to do twice 
the work.

> Moreover, assembly language programming for applications was
> still common.  Using assembler would have had a lot of reach,
> even if it's a fairly opaque way to present algorithms.
> 

Sure, assembly was very commonly used for applications - and for a long 
time afterwards.  It's a major reason why the computing world is 
dominated by the polished turd that is the modern x86 processor - 
translating assembly programs into anything else is difficult, expensive 
and risky, so it is rarely done.

>> I am sure people were already
>> familiar with the pain of converting code written in assembly for one
>> system into assembly for a very different system - the only advantage of
>> the MIX code was that it was equally useless to everyone, and favoured
>> no one!
> 
> Ha; great description.  But had he chosen Burroughs, or IBM 360,
> or PDP-6, or the GE-635, or whatever else, it would have been
> seen as favoring a particular vendor (and therefore irrelevant
> to those using other machines) or too specific to be considered
> general.

I can fully understand neutrality here.  He may even have wanted to 
avoid favouring one existing high-level language for another.  But the 
guy was pretty smart - he could easily have invented his own 
hypothetical high-level language to use instead of such a low-level one.

> 
>>> Unfortunately, he is quite adamant about this.  He truly
>>> believes that the best way to understand how an algorithm works
>>> on a computer is to see it at the instruction level.
>>
>> Then he could easily have invented a machine that is powerful enough for
>> the details not to matter, and not need describing.  The number and size
>> of registers should not matter in any way for understanding algorithms.
> 
> Perhaps?
> 
> I suspect that he felt that he _did_ come up with a machine
> powerful enough to describe what he wanted, yet not so abstract
> that one couldn't see one's way to implementing on the local
> CPU.  He wasn't writing for the home computer user or hobby
> programmer, as home computers as we know them were yet to be
> invented.  He was writing for people working in a computer
> center running programs on slow machines that filled a large
> room, and likely doing so on punched cards, possibly in
> assembler.  We can look at MIX now (or even in the early 1990s)
> and say, "huh, that's weird..." but in 1968 it probably would
> not have raised so many eyebrows among its intended audience.
> 
>>> Other books exist that are better references for most people;
>>> certainly for most programmers:
>>>
>>> * "Introduction to Algorithms" by Cormen, Leiserson, Rivest,
>>>     and Stein is a standard.
>>> * Sedgewick's books in C, simply titled, "Algorithms" are pretty
>>>     good, though his code style is slightly idiosyncratic.  Now in
>>>     its 4th Edition, he has switched to Java and taken on a
>>>     coauthor (Kevin Wayne).
>>> * "Algorithms", by Dasgupta, Papadimitriou, and Vazirani is a
>>>     wonderful book that, I think, strikes a nice balance between
>>>     formality and utility.
>>> * I am rather partial to Skiena's work, "The Algorithm Design
>>>     Manual."
>>> * "Data Structures and Their Algorithms" by Lewis and Denenberg
>>>     is a bit dated, but very accessible; examples are presented in
>>>     a Pascal-like pseudocode.
>>> * "Data Structures and Algorithms" by Aho, Hopcroft, and Ullman
>>>     is a nice book.  Be careful not to confuse it with Aho and
>>>     Ullman's, "The Design and Analysis of Computer Algorithms",
>>>     however; the latter is far denser and intended for academics
>>>     studying the fundamental properties of algorithms.
>>> * "Algorithms + Data Structures = Programs" and the later
>>>     revision, "Algorithms & Data Structures", by Wirth, are
>>>     similarly dated, but still very nice.
>>> * "Purely Functional Data Structures", by Okasaki; I include
>>>     this just because I think that it is fun.
>>
>> My bookshelves are too scattered for me to easily see what I have.  But
>> I am not convinced that books are good references at all these days, for
>> most purposes.  They are, however, still good for study if you are doing
>> courses or really learning a subject.
> 
> Oh?  Nowdays we have far more available resources, so I can see
> how one wouldn't necessarily reach for a book the way one would
> have in days past, but what do you see as the alternative?
> 

I don't know that there is one right answer - it depends on the depth 
you want to go into, how specialist the topic is, and what you are 
trying to get out of it all in the end.  And it depends on how you 
personally want to learn.  For deeper study and for more specialist 
topics, books are still the top choice for me.  And I much prefer to 
read books than websites over breakfast.

But if I want a reference or refresher on AVL trees (to pick a random 
topic :-) ), my first port of call is Wikipedia.  If that is not enough, 
I might be looking for videos - there's plenty around that can give nice 
animations to help you understand what is going on, from five minute 
quick introductions to hour-long lectures.  I'd look for sample code in 
a high level language - typically Python, but it might be interesting to 
look at implementations in Haskell or other significantly different 
languages.  There are webpages full of explanations of them, and 
comparisons to other tree structures.  And there are online courses for 
those looking for more academic treatment of data structures and algorithms.

The internet is full of resources like this.  Of course the quality is 
varied - you definitely want to look at more than one site to get a 
balanced view, and to minimise the risk of missing something important. 
But for technical and non-controversial subjects like this, you are 
going to be fairly safe with Wikipedia and a google search.

>>> Did Knuth err using MIX and then MMIX for TAOCP?  Perhaps; I do
>>> think that neither Fortran nor Lisp would have been appropriate
>>> choices; Algol perhaps.  Other authors around that time or
>>> slightly later either adopt a more mathematics-inspired
>>> pseudonotation (Dijkstra; Hoare) algolish pseudo-code (Aho et
>>> al), or a language of their own design (Wirth).
>>
>> As Hoare was the head of department when I was at university, and
>> therefore very influential in how we were taught, I am of course partial
>> to his style of notation and think that would have been the best choice!
> 
> Could be!  I've always enjoyed the notation he came up with for
> CSP, for example.
> 

I wonder how CSP is taught now that people wave bank cards or mobile 
phones at vending machines instead of inserting coins...

(There's a fun family of microcontrollers with CSP at their heart from 
XMOS.)

[toc] | [prev] | [next] | [standalone]

#402854

On Fri, 9 Oct 2026 12:38:04 -0000 (UTC)
cross@spitfire.i.gajendra.net (Dan Cross) wrote:

> 
> Knuth is a wonderful object of study, but I do not recommend it.
> 
> 	- Dan C.
> 

Disagreed.

[toc] | [prev] | [next] | [standalone]

#402857

In article <20261009174739.00006700@yahoo.com>,
Michael S  <already5chosen@yahoo.com> wrote:
>On Fri, 9 Oct 2026 12:38:04 -0000 (UTC)
>cross@spitfire.i.gajendra.net (Dan Cross) wrote:
>> Knuth is a wonderful object of study, but I do not recommend it.
>
>Disagreed.

Lacking a lot of information here.

Which part of what I wrote, most of which you snipped, do you
disagree with, specifically?  Would You recommend TAOCP as a
reference for working programmers?  What about it do you like?
Is there anything about it that you do not like?

Perhaps I should clarify: I recommend _studying_ it.  I do not
recommend it as an everyday reference for programmers, nor for
learning data structures and algorithms; I thought that would
have been obvious from the context that you omitted.

	- Dan C.

[toc] | [prev] | [next] | [standalone]

#402881

On Fri, 9 Oct 2026 16:48:21 -0000 (UTC)
cross@spitfire.i.gajendra.net (Dan Cross) wrote:

> In article <20261009174739.00006700@yahoo.com>,
> Michael S  <already5chosen@yahoo.com> wrote:
> >On Fri, 9 Oct 2026 12:38:04 -0000 (UTC)
> >cross@spitfire.i.gajendra.net (Dan Cross) wrote:  
> >> Knuth is a wonderful object of study, but I do not recommend it.  
> >
> >Disagreed.  
> 
> Lacking a lot of information here.
> 
> Which part of what I wrote, most of which you snipped, do you
> disagree with, specifically?  Would You recommend TAOCP as a
> reference for working programmers?  What about it do you like?
> Is there anything about it that you do not like?
> 
> Perhaps I should clarify: I recommend _studying_ it. 

That's better.

> I do not
> recommend it as an everyday reference for programmers, nor for
> learning data structures and algorithms;

It is still the best reference for *some* data structures and
algorithms. Not necessarily something that is still practically
important. In particular, I am thinking about external sortng.

> I thought that would
> have been obvious from the context that you omitted.
>

No, it was not.
 
> 	- Dan C.
> 

What I find especially embarrassing in above conversation between David
and yourself is likening of TAoCP to K&R. 
K&R is just another book of rather average quality that turned important
only because,  by lucky twist of history, the language it describes
became extremely popular.
OTOH, TAoCP is a monument.

[toc] | [prev] | [next] | [standalone]

#402882

On 10/10/2026 18:08, Michael S wrote:

> What I find especially embarrassing in above conversation between David
> and yourself is likening of TAoCP to K&R.
> K&R is just another book of rather average quality that turned important
> only because,  by lucky twist of history, the language it describes
> became extremely popular.
> OTOH, TAoCP is a monument.
> 

The comparison was that both were well-written textbooks with clear and 
readable language, and both are now outdated and usually a poor choice 
for someone today wanting to learn about their topics or use them as 
references.

Obviously there are also very significant differences between them.  You 
don't even need to open the books - you only need to look at the 
thickness of the books to see their scopes were hugely different.

[toc] | [prev] | [next] | [standalone]

#402886

In article <11adp65$1s1lb$2@dont-email.me>,
David Brown  <david.brown@hesbynett.no> wrote:
>On 10/10/2026 18:08, Michael S wrote:
>> What I find especially embarrassing in above conversation between David
>> and yourself is likening of TAoCP to K&R.
>> K&R is just another book of rather average quality that turned important
>> only because,  by lucky twist of history, the language it describes
>> became extremely popular.
>> OTOH, TAoCP is a monument.
>
>The comparison was that both were well-written textbooks with clear and 
>readable language, and both are now outdated and usually a poor choice 
>for someone today wanting to learn about their topics or use them as 
>references.
>
>Obviously there are also very significant differences between them.  You 
>don't even need to open the books - you only need to look at the 
>thickness of the books to see their scopes were hugely different.

I find it weird that this guy feels the need to rise to the
defense of Knuth's honor or something.

	- Dan C.

[toc] | [prev] | [next] | [standalone]

#402913

On 10/10/2026 19:44, Dan Cross wrote:
> In article <11adp65$1s1lb$2@dont-email.me>,
> David Brown  <david.brown@hesbynett.no> wrote:
>> On 10/10/2026 18:08, Michael S wrote:
>>> What I find especially embarrassing in above conversation between David
>>> and yourself is likening of TAoCP to K&R.
>>> K&R is just another book of rather average quality that turned important
>>> only because,  by lucky twist of history, the language it describes
>>> became extremely popular.
>>> OTOH, TAoCP is a monument.
>>
>> The comparison was that both were well-written textbooks with clear and
>> readable language, and both are now outdated and usually a poor choice
>> for someone today wanting to learn about their topics or use them as
>> references.
>>
>> Obviously there are also very significant differences between them.  You
>> don't even need to open the books - you only need to look at the
>> thickness of the books to see their scopes were hugely different.
> 
> I find it weird that this guy feels the need to rise to the
> defense of Knuth's honor or something.
> 

If that is the case, then he needn't bother - I have great respect for 
Knuth and what has contributed to the field of computer science (and of 
course also computer typography).  But that doesn't mean I think he made 
the right decision in his use of MIX and assembly, or that I think his 
books are ever-lasting.  We can appreciate people's achievements without 
idolising them or their works.

[toc] | [prev] | [next] | [standalone]

#402885

In article <20261010190833.00007268@yahoo.com>,
Michael S  <already5chosen@yahoo.com> wrote:
>On Fri, 9 Oct 2026 16:48:21 -0000 (UTC)
>cross@spitfire.i.gajendra.net (Dan Cross) wrote:
>
>> In article <20261009174739.00006700@yahoo.com>,
>> Michael S  <already5chosen@yahoo.com> wrote:
>> >On Fri, 9 Oct 2026 12:38:04 -0000 (UTC)
>> >cross@spitfire.i.gajendra.net (Dan Cross) wrote:  
>> >> Knuth is a wonderful object of study, but I do not recommend it.  
>> >
>> >Disagreed.  
>> 
>> Lacking a lot of information here.
>> 
>> Which part of what I wrote, most of which you snipped, do you
>> disagree with, specifically?  Would You recommend TAOCP as a
>> reference for working programmers?  What about it do you like?
>> Is there anything about it that you do not like?
>> 
>> Perhaps I should clarify: I recommend _studying_ it. 
>
>That's better.

Better?  Better would be to preserve context and add useful
information to the thread.

You quoted the part where I sayd, "Knuth is a wonderful object
of study" and then replied with the single, information-free,
word, "Disagreed", leaving it totally ambiguous whether you
disagreed with that or with my saying that "I do not recommend
it."

>> I do not
>> recommend it as an everyday reference for programmers, nor for
>> learning data structures and algorithms;
>
>It is still the best reference for *some* data structures and
>algorithms. Not necessarily something that is still practically
>important. In particular, I am thinking about external sortng.

CLRS covers external sorting, or did in earlier editions.

>> I thought that would
>> have been obvious from the context that you omitted.
>
>No, it was not.

To you.

Let's look at your response and the context your preserved.

Given that "Knuth is a wonderful object of study, but I do not
recommend it", your response was either factually incorrect, or
a statement of your own dislike of studying Knuth.  Which was
true depends on which part of my statement you disagreed with.

If the second part, that I do not recommend Knuth, then
"Disagreed" would mean that you think I _am_ recommending it, in
direct contradiction of what I had just said; that would be
factually incorrect.

If "Disagreed" with the _first_ part, then you are saying you
disagree that Knuth is a, "wonderful object of study."  If that
is the case, just say so.

>What I find especially embarrassing in above conversation between David
>and yourself is likening of TAoCP to K&R. 
>K&R is just another book of rather average quality that turned important
>only because,  by lucky twist of history, the language it describes
>became extremely popular.
>OTOH, TAoCP is a monument.

Cool, man. Cool.

	- Dan C.

(If he saw this, Don would roll his eyes.)

[toc] | [prev] | [next] | [standalone]

#402889

On 2026-10-10 18:08, Michael S wrote:
>> TAOCP
> 
> It is still the best reference for *some* data structures and
> algorithms. Not necessarily something that is still practically
> important. In particular, I am thinking about external sortng.

Have you anything specific in mind beyond merge-sort?

I was under the impression that many books about algorithms
and data-structures covered the topics that Knuth collected
in his "monument".

>> [...]
> [...]
> K&R is just another book of rather average quality that turned important
> only because,  by lucky twist of history, the language it describes
> became extremely popular.

I know people that back in the days valued K&R as excellent
book. (I never understood where that came from, though.)

Janis

[toc] | [prev] | [next] | [standalone]

#402893

In article <11ae0h8$cjlv$3@dont-email.me>,
Janis Papanagnou  <janis_papanagnou+ng@hotmail.com> wrote:
>On 2026-10-10 18:08, Michael S wrote:
>>> TAOCP
>> 
>> It is still the best reference for *some* data structures and
>> algorithms. Not necessarily something that is still practically
>> important. In particular, I am thinking about external sortng.
>
>Have you anything specific in mind beyond merge-sort?

Radix sort?

>I was under the impression that many books about algorithms
>and data-structures covered the topics that Knuth collected
>in his "monument".

They do.  Knuth does go into great detail about the precise
mathematical properties of the methods he discusses, but it is
not as if treatment is absent from other sources.

>>> [...]
>> [...]
>> K&R is just another book of rather average quality that turned important
>> only because,  by lucky twist of history, the language it describes
>> became extremely popular.
>
>I know people that back in the days valued K&R as excellent
>book. (I never understood where that came from, though.)

The way the poster described it, I think it likely a reflection
of deference to the cachet of Knuth, less the substance of
either reference.

	- Dan C.

[toc] | [prev] | [next] | [standalone]

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.lang.c

csiph-web