CODE JOURNAL: Your Guide to Programming March 11, 2002 In This Edition: - Welcome to the Code Journal - Handling Errors Exceptionally Well in C++ - Time Flies Like an Arrow, but Time Algorithms with Big-O - Programming Challenge 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 --------------------------------------------------------- Handling Errors Exceptionally Well in C++ One handy feature of C++ is its exception handling system. An exception is a situation in which a program has an unexpected circumstance that the section of code containing the problem is nor explicitly designed to handle. In C++, exception handling is useful bcause it makes it easy to separate the program design between code written to handle the chores of the program and code written to handle errors; doing so makes reading the code much easier. Furthermore, exception handling in C++ propagates the exceptions up the stack; therefore, if there are several functions called, but only one function that needs to reliably deal with errors, the method C++ uses to handle exceptions means that it can easily handle those exceptions without any code in the intermediate functions. When errors occur, the function generating the error can 'throw' an exception. For example, take a sample function that does division: const int DivideByZero = 10; //.... double divide(double x, double y) { if(y==0) throw DivideByZero; return x/y; } The function will throw DivideByZero as an exception that can then be caught by an exception-handling catch statement that catches exceptions of type int. The necessary construction for catching exceptions is a try catch system. If you wish to have your program check for exceptions, you must enclose the code that may have exceptions thrown in a try block. For example: try { divide(10, 0); } catch(int i) { if(i==DivideByZero) cerr<<"Divide by zero error"; } The catch statement catches exceptions that are of the proper type. You can, for example, throw objects of a class to differentiate between several different exceptions. As well, once a catch statement is executed, the program continues to run from the end of the catch. It is often more useful for you to create a class that stores information on exceptions as they occur. For example, it would be more useful if you had a class to handle exceptions. class DivideByZero { public: double divisor; DivideByZero(double x); }; DivideByZero::DivideByZero(double x) : divisor(x) {} int divide(int x, int y) { if(y==0) throw DivideByZero(x); } try { divide(12, 0); } catch (DivideByZero divZero) { cerr<<"Attempted to divide "<<<" by zero"; } Of course, it's also possible to have a general exception handler that will respond to any thrown exception. To use it, simply use catch(...) for the catch statement. The handy thing about exception handling is that the errors can be handled outside of the regular code. This means that it is easier to structure the program code, and it makes dealing with errors more centralized. Finally, because the exception is passed back up the stack of calling functions, you can handle errors at any place you choose. ******************** Alexander Allain is the webmaster of http://www.cprogramming.com. Contact him at webmaster@cprogramming.com --------------------------------------------------------- Algorithms and Programming by Eric Suh --------------------------------------------------------- Time Flies Like an Arrow, but Time Algorithms with Big-O In Computer Science, there is often a need to measure the speed of an algorithm. In this way, we can compare the efficiency of different algorithms, and so make better and better ones. How, then, does one go about finding the speed of an algorithm? Maybe an experimental method would work. Implement the algorithms on one computer, and then run all of them and time them. The one with the smallest running time would be the most efficient. This method seems great and pretty simple, but there are several flaws with it. First, the performance of the machine can vary greatly from trial to trial, because it is very difficult to create an identical, clean environment for every run. Secondly, algorithms can be slower or faster depending on the architecture of the operating system, the hardware, and even the compiler or interpreter. Some systems can simply handle certain operations better than others, while hardware and software often make optimizations to code that can really affect performance. Third, what would the size of the testing data set be? Often, the "faster" algorithms will be about the same or even worse than the "slower" algorithms for small data sets. However, if a large data set is used, then testing will take a very long time, and small independent factors can have a much greater effect on the computational speed. All in all, it is better to get a theoretical, abstract way of defining the efficiency of an algorithm. Let us define the number 'n' to be a designation for the "size" of the problem. In sorting, this might be the number of elements to be sorted. In searching, this would be the number of items to be searched through. It could be the number of bits in number, or just about anything that determines how long the algorithm will take. The theoretical abstract way of defining efficiency is called Big-O notation. This notation is written as O(f(n)), where f(n) is some function of the variable 'n' which we defined above. The notation O(f(n)) means that for large enough values of 'n', the exact number of theoretical operations (be it comparisons or data writing or something else entirely) the algorithm must do (designated T(n)) is less than f(n) multiplied by some constant multiplier. That is, T(n) <= k x f(n), where k is some constant. The algorithm with T(n) operations would then be considered O(f(n)). The Big-O stands for "order of magnitude", a mathematical concept of how "fast" something changes for very large values. Of course, if you think about it, you could say that all algorithms are then O(infinity). This is true, of course, but it doesn't help us in our analyzing an algorithm. So, by convention, f(n) is usually made as small and as simple as possible, so that we can quickly get much information about the speed of an algorithm out of the notation. For instance, some of the most common values for f(n) are: 1, n, n^2, n^3, n*log2(n), log2(n), e^n, 2^n. (The caret '^' sign means "to the power of". So, n^2 is "n squared." The log2(n) means "Logarithm to the Base 2 of n"). For sufficiently large n, those functions can be ordered from fastest to slowest. O(1) O(log2(n)) O(n) O(n*log2(n)) O(n^2) O(n^3) O(2^n) O(e^n) When Computer Scientists began to use this notation and analysis often, they began to encounter some problems for which algorithms were always O(2^n) or something large like that. They found that these problems all seemed to have similar situations appearing. Thus, Computer Scientists began to distinguish between "Polynomial Time" problems and "Non-deterministic Polynomial Time" problems (or in short, P and NP problems). P problems are those problems for which a solution can be found that is O(n^x) or faster, where x is some integer. n^x is a polynomial function, so these problems are called "Polynomial Time" problems. In NP problems, the solution to a problem can be checked in Polynomial time. That is, if you have a possible solution to an NP, checking to see if the solution is correct is a P problem. So, all P problems are a subset of NP. Sorting an array is a P-problem, and checking to see if an array is sorted is also a P-problem: you just see if the elements are in order. Not all NP problems are necessarily P problems, however. Think about factoring a number: the best algorithm anyone can think of right now involves simply checking all of the numbers from 2 onwards and dividing. That algorithm is an exponential time solution, but checking to see if the solution is correct is easy: you just multiply the factors and check if you get the correct number. No one knows, however, whether this problem can be done in polynomial time or not; maybe we just haven't gotten a smart enough programmer. Or maybe it just isn't possible to do it in polynomial time. The big question of this century and the next for Computer Science is, "Is NP = P?" It has not been proven either right or wrong, even though there is a million dollar prize waiting for anyone who proves it one way or the other. Who knows, maybe you will be the one to prove it. ************************************ 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. We only received one response to last weeks challenge. Mike McInnis submitted a standard knight's tour program rather than the modified version; but given the dearth of responses we are publishing his response: http://www.cprogramming.com/source/mm-knight.cpp This week's challenge: Write the shortest quicksort algorithm you can. It's possible to do it, minus the variable declarations, in roughly four lines. Winners will be selected based on length of code. --------------------------------------------------------- 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