Analysis of Algorithms : An Active Learning Approach

7.6 PARALLEL NUMERICAL ALGORITHMS 203 Analysis This process took seven cycles to multiply a 2  3 matrix by a 3  4 matrix. Ther ...

204 PARALLEL ALGORITHMS would do 32,258,000 multiplications, each one in a separate processor cycle for 32,258,000 cycles. Using ...

7.6 PARALLEL NUMERICAL ALGORITHMS 205 ■ 7.6.3 Solving Systems of Linear Equations with an SIMD Algorithm In Section 4.3, we look ...

206 PARALLEL ALGORITHMS end if end for z end for y Parallel End end for x In this algorithm, the outer loop steps through each o ...

7.7 PARALLEL GRAPH ALGORITHMS 207 7.7 Parallel Graph Algorithms To explore parallel graph algorithms, we will use the representa ...

208 PARALLEL ALGORITHMS matrix with the shortest paths through the entire graph because any path with N or more edges must inclu ...

7.7 PARALLEL GRAPH ALGORITHMS 209 than the number of nodes minus 1. For the graph in Fig. 7.6, we would have all of the shortest ...

210 PARALLEL ALGORITHMS nodev, and distance(vi,vj), which gives the shortest distance between nodesvi and vj. Formally, this alg ...

7.7 PARALLEL GRAPH ALGORITHMS 211 take two cycles. The last parallel block takes one comparison to see if the new node is in the ...

212 PARALLEL ALGORITHMS Formally rewrite the standard sequential matrix multiplication to calculate the shortest path as descri ...

CHAPTER 8 Nondeterministic Algorithms PREREQUISITES Before beginning this chapter, you should be able to Write and explain an a ...

214 NONDETERMINISTIC ALGORITHMS p to now, all of the algorithms we have considered have solved their problems in a reasonable am ...

8.1 WHAT IS NP? 215 that we have considered had complexity in O(N^3 ).^1 In fact, the most time- complex algorithm we examined w ...

216 NONDETERMINISTIC ALGORITHMS these cities. The goal is to determine the order we should visit all of the cities (once), retur ...

8.1 WHAT IS NP? 217 algorithm produces, you might find that the paths you put together take you to a node more than once. The se ...

218 NONDETERMINISTIC ALGORITHMS in polynomial time and the second problem can be solved in polynomial time, we know that our new ...

8.1 WHAT IS NP? 219 We show that a problem is NP-complete by showing that every other prob- lem in the class NP can be transform ...

220 NONDETERMINISTIC ALGORITHMS another NP-complete problem, to them. A 1979 book by Garey and Johnson lists hundreds of problem ...

8.2 TYPICAL NP PROBLEMS 221 associating with each node of the graph a different color, usually represented by some integer. The ...

222 NONDETERMINISTIC ALGORITHMS pack materials as efficiently as possible, and to the production of custom- ordered pieces of so ...