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 --------------------------------------------------------- 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 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 Eric stated that Fortran had rigid formatting requirements; however, the latest Fortran standard frees the programmer from these restrictions. --------------------------------------------------------- Suggestions and comments should be sent to codejournal@cprogramming.com. Editors: Eric Suh, webmaster@aihorizon.com Alexander Allain, webmaster@cprogramming.com To unsubscribe, send a blank email to codejournal-unsubscribe@mlm-cprogramming.com