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

Groups > comp.lang.c > #402850

Re: AVL tree insertion - programming exercise

From cross@spitfire.i.gajendra.net (Dan Cross)
Newsgroups comp.lang.c
Subject Re: AVL tree insertion - programming exercise
Date 2026-10-09 12:38 +0000
Organization PANIX Public Access Internet and UNIX, NYC
Message-ID <11aan7c$ki0$1@reader2.panix.com> (permalink)
References <86ece2kppv.fsf@linuxsc.com> <11aa8vb$jk93$1@dont-email.me> <11aaggn$mu6q$1@dont-email.me> <11aaimc$n0f0$2@dont-email.me>

Show all headers | View raw

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.

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

Thread

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 scott@slp53.sl.home (Scott Lurndal) - 2026-10-11 15:24 +0000
  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

csiph-web