Code Journal

Code Journal is a free, biweekly newsletter on programming and computer science provided jointly by Cprogramming.com and AI Horizon. There is also an archive of all past issues on both websites.

CODE JOURNAL: Your Guide to Programming

February 5, 2002

In This Edition:
- Welcome to the Code Journal
- What's the Point of C#
- Search and ... Employ?
- Programming Challenge
- Errata

Welcome to Code Journal, a joint venture between Cprogramming.com
(http://www.cprogramming.com) and AI Horizon (http://www.aihorizon.com)
that aims to provide insightful articles on both C++ and algorithmic



programming. Code Journal is helpware: in return for reading it, you
are asked to help someone else out with their own programming problems.
Good luck, and quick compiling.


---------------------------------------------------------
C/C++ Programming by Alex Allain
---------------------------------------------------------
What's the point of C#?

There has been BCPL, C, and C++; Microsoft recently introduced yet
another language in the same naming tradition: C# (pronounced "C sharp").
C# is a language designed to be fully compatible with Microsoft's
.NET initiative while taking advantage of what has been learned
from C and C++ (as well as Java).

C# is designed to be a platform-independent language in the tradition
of Java. It's syntax is similar to C and C++ syntax, and C# is
designed to be an object-oriented language. There are, for the most
part, minor variations in syntax between C++ and C#. Main has no
return type, there are no semicolons after class names, there are
some (to C++ programmers) strange decisions regarding capitalisation
- such as the capitalisation of Main. Other a few differences,
the syntax is often the same. This decision is reasonable, in light of
the fact that C syntax has been used with several other languages -
notably Java.

Similar to Java, C# does not support multiple inheritence; instead it
provides Java's solution: interfaces. Interfaces implemented by a
class specify certain functions that the class is guaranteed to implement.
Interfaces avoid the messy dangers of multiple inheritence while maintaining
the ability to let several classes implement the same set of methods.

Another helpful feature of C# is garbage collection. Therefore, it is
unnecessary to include a destructor for each class unless a class
hanldes unmanaged resources; if so, it's necessary to release control those
resources from within the class (The Finalize function is used to clear
up these unmanged resources; it can even be abbreviated with the same
syntax as a C++ destructor). Of course, C# also provides direct access
to memory through C++ style pointers, but these pointers are not garbage
collected until specficially released by the programmer.

C#, as part of the .NET framework, is compiled to Microsoft Intermediate
Language
(MSIL), which is a language similar to Java's bytecode. MSIL allows
C# to be platform independent and runs using just in time compiling. Therefore
programs running under .NET gain speed with repeated use. Furthermore, because
the other languages that make up the .NET platform (including VB and Cobol)
compile to MSIL, it is possible for classes to be inherited across languages.
The MSIL, like bytecode, is what allows C# to be platform independent.

The potential for C# is great if the .NET platform succeeds. C# is designed to
take advantage of the design of .NET, and Microsoft has poured a great deal of
money into .NET. Do you need to learn C#? If you knoow C++, you'll probably
be able to pick it up quickly, and yes, you can still use C++ with .NET. It's
important to keep an eye on C# to see how it will affect you.


********************
Alexander Allain is the webmaster of http://www.cprogramming.com.
Contact him at webmaster@cprogramming.com

---------------------------------------------------------
Algorithms and Programming by Eric Suh
---------------------------------------------------------

Search and ... Employ ?

All right, so you've read about sorting algorithms at AI Horizon, and now
you've got a sorted array. Just having a sorted array, however, doesn't do
anything for you unless you are going to search for things in the array
itself.

Assume you have a sorted array. Now, when you search for that item, what you
really want to do is see if the item is actually stored in the array. If it
isn't, then you want the algorithm to say so. If the item actually is present,
however, then you want the algorithm to not only say that it is present, but
you also want to have the algorithm return the entire element so that you can
access it.

Now, let's say that the elements of your sorted array are records of employees,
sorted by the employee's 3-digit company ID number (this is a small company,
so the number is - we can hope - unique to each employee). Now, we want to
see if an employee with a certain ID number - 243, for instance - exists.
Let's call that number the target number.

There are a variety of algorithms to search a sorted array, but we shall
examine only two of them. One is extremely simple, and the other one is still
easy, but it is greatly more efficient.

The simplest way is to just start at the beginning of the array and compare,
from smallest to greatest, each employee's ID number with the target number.
When the target number becomes smaller than an employee's ID number, then we
know that the target number isn't in the array.

Of course, if the target number were really big, then we'd have to compare it
to almost every single element in the array before deciding whether or not it
is in the array.

This method works well for situations where you can only access the elements
of the array in order; this kind of array is called a stream, and you often
use this method with ordered linked lists, where you have to start at the
beginning and just compare down the entire linked list.

For normal arrays, however, there is a more efficient method. This algorithm
relies upon the fact that you can access any element of the array without
having to go through all of the elements before it; this ability is called
random access. (On a side note, the temporary memory in your computer is
basically a big array that you can access like this, and so it is called
Random Access Memory, or RAM.)

Let's say our ordered array has 100 employees recorded in it. Since we can
access any array element we want, wouldn't it be more efficient to start
searching in the middle of the array instead of at the end? If the target
number is less than the middle employee's ID number, then we know that all
of the numbers coming after this employee's ID are going to be bigger than
the target number anyway. If the target's bigger, than the situation is just
the opposite. So, we can eliminate half the array from the search!

Now, we're down to one section of the array. We could just start searching
from one end of that section and keep working our way to the end.or we could
just treat it as another array and use the previous step again. Now, we can
do this over and over until we either find an element that matches the target
number, or we're down to a section with only one element in it that doesn't
match the target number. So, we've got the results we wanted, and the
algorithm is much faster than just searching from one end.

For the people knowledgeable about Big-O notation and mathematics, this
algorithm is essentially O(log2(n)). That is, this algorithm has the
order-of-magnitude similar to the logarithm of n to the base 2, where n is the
number of elements in the sorted array.

What does this mean in non-mathematical terms? Well, if you have a sorted
array of one thousand elements, using the first searching method, you might
search all of the elements, making up to 1000 comparisons in the worst case.
With the second method, however, you will make at most about 10 comparisons.
The time saved gets even better when you get to talking about extremely large
numbers: for a huge array of 1 trillion elements (American trillion, that is,
which is numerically 1,000,000,000,000), using the second method, you only have
to make up to 40 comparisons. That's it!

The way you implement this algorithm is really quite simple. You need two
variables: a low variable and a high variable, which keep track of the ends
of the section of the array that you are looking at. Initially, the low
variable will store the index value of the first element of the array
(in C++, that is normally 0) and the high variable will store the index
value of the last element of the array (in C++, that would be n-1, where n is
the number of elements).

You need to find the middle of the section. The index for the middle element
is basically (hi - lo)/2 + lo rounded off to the nearest integer in some
manner. If t, the target number, is less than the middle element, then reset
hi to equal that middle element's index. If t is greater than the middle
element, then reset lo to equal the middle element's index instead. In this
way, you will eventually narrow down on where the target number should be in
the array.

This handy little algorithm has been used everywhere, and it has even been
modified to be used in a Chess playing algorithm called MTD(f). The algorithm
that you have just learned is called the "binary search algorithm", so titled
because you keep on dividing the array into two halves. So, have fun with
this new, time-saving search algorithm.

************************************
Eric Suh is the webmaster of AI Horizon (http://www.aihorizon.com/), a site
devoted to Artificial Intelligence and Computer Science programming.
Contact him at webmaster@aihorizon.com



---------------------------------------------------------
Code Challenge
---------------------------------------------------------

At the end of every issue we will issue a programming challenge and ask
people to submit their solutions within two weeks. The best solutions
will be published the next issue, along with a new challenge.

Congratulations to top three finishers in the Towers of Hanoi challenge:
James Galloway, Praveena.M, and Thota Raja Sekhar.

Source code available at
http://www.cprogramming.com/source/jghanoi.c
http://www.cprogramming.com/source/pmhanoi.cpp
http://www.cprogramming.com/source/trshanoi.cpp

This week's challenge:

One famous chess problem is the Knight's Tour, in which a knight, placed on
a starting square, is then moved to every other square on the chessboard.
The Knight's Tour is a fairly typical chess problem. Your challenge is not
only to write a program to calculate the Knight's Tour from any square on the
board, but also to allow the user to add up to five pieces to the board that
the moving knight must avoid capturing and must also avoid being moved onto
a square where it could be captured. As an interesting note, in _The
Psychology of Chess_ the authors talk about a test for chess talent that
works under similar conditions and is based on the speed of response.
The test accurately predicated a future grandmaster.



Send your solution's source code to codejournal@cprogramming.com, and you may
find it published (Note: due to length of code, solutions will be downloadable
from the web rather than printed). Please include either your name or an
identifying username so that we may attribute the solution to you in the next
newsletter. If you wish, you may ask us to withhold your name.

---------------------------------------------------------
Errata to previous issue
---------------------------------------------------------

In the previous issue we made two major mistakes:
Eric wrote that the fiftieth element of an array is accessed by typing

employees[50];

He should have written

employees[49];

As well, Alexander wrote that C++ has no Exclusive-Or operator. It does,
however. ^ is the symbol for bitwise exclusive-or. Eg,

A^B;

We apologize for these mistakes, and if we have made any errors in this
issue, please inform us.
---------------------------------------------------------
Suggestions and comments on this newsletter should be sent to codejournal@cprogramming.com or codejournal@aihorizon.com.

Editors:
Eric Suh, webmaster@aihorizon.com
Alexander Allain, webmaster@cprogramming.com

To unsubscribe from this journal, send a blank email to codejournal-unsubscribe@mlm.cprogramming.com.



-----
Interested in advertising with us?
Please read our privacy policy.
Copyright 1997-2005 Cprogramming.com. All rights reserved.