REMEMBER: Your homework #4 is due Thursday next week!!
We are going to take a more in-depth look at some of the objects and "try its" on the W3C Schools JavaScript web site, as well as do some exploring of the Mozilla JavaScript site. These are good online references to assist you with your programming tasks. We'll also do a quick search on the Stack Overflow site so you can see what happens there. There are several important JavaScript Objects on which we have not yet touched (Date, RegExp, Number, Error), so we'll see what they have built in for us.
Over the past semester, we have seen how to break down a problem into smaller problems, so that we can solve the smaller problems to arrive at a "grand" solution. We have taken our problem descriptions apart, written each part in a step-wise fashion in some sort of quasi-pseudocod, and then seen how those smaller steps can be turned into the actual code to solve the problem.
Remember how when doing a web page solution to a problem (such as the stack, the quadratic solver, or the calculator) we have split the parts of the solution into two files? That is the basics of what is called modularization. The idea is that it is easier to maintain small modules of code than it is to maintain large monolithic programs. In addition, the small modules can be linked together to create the larger program functionality, and can be re-used in many different programs so that the programmer can take advantage of what has gone before (and has been DEBUGGED before!) to lessen the amount of work required. This also reduces the schedule time needed to produce a software product, which reduces costs.
With modular programming, modules can contain functions that are grouped logically so that similar functionality is collected together. The functions can also be controlled, so that they have ways of being accessed that provide well-defined inputs and outputs. This specificity helps the programmer who uses the module know exactly how to use it, what the inputs should be, and what the expected outputs will be for each of the inputs.
Systems that are designed with modularity in mind, if correctly implemented, can be much more easily used and adapted than their monolithic counterparts, in which the entire program is one module. If done in a manner to facilitate such use, they can be "extended" as well, allowing new functionality to be added on, which is related but not generic enough for the original module to have included it originally. This philosophy is particularly applicable in Object-Oriented methods of programming.
Some examples to discuss:
Once we have developed an algorithm to solve a problem, we need to reflect if it is the best way to solve that problem. This process is sometimes known as optimizing or optimization. The idea here is to try to determine the "running time" of the algorithm, and then see if there is another way to solve the problem, or another way to do parts of the solution, that will be more optimal than the original. There are two basic ways of comparing solutions: Efficiency, and Running Time.
Efficiency is based on several things, depending on what is the most important consideration of the program. For example, when writing a loop to index an array, one can choose a "for" loop or a "while" loop. If the maximum array size is known beforehand, it makes sense to use the former, since the ending condition of the loop invariant is easily known. However, as we've seen in several of our homework problems, it is often the case that the programmer has no idea what the length of the input might be [as an example] and thus needs to handle an array of a size that is unknown at the time the code is written. In this case the "while" loop might be a better choice.
Running time is most often based on the time required to process different data sets using different algorithmic solutions. For example, when performing a search for a specific item in a list, you can start at the beginning of the list and look at every item until you find the one you seek. However, if the list is sorted in some order, you can do a "binary search" which will greatly reduce the number of comparisons required to find the item.
Analyzing Algorithms is usually done (in CS anyhow!) using a type of standardized notations called "Big-Oh Notation". [The letter O is used because the original idea was taken from the analysis of mathematical functions, in which their growth rates were based on the "order" of the function.] Analysis is based on two different but related resources: time complexity based on the number of operations required, and space complexity, which is a description of the data set size for the data the algorithm is operating upon.
The complexity for the worst-case running of a given algorithm can often be figured out by looking at the structure of the code used to implement it. Consider the following code:
var n = parseInt( prompt( "Enter an integer" ) );
var output = '';
if( n > 10 ) {
alert( "This may take some time" );
}
for( var i = 1; i < n; i++ ) {
output += (i * 2) + "<br />";
}
alert("done");
A computer will require time to execute each of the instructions in this algorithm. Analyzing this code, the first, second, third, and last lines will each only run one time. However, the loop will be executed a number of times, and in fact, each of the parts of the loop will execute that many times. Remember that in this loop, the initialization of the loop counter is done once, but the loop check, the body of the loop, and the incrementing are done once for each time through the loop. Therefore, if the value of n is 20, they will be executed 20 times each, for a total of 60 operations. Add the initial step of the loop, and the other three lines, and there are 64 total operations performed for this program using an integer input of 20. You can also easily see that as the input goes up, the number of operations approximately triples given each increment of the input. Because there is a linear relationship between the number of operations and the size of the data, we call this a "linear" algorithm, and say it runs in "big-oh of N" time.
Remember the "binary search" algorithm we discovered a few weeks ago? That is said to run in "logarithmic time", also known as "big-oh of log-n" time, because the number of comparisons is the log of the number of data items in the list to be searched.
Here is a list of the different types of classifications and their names.| Big-Oh Name | Common Name |
|---|---|
| O(1) | constant |
| O(log n) | logarithmic |
| O(root-n) | root-N |
| O(n) | linear |
| O(n log n) | N-log-N |
| O(n2) | N-squared |
| O(n3) | N-cubed |
| O(2n) | two-to-the-N |
So, let's work an example.
var n = parseInt(prompt("Enter an integer"));
if( n > 10 ) {
alert("This may take some time);
}
for( var i = 1; i < n; i++ ) {
for( var j = 1; j < i; j++ ) {
output += (i * j) + "<br />";
}
}
alert("done");