outline

Figure2.10

• 
• Algorithm to find the largest value in a list

• Figure2.10
• 

Figure2.11

• 
• First draft of the pattern-matching algorithm

Desigman "Genes"

• Genes: Sequence of nucleotides
• Human genome: over 100,000 genes => 3.5 billion nucle.
• A genes ~= over 10,000 nucleotides
• A probe: search pattern for a gene
• ex: Genome: ...TCAGGCTAATCG...
  Probe: TAATC
• A pattern matching problem.
• Matching process
  • step 1: T1 T2 T3 T4 T5 ... -> source
    P1 P2 P3 ... -> target
  • Step 2: T1 T2 T3 T4 T5 ...
    -------->P1 P2 P3
    slide

Analysis of Algorithms

• Sequential Search for n items
  • unit of work = compares
• Best case: 1 (first item)
• Worst case: n (last or missing item)
• Average case: n/2
• Housekeeping (advancing index)
  • a constant multiple

Figure 3.6

• 
• Work = 2n

Figure 3.7

• 
• Work = cn for various values of c

Figure 3.8

• 
• Growth of Work = cn,br>for Various values of c

Order of magnitude

• Sequential search is linear:0(n)
  • shape of graph
  • constant does not affect shape
• Processing 2-D table is quadratic
  • o(n²)
  • shape of graph
• 0(n²) always gets bigger than 0(n) eventually

Figure 3.10

• 
• Work = cn²for carious values of c

Figure 3.11

• 
• A comparison of n and n²

Comparison

• Pentium Pro 200 runs at bout 75 megaflops (75 million floating-point operations per second
• Cray T3E-900 can achieve speeds of 670 gigaflops (670 billion floating-point operations per second
• Race between Tortoise and Hare
• Pentuim runs the 0(n) algorithm and the Cray runs the 0(n²) algorithm

Comparison 2

• timing result:
  

  n	Pc	Cray
  750	0.00001 sec	0.00000084 sec
  7,500	0.0001 sec	0.000084 sec
  75,000	0.001 sec	0.0084 sec
  750,000	0.01 sec	0.84 sec
  7,500,000	0.1 sec	84 sec
  75,000,000	1 sec	8400 sec = 2.3 hr
  750,000,000	10sec	840,000 sec = 9.7 days

Comparison 3

• At beginning the Cray has the lead, but by the end the Pentium surpassed the Cray
• "The order of magnitude of the algorithm being executed can play a more important role than the raw speed of the computer.

Figure 3.13

• 
• A Comparison of two extreme 0(n²) and 0(n) algorithms

Selection Sort

• Input: unsorted list
• Output: sorted list
• Algorithm
  • find max value in unsorted section
  • swap with last value in unsorted section

Selection Sort Algorithm

• 1. Get values for n and the n list items
• 2. Set the marker for the unsorted section at the end of the list
• 3. Repeat step 4 through 6 until the unsorted section of the list is empty
  • 4. Select the largest number in the unsorted section of the list
  • 5. Exchange this number with the last number in the unsorted list
  • 6. Move the marker for the unsorted section forwards one position
• 7. Stop

Sort Example

•      output               input
      2 3 5 7 8  <---   5 7 2 8 3
  

• Unsorted List	Sorted List
  5 7 2 8 3
  5 7 2 8 3
  5 7 2 3	8
  5 2 3	7 8
  2 3	5 7 8
  2	3 5 7 8
  	2 3 5 7 8

Explanation of example

• To put 8 in place in the list 5, 7, 2, 8, 3 |
• Compare 5 (largest so far) to 7
  • 7 becomes largest so far
• Compare 7 (largest so far) to 2
• Compare 7 (largest so far) to 8
  • 8 becomes largest so far
• Compare 8 to 3
• Total number of comparisons: 4 (which is 5 - 1)

Explanation of example 2

• To put 7 in place in the list 5, 7, 2, 3 | 8
• Compare 5 (largest so far) to 7
  • 7 becomes largest so far
• Compare 7 to 2
• Compare 7 to 3
• 7 is the largest
• Total number of comparisons: 3 (Which is 5 - 2)

Explanation of example 3

• To put 5 in place in the list 5, 3, 2 | 7, 8
• Compare 5 (largest so far) to 3
• Compare 5 to 2
• 5 is the largest
• Total number of comparison: 2 (which is 5 - 3)

Explanation of example 4

• To put 3 in place in the list 2, 3 | 5, 7, 8
• Compare 2(largest so far) to 3
• 3 is the largest
• Total number of comparisons: 1 (which is 5 - 4)

Selection Sort Analysis

• Work unit = comparisons
  • done in finding maximum element
• (n -1) + (n - 2) + ... + 1
  • (1/2)n² - (1/2)n + swapping
  • 0(n²)

Binary Search algorithm

• Requires sorted list
• Work unit = compares
• Compare at successive minpoints as list gets cut in half
• Work = number of times n is divisible by 2 = log₂(n) = lg n
• lg n = 0(lg n)
  • shape of curve

Binary Search Algorithm (list must be sorted)

• 1. Get values for NAME, n, N₁, ..., N_n and T₁, ..., T_n
• 2. Set the value of beginning to 1 and set the value of Found to NO
• 3. Set the value of end to n
• 4. Repeat steps 5 through 10 until either Found = YES or end is less than beginning

Binary Search Algorithm (list must be sorted) 2

• • 5. Set the value of m to the middle value between beginning and end.
  • 6. If NAME is equal t N_m, then name found at the midpoint between beginning and end, then do step 7 and 8
  • 7. Print the telephone number of that person, T_m
  • 8. Set the value of Found to YES

Binary Search Algorithm (list must be sorted) 3

• • 9. Else if NAME precedes N_m alphabetically, then set end = m - 1
  • 10. Else (NAME foloows N_m alphabetically) set beginning = m + 1
• 11. If (Found = NO) then print the message 'I am sorry but that name is not in the directory'
• 12. Stop

Figure 3.20

• 
• Binary Search Tree for a Seven-Element List

Figure 3.21

• 
• Values for n and lg n

Figure 3.22

• 
• A Comparison of n and lg n

Figure 3.23

• 
• Order-of-Magnitude Time Efficiency Summary

Orders of magnitude

• 0(n²) = walking
• 0(n) = driving
• 0(lg n) = flying

Brute force algorithm

• Hamiltonian circuit problem
• Trace all paths in a graph
  • work unit = examine path
  • suppose only 2 choices per node
  • 2ⁿ paths, exponential
• 0(2ⁿ)
• Too costly, too slow, impractical

Figure 3.24

• 
• Four Connected Cities

Figure 3.25

• 
• Hamiltonian Circuits among all paths from A in figure 3.24 with four links

Explanation

• For n-node city, the bottom of the tree has 2ⁿ nodes ans 2ⁿ path to examine
• 0(2ⁿ) ==> exponential

Figure 3.26(a)

• 
• Comparisons of lg n, n², and 2ⁿ

Figure 3.27

• 
• A comparison of four orders of magnitude

Orders of Magnitude - 2

• 0(lg n) = flying
• 0(n) = driving
• 0(n²) = walking
• 0(n³) = crawling
• 0(n⁴) = barely moving
• 0(n⁵) = no visible progress
• 0(2ⁿ) = forget it, it will never happen