Analysis of Algorithms : An Active Learning Approach

3.10 PROGRAMMING EXERCISES 103 3.2.4. Does your test show any differences? How do your results relate to the analysis done in th ...

104 SORTING ALGORITHMS b. Bubble sort—displaying the list at the end of each pass of the outer loop c. Shellsort—displaying the ...

Chapter 4 Numeric Algorithms PREREQUISITES Before beginning this chapter, you should be able to Do simple algebra Evaluate poly ...

106 NUMERIC ALGORITHMS method and calculate the preprocessed coefficients for the polynomials x^3 + 4 x^2
3 x + 2 and x^7
8 ...

4.1 CALCULATING POLYNOMIALS 107 facturing can be moved and manipulated through matrix operations. Image analysis will use matric ...

108 NUMERIC ALGORITHMS The standard evaluation algorithm is very straightforward: Evaluate( x ) x the value to use for evaluatio ...

4.1 CALCULATING POLYNOMIALS 109 into two polynomials of lesser degree. For example, if you want to calculate x^256 , you could u ...

110 NUMERIC ALGORITHMS If we divide p(x) by x^4 + 5, we will get a quotient and remainder polynomials, and those are the values ...

4.1 CALCULATING POLYNOMIALS 111 Solving these equations we find that we will do approximately N / 2 multi- plications and (3N
1 ...

112 NUMERIC ALGORITHMS 4.2 Matrix Multiplication A matrix is a mathematical structure of numbers arranged in rows and columns th ...

4.2 MATRIX MULTIPLICATION 113 work was absolutely necessary, and they eventually found algorithms that mul- tiply matrices faste ...

114 NUMERIC ALGORITHMS for j = 2 to d do columnFactor[i] = columnFactor[i] + H2j-1,i* H2j,i end for j end for i // calculate R f ...

4.2 MATRIX MULTIPLICATION 115 ■ 4.2.2 Strassen’s Matrix Multiplication For Strassen’s algorithm, we will work with matrices that ...

116 NUMERIC ALGORITHMS Strassen’s algorithm is rarely used in actual practice because of the book- keeping necessary to use it r ...

4.3 LINEAR EQUATIONS 117 One way to try to find the value for each x would be to do substitutions of the equations. In other wor ...

118 NUMERIC ALGORITHMS The basic plan is to divide the first row by the value in the first column and then subtract multiples of ...

4.3 LINEAR EQUATIONS 119 The final matrix gives us the x values of x 1 = 2, x 2 = 4, x 3 = 3, and x 4 = 7. The problem with this ...

This page intentionally left blank ...

Chapter 5 Matching Algorithms PREREQUISITES Before beginning this chapter, you should be able to Create finite automata Use cha ...

122 MATCHING ALGORITHMS text, you should trace the straightforward algorithm and the Knuth-Morris- Pratt algorithm using the pat ...