CMIS 240 DE Week 4 Study the second half of chapter 3 this week. Analyzing the efficiency of algorithms is an important topic in computer science. The discussion in the book is a good introduction to it. Once an algorithm is correct, we can worry about its efficiency. Basically we are just counting the number of times some fundamental operation of the algorithm executes. This operation will be the unit of work. For searches and sorts, the operation is a comparison of two values. For numeric algorithms, typically a multiplication and/or division is the "countable" operation. We want an algebraic function (one of those f(x) things) that relates the input size (or problem size, or amount of data) to the number of operations executed (x is the input size). The big-O notation allows us to disregard multiplicative factors and lesser terms in the actual analyzed function and just talk about the dominant term. Most practical algorithms are in one of the "bins" (functions) of table 3.2. Note that the last row with N=256 is still a small value, most real-world programs deal with much larger amounts of data, hence the critical need to find efficient algorithms (i.e. ones with smaller rate of growth function), if indeed there can be any (some problems require at least a minimum amount of work in order to be solved). The general discussion is then made concrete by applying it to the member functions of the sorted and unsorted list classes. Note in particular the difference between linear (sequential) search and binary search. This week's exercise will be to demonstrate this to yourself. The next section is more C++ class topics. A class typically has one or more constructor (ctor) functions used to initialize a newly created object. They are convienant and they provide a guarantee that objects are correctly initialized. The name of the ctor functions is the same as the class name. They have no return value and can not use the return statement. They do away with the need for the Initialize and MakeEmpty kind of member functions we've been using in our classes so far. A ctor is automatically called when an object is declared. They can not be explicitly called. The ctor with no arguments is known as the default ctor. The argument lists (i.e. signatures) of the ctors must be distinct so the compiler knows which one to set up to be called when the object is created at run-time. We'll see lots of ctors as we advance through the chapters. Understand the examples in this section. A class can have one destructor (dtor) function. It has the same name as the class but with a tilde ~ in front. It's automatically called when an object goes out of scope, e.g. it's a local variable in a function that is terminating. They are typically used with objects created with dynamically allocated memory, which we first encounter in chapter 4. Operator overloading is one of the coolest things in C++. You can create new meanings for the operators so that they work with class objects. The example has overloaded the < and == operators so that they work with StrType objects. I've also posted a modified DateType class with ctors and an overloaded == operator. The case study is rather long and doesn't include anything new, so I don't recommend spending much time with it. ---------------------------------------------------------------- Exercise Binary search vs sequential search. In the Chapter3/ directory of the class web site is sort.cpp. It creates an array of random ints of the size specified by the user and then sorts the values using the library qsort() function. Download and run the program. Read it to see how it works. There are also binsearch_dos.exe and binsearch_linux.exe files. It creates a random array of user-specified size (up to 100000) and then does random searches in it (i.e. searching for random values). Run the program until you understand what it's doing. The searches are sequential and binary (the array is sorted before the binary searches are done). Your exercise is to create this program. Use the sort.cpp as a base. Add to it code (i.e. functions) to do binary search and sequential search. Keep count of the number of comparisons that are done. Don't use the Sortedtype or any other classes. Sequential search an unsorted array and binary search the sorted array.