10. Program Execution Time ( Terminal Session on this Machine )

10.1 Introduction

One of the questions which computer scientists have dealt with from the very beginning of this field has to do with just How far can one go in computer science?, or What are the limits of computer science? We have studied algorithms which are too time consuming to execute on any computer. However there are other kinds of questions we should ask. For example, there are problems for which there are no known, as of yet, algorithms. There are problems which are known to be non-computable. A problem is said to be non-computable if a proof exists that, given the current structure for computers or computation, no program can be written which solves the problem.

10.2 Order Notation

In Chapter 5, Algorithms, we developed the idea of quantifying the amount of work done during the execution of a program. This quantification involved presenting the work done as a function of the size of the problem. The idea of work done by a program may include the number of times a certain operation is performed or the amount of memory used by the program or the execution time of the program. Since any of these categories of work ultimately take some amount of time, we can simplify our analysis, without any loss of generality, by using execution time as our measure of program performance.

We say a computer program is order (f n), written as (O (f n)), if there is a function f and a constant k such that the execution time of the program is not more than (* k (f n)). We say that n is the size of the problem which the program solves and of course we are interested in what happens to the execution time when the size of the problem is large.

As an example of the order notation consider the following function which computes the largest element of a non-empty list of numbers.

10.2.1 Maximum Function

(define maximum
  (lambda (ls)
    (define max-helper
      (lambda (ls1 max)
        (if (null? ls1)
          max
          (if (> (car ls1) max)
            (max-helper (cdr ls1) (car ls1))
            (max-helper (cdr ls1) max)))))
    ; (trace max-helper)
    ; This function assumes ls has at least 1 element
    (max-helper (cdr ls) (car ls))))

Uncommenting the trace of max-helper yields the following output.

(maximum '(1 9 2 4 10 5))
Entry (max-helper '(9 2 4 10 5) 1)
|Entry (max-helper '(2 4 10 5) 9)
| Entry (max-helper '(4 10 5) 9)
|  Entry (max-helper '(10 5) 9)
|  |Entry (max-helper '(5) 10)
|  | Entry (max-helper '() 10)
|  | ==> 10
|  |==> 10
|  ==> 10
| ==> 10
|==> 10
==> 10

One can easily verify that the number of times max-helper is used, i.e., the execution time of maximum, is n, the number of elements in ls. Hence, the execution time of maximum is of order n.

10.2.2 A Sorting Algorithm

Suppose we which to sort a list of numbers such as (9 1 4 2) in ascending order. We could make a pass through the elements of this list using the following algorithm called a sort-pass. Compare the first two elements. Since they are not in sorted order, interchange them producing (1 9 4 2). Continue this process with the next two elements producing (1 4 9 2) and finally, compare the last two elements and since they are not in sorted order, interchange them producing (1 4 2 9). The sort-pass has succeeded in finding the largest element in the list and putting it in the last position.

10.2.3 sort-pass Function

(define sort-pass
  (lambda (ls)
    ; stop when we have a list of two elements
    (if (null? (cddr ls))
      (if (< (car ls) (cadr ls))
        ls
        (reverse ls))
      (let ((1st (car ls))
            (2nd (cadr ls)))
      (if (< 1st 2nd)
        (cons 1st (sort-pass (cdr ls)))
        (cons 2nd (sort-pass (cons 1st (cddr ls)))))))))
(sort-pass '(9 1 4 2)) ==> (1 4 2 9)
(trace sort-pass) ==> #<unspecified>
(sort-pass '(9 1 4 2))
Entry (sort-pass '(9 1 4 2))
|Entry (sort-pass '(9 4 2))
| Entry (sort-pass '(9 2))
| ==> (2 9)
|==> (4 2 9)
==> (1 4 2 9)
4 2 9)

In the above trace of sort-pass with n = 4, it is clear that 3 comparisons were made. From this it follows that when a list has n elements, sort-pass makes (- n 1) comparisons.

To complete the sort of a list, we notice that we could use sort-pass on the list which remains after removing the last (which is now known to be the largest) element. This process should be repeated on successively shorter lists until a list of two numbers is obtained.

10.2.4 sort Function

(define sort
  (lambda (ls)
    ; stop when we have a list of just two elements
    (if (null? (cddr ls))
      (sort-pass ls)
      (let ((result (sort-pass ls)))
        (append (sort (all-but-last result))
                (last-pair result))))))

If we trace sort, we have:

(sort '(9 1 4 2))
Entry (sort '(9 1 4 2))
|Entry (sort '(1 4 2))
| Entry (sort '(1 2))
| ==> (1 2)
|==> (1 2 4)
==> (1 2 4 9)
2 4 9)

This sort algorithm is referred to as bubble sort. The name is derived from the fact that as each pass is made, the largest element in a sub-list sinks all the way to the bottom of the list, displacing each smaller element one position, at most, upward. As the sort progresses, the larger elements sink quickly to their lower positions while the smaller elements slowly "bubble" up to their final resting place, one position per sort-pass.

We see that when n = 4, sort-pass is used 3 times, that is, sort-pass is used on the entire list (9 1 4 2) to find the largest element, 9, and put it at the end. Then sort-pass is used again on the list (1 4 2) to find its largest element, 4. Finally, sort-pass is used on (1 2) and that two element list is returned since the elements are in the right order. Next, we count the number of comparisons required to sort this 4 element list. The first sort-pass uses 3 comparisons, the second uses 2 comparisons and the last uses 1 comparison for a total of 6 comparisons.

For a list of n elements, the comparison total is:

c = (+ (- n 1) (- n 2) ... 2 1)

We wish to simplify the formula for c. We can also write c as:

c = (+ 1 2 ... (- n 2) (- n 1))

Adding these two formulas we have

(* 2 c) = (+ n n ... n n) = (* n (- n 1))

so that

c = (/ (* n (- n 1)) 2) = (- (/ (* n n) 2) (/ n 2))

Since c involves only terms of n squared and n, we say that the bubble sort algorithm is of order (* n n). To sort a list of 1000 elements will require almost 500,000 comparisons while sorting a list 1,000,000 elements will require about (expt 10 12) comparisons. This number is so large that bubble sorting lists of this size is not practical. There are faster sorting algorithms. Hoare's QuickSort algorithm runs in a time of order (* n (log2 n)).

The execution times for the maximum function, bubble sort and QuickSort are compared in the following chart.

The numeric data for this graph shows that the bubble sort is probably not practical for n values much larger than 1000 and it also shows that even QuickSort will have difficulty sorting large lists.

         1000         10000  100000        1000000       n                              
       499500      49995000  4999950000    5E+11         (- (/ (* n n) 2) (/ n 2))      
   9965.78428    132877.124  1660964.05    19931568.6    (* n (log2 n))

10.2.5 Polynomial Execution Time

A polynomial in n of degree j is a function which can be written in the form:

(+ a0 (* a1 n) (* a2 (expt n 2)) ... (* aj (expt n j)))

A computation is said to be tractable if its execution time is less than or equal to some polynomial in n. It follows that a computation is intractable if its execution time is greater than any polynomial.

10.3 Intractable Computation

Recall that the fibonacci function, studied in Chapter 5

10.3.1 fibonacci Function

(define fibonacci
  (lambda (n)
    (if (< n 2)
      n
      (+
        (fibonacci (- n 1))
        (fibonacci (- n 2))))))

had an execution time of

(+ (* e (expt q n)) (* f (expt r n)))

for suitably chosen e, q,f and r. This time is exponential which is clearly greater than any polynomial in n. Hence, the fibonacci function above is an example of an intractable computation.

10.3.2 The Towers of Hanoi

An ancient legend describes the activities of some monks in a far away place who are engaged in the task of moving 64 disks of increasing size from one of three pegs to another. The ground rules of this task is that only one disk may be moved at a time and putting a larger disk on top of a smaller disk is not allowed. It is said that time will end when the monks finish this task.

Suppose we wish to move one disk from peg a to peg c. This is an easy task; just move the disk from a -> c.

Next, consider the problem of moving two disks from peg a to peg c.

The moves would be a -> b

a -> c

and b -> c.

The problem of moving three disks from a -> c is a bit more complex. However, it can be decomposed into three smaller problems, namely, moving the top two disks from a -> b, moving one disk from a ->c and moving two disks from b -> c.

The moves for this problem are:

a -> c
a -> b, c -> b
a -> c, b -> a
b -> c, a -> c

10.3.3 display-tower-of-hanoi Function

(define display-tower-of-hanoi
  (let ((show-move (lambda (s d) 
                     (display s)
                     (display " -> ")
                     (display d))))
    (lambda (n)
      (letrec 
        ((move 
           (lambda (n source destination helper)
             (if (= n 1) 
                 (begin
                   (show-move source destination) 
                   (newline))
                 (begin
                   (move (- n 1) source helper destination)
                   (show-move source destination)
                   (display ", ")
                   (move (- n 1) helper destination source))))))
        (move n 'a 'c 'b)))))

We now try to analyze display-tower-of-hanoi to discover the order of execution time for this function. Notice that:

(display-tower-of-hanoi 4) ==>
a -> b
a -> c, b -> c
a -> b, c -> a
c -> b, a -> b
a -> c, b -> c
b -> a, c -> a
b -> c, a -> b
a -> c, b -> c

and,

(display-tower-of-hanoi 5)
a -> c
a -> b, c -> b
a -> c, b -> a
b -> c, a -> c
a -> b, c -> b
c -> a, b -> a
c -> b, a -> c
a -> b, c -> b
a -> c, b -> a
b -> c, a -> c
b -> a, c -> b
c -> a, b -> a
b -> c, a -> c
a -> b, c -> b
a -> c, b -> a
b -> c, a -> c

A little additional analysis shows that (display-tower-of-hanoi n) produces (- (expt 2 n) 1) moves. The display-tower-of-hanoi program is intractable since its order is (- (expt 2 n) 1) which is exponential (exponential times are always greater that polynomial time).

(display-tower-of-hanoi 64) ==> (- (expt 2 64) 1) =

18446744073709551615 moves. If a modern workstation can generate 1000 moves per second, it will take that workstation approximately 5,849,424 centuries, 17 years, 129 days, 14 hours, 25 minutes and 52 seconds to generate all of the moves.

10.4 Practical Problems Having Intractable Solutions

The traveling salesman problem is the problem of computing the shortest path to visit n cities where each city is connected to every other city by a road. The following diagram shows the problem for n = 5 cities.

A brute-force algorithm exists which computes each possible path. There are 5 ways to choose the first city in a path, 4 ways to choose the second city, etc. Since the path from city a to city b is the same length as that from city b to city a, there are (/ (* 5 4 3 2 1) 2) paths to consider. For n cities, the brute-force program requires computing the lengths of (/ (fact n) 2) paths where:

10.4.1 fact Function

(define fact
  (lambda (n)
    (if (< n 2)
     1
     (* n (fact (- n 1))))))

If n = 20, this algorithm would require computing the lengths of 1216451004088320000 paths between cities. If a workstation can compute the lengths of 10000 paths per second, this algorithm requires approximately 38,573 centuries, 40 years, 302 days, 21 hours, 7 minutes and 12 seconds to finish.

This problem has been studied for more than 50 years and some researchers have found better than brute-force solutions, but no one has found a tractable solution yet! Research continues on this problem.

10.4.2 Minimum Covering Problem

In many manufacturing operations a sheet of material (metal, plastic, cardboard, etc.) must be cut into a given number of different shapes. Of course, the manufacturer wants to minimize the amout of waste material.

Here, the brute-force solution (consider all possible positions of the shapes) is a bit harder to describe, since the object orientation must be considered as well. This problem, as of yet, has no tractable solution.

10.4.3 Game Playing

The problem of choosing the best possible decision in a complex environment, such as business decision making, is very difficult because often the rules governing the decisions are not known or are not well understood. Researchers have studied decision making in simpler situations (that of playing games) where the rules of the game may be precisely stated.

For example, in the game of Checkers, each piece has a small number of moves. At the start of a game, black has 7 possible moves. White has 7 possble responses to some of these moves, but some starting move which black makes have only 2 reasonable responses. It is left as an exercise to the reader to consider some of these possibilities. We can organize the complexity of this decision process by drawing tree diagrams which represent the decision choices.

Samuels, at IBM Research, studied this problem and developed a program which learned to make checkers decisions by playing against a copy of the program which made random choices for moves. The program saved information about decisions which led to wins and learned to avoid decisions which lead to losses. After a learning period of time, the program was able to easily beat Samuels in Checkers games! Brute force attempts to consider all possible choices are clearly intractable.

More complex games, such as Chess, have also been studied. Heuristic algorithms (algorithms which cannot be proven to terminate in a finite amount of time or which do not necessarily lead to an optimal solution) have been used in Chess playing computer programs. Programs exist now which play almost at the Master's level using such methods.

10.5 Summary

One of the main focal points of computer science is the study of algorithms. The limits of computer science are determined largely by our success in finding tractable algorithms and programs. Occasionally we are able to prove that certain problems do not have a computable solution. An example of such a problem is the Halting problem. Given a programming language, P, it has been proved that it is not possible to write a P program which will determine whether or not any given P program halts with an answer after a finite amount of time.

Many problems remain for which only intractable solutions have been found. Such problems provide exciting and challanging research experiences for computer scientists.