CPS 1 - Spring, 1997 - Ramm 4/14/97 #34
- Announce
- Read Chapter 11, Program Execution Time
- Quiz Wednesday
- Lab Finals start Thursday; Sample on Web
Chapter 10. Language Translation
- Language Translation Demo
Chapter 11. Program Execution Time
- On the Limitations of Computer Science
Reasons for failure
- runs too long
- real time requirements
- predicting yesterday's weather
- Non-computable
- Don't know the algorithm
- Complexity, N
- Tractable and Intractable
- Study of a Sorting Algorithm
- Sorting, Ordering
- Alphabetizing
- Selection Sort
- N items in an array named Data
[ 2 | 4 | 7 | 3 | 1 | 8 | 5 ]
- Find smallest of elements 1 thru N of Data
- Interchange this with 1st element of array Data
[ _ | _ | _ | _ | _ | _ | _ ]
- Find smallest of elements 2 thru N of Data
- Interchange this with 2nd element of array Data
[ _ | _ | _ | _ | _ | _ | _ ]
- ...
- Find smallest of elements K thru N of Data
- Interchange this with Kth element of array Data
[ _ | _ | _ | _ | _ | _ | _ ]
[ _ | _ | _ | _ | _ | _ | _ ]
[ _ | _ | _ | _ | _ | _ | _ ]
- Done when K = N
[ _ | _ | _ | _ | _ | _ | _ ]
- How Many Operations?
- Comparisons
- N-1 comparisons in first pass
- N-2 comparisons in first pass
- ...
- 1 comparisons in last pass
- N-1 + N-2 + N-3 + ... 2 + 1
- N*(N-1)/2 = N*N/2 - N/2 (Gauss)
- What does Order N Square Mean?
- Examples
- Various values of N
-
| N | N*N/2 | -N/2 | comparisons
|
| 2 | 2 | -1 | 1
|
| 3 | 4.5 | -1.5 | 3
|
| 4 | 8 | -2 | 6
|
| 6 | 18 | -3 | 15
|
| 8 | 32 | -4 | 28
|
| 10 | 50 | -5 | 45
|
| 20 | 200 | -10 | 190
|
| 40 | 800 | -20 | 780
|
| 100 | 5000 | -50 | 4950
|
| 200 | 10000 | -100 | 9900
|
| 1000 | 500000 | -500 | 499500
|
| ________ | ____________ | ________ | ____________
|
| ________ | ____________ | ________ | ____________
|
| ________ | ____________ | ________ | ____________
|
| ________ | ____________ | ________ | ____________
|
- t = A * N * N = A * N^2
- Linear Time Algorithms
- Add elements of an array
- Single loop algorithms
- t = A * N
- Cubic Time Algorithms
- matrix multiplication
- t = A * N^3
- Polynomial Time
- t = A * N^K
- and in-between
- Faster machines make a lot of difference
- Quicksort
- t = A * N * log(N)
- logarithmic behavior