Will I ever forget this?

I just chatted with my colleagues on using sentinel of linear search.  In my mind, I always assume one can use a negative infinity as a sentinel.

But when one of colleagues come back to me and ask "Doesn't that mean you still have two comparisons? "  Then I was dumbfounded.   And his is right! I was dead wrong!

As it turns out, one should actually use the key as the sentinel.  In that case, one just need to check the return index is smaller than the length of the array or the length of the array +1 at the end of the search to decide if the search is sucessful.

This is a good mistake, I think I will never forget this trick from now on.

Linear Search 6 (MIXAL)

This is just to back record my previous writing using the Dan's MIX compiler

http://tcrcstudy.blogspot.com/2011/05/some-taocp-readings-merge-sort.html

Linear Search I wrote.

Seems to be a reasonable implementation for a simple program. 

#include <stdio.h>
#define N 5
int linear_search(int a[],int key)
{
  int i;
  for(i=0;i<N;i++)
    if(a[i]==key)
      return i;
  return -1;
}
int main(int c,char *v[])
{
  int A[N]={44,22,33,41,50};
  printf("33? %d\n",linear_search(A,33));
  printf("99? %d\n",linear_search(A,99));
  return 0;
}

Linear Search 1

Linear Search 1 (Bad)
Reason: mistyped a as A.  Not in the flow and certainly the effect of Sunday. As they say, "not many great discovery is made by people who enjoy themselves and having fun". 

Some TAOCP readings: merge sort, sequential search and my first MIXAL.

Among the three classic textbooks.  TAOCP is probably the most difficult to read.  The requirement on math is certainly an issue but I found the most difficult part is to understand MIX and MIXAL.  My honest reaction to MIX and MIXAL is - why would anyone use it? 

If I was going to write a book about programming, I would certainly used C or probably Intel Assembly language.   But after I understand the first MIX program, a sequential Search in Chapter 6, only 7 lines but it's already a wrestle for me,  I start to understand why Prof. Knuth would want to do things like that.  (See Listing 1)

      K EQU 10
      N EQU 10
    KEY EQU 200
   INFO EQU 210
START LDA 10
      ENT1 1-N
2H    CMPA KEY+N,1
      JE SUCCESS
      INC1 1
      J1NP 2B
FAILURE EQU *
SUCCESS LDA INFO+N,1
EXIT JMP *


The reason why MIX is used is to convince the reader that programming is independent of the choice of language.  So if the language is created within a book, one can still use it to analyze programs.   Their properties would just be exactly the same as written in any programming languages!

Of course, once you figure out the meaning of every line of the program and how it works.  You can start to see the beauty of it as well!

In a way, Prof. Knuth is like the Tolkien in C.S. He create a new language within his book which is quite an epic like The Lord of the Rings.

* 5.2.4 is a mysterious to me.
* 6.1 opens my eyes.   I have no idea there are so much to think about in sequential search.  I should implement linear search as part of practice.