|
|
|
February
5, 2002 Issue of Code Journal
(Back to Code
Journal Archive)
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 in both HTML
and text formats.
This is the February 5th Issue. (If you want a pure text version,
go to the text archive
of Code Journal.)
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 the Code Journal, a joint
venture between Cprogramming.com
and AI Horizon 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 know 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 Cprogramming.com.
Contact him at [email protected]
---------------------------------------------------------
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, a site devoted to Artificial Intelligence and Computer
Science programming.
Contact him at [email protected].
---------------------------------------------------------
Code Challenge
---------------------------------------------------------
Every issue, we will issue a programming challenge and ask people
to submit their solutions within two weeks. A few of the best solutions
will be published the next issue, along with a new challenge.
The Previous Issue's Challenge
------------------------------------
The Towers of Hanoi is a very old problem,
and its solution is a relatively simple algorithm to work out and
program. In the game, there is a pyramidally shaped stack of disks
placed onto an upright peg. There are two other pegs, each empty.
The challenge is to move all of the disks from the first peg to the
third peg.
There is a catch, however. Each disk is a different size, and each
disk can only be placed on top of a larger disk. You are free to place
any disk on an unoccupied peg, but after the first disk has been placed,
only smaller disks can be placed on it. Also, you can only move one
disk at a time (they're made of ultra-dense, ultra-heavy material!)
-|- | |
--|-- | |
---|--- | |
----|---- | |
Move these to here.
The program must be able to handle any height of disks up to and including
eight; the program should be able to output the intermediate steps
as the solution is worked out; the program should use some form of
ASCII output for the representation.
Solutions
------------------------------------
Congratulations to top three finishers in the Towers of Hanoi challenge:
James Galloway, Praveena.M, and Thota Raja Sekhar.
Their solutions are available at (respectively)
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 solutions to [email protected]
as source code files, and you may find it published. 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
---------------------------------------------------------
In the previous issue Eric stated that Fortran had rigid formatting
requirements; however, the latest Fortran standard frees the programmer
from these restrictions.
---------------------------------------------------------
Suggestions and comments on this newsletter should be sent to [email protected]
or [email protected].
Editors:
Eric Suh, [email protected]
Alexander Allain, [email protected]
To unsubscribe from this journal, send a blank email to
[email protected]. |
|
|
Home 
