Analysis of Algorithms : An Active Learning Approach

6.5 SHORTEST-PATH ALGORITHM 163 Prove whether it is always, never, or sometimes true that the order in which the nodes are adde ...

164 GRAPH ALGORITHMS clearly not the shortest path, because you can see in Fig. 6.7(a) that there is a direct path between node ...

6.5 SHORTEST-PATH ALGORITHM 165 Beginning our path at node A gives us four possible edges to consider. Of those four, the edge A ...

166 GRAPH ALGORITHMS of the other connections, we now choose node F to get Fig. 6.8(f ). You should see that even though the sel ...

6.5 SHORTEST-PATH ALGORITHM 167 In the example in Fig. 6.8, we have the full shortest-path tree for node A because our destinati ...

168 GRAPH ALGORITHMS Alter the algorithm in this section so that it efficiently determines the short- est path from the start n ...

6.6 BICONNECTED COMPONENT ALGORITHM 169 Determining the biconnected components of a network indicates how sta- ble the network c ...

170 GRAPH ALGORITHMS To accomplish this algorithm, we will keep a count of how many nodes of the graph we have visited. Each nod ...

6.6 BICONNECTED COMPONENT ALGORITHM 171 6.6.1 Determine the biconnected components of the following graphs: Write an algorithm ...

172 GRAPH ALGORITHMS 6.7 Partitioning Sets A number of algorithms need to maintain a set of values as a collection of dis- joint ...

6.7 PARTITIONING SETS 173 As was discussed, the initialize routine just sets each location of the Parent array to
1 to indicate ...

174 GRAPH ALGORITHMS FindRoot( s ) s the element whose partition root we want result = s while Parent[result] > 0 do result = ...

6.8 PROGRAMMING EXERCISES 175 what you have found. If you do this for multiple graphs for each maximum, your results will be mor ...

This page intentionally left blank ...

CHAPTER 7 Parallel Algorithms PREREQUISITES Before beginning this chapter, you should be able to Read and create algorithms Ana ...

178 PARALLEL ALGORITHMS eople have recognized for a long time that in most instances two people can accomplish a task faster tha ...

7.1 PARALLELISM INTRODUCTION 179 ■ 7.1.1 Computer System Categories Computer systems can be divided into four main categories. T ...

180 PARALLEL ALGORITHMS different perspective, we see that finding if a number is prime can be improved with this type of machin ...

7.1 PARALLELISM INTRODUCTION 181 plete computer system that could function on its own. Parallelism is achieved by the way that t ...

182 PARALLEL ALGORITHMS intermediate nodes, whereas in the ring network of Fig. 7.2, that message could now get there by passing ...