Analysis of Algorithms : An Active Learning Approach

PSEUDORANDOM NUMBER GENERATION 263 repeat location =  N * RanNum() + 1  until list[location] = 0 list[location] = i end for Ev ...

264 APPENDIX B each random number generated. This reduces the chance of two locations having sequential numbers, because that wi ...

Appendix c Results of Chapter Study Suggestions This appendix gives the output that should be produced from a hand execution of ...

266 APPENDIX C Bubble Sort Pass 6:46891015161731114251213 Pass 7:14689101516731114251213 Pass 8:14678910151631114251213 Pass 9:1 ...

RESULTS OF CHAPTER STUDY SUGGESTIONS 267 Shellsort Heapsort The Original List:62471385 After using increment of 7:52471386 After ...

268 APPENDIX C Merge Sort Pass 6: 1 0897652413111213141516 Pass 7:98576324110111213141516 Pass 8:87546321910111213141516 Pass 9: ...

RESULTS OF CHAPTER STUDY SUGGESTIONS 269 Quicksort After merging loca- tion 9 to location 10: 14689101516371114251213 After merg ...

270 APPENDIX C Radix Sort Chapter 4 Original Polynomial x^3 + 4x^2
3 x + 2 Horner’s Method [(x + 4) *x
3] *x + 2 Preprocessed ...

RESULTS OF CHAPTER STUDY SUGGESTIONS 271 Preprocessed Coefficients Standard Matrix Multiplication Winograd’s Matrix Multiplicati ...

272 APPENDIX C Gauss-Jordan Method Chapter 5 Knuth-Morris-Pratt The pattern is abcabc The fail array contains 0 1 1 1 2 3 39621 ...

RESULTS OF CHAPTER STUDY SUGGESTIONS 273 Boyer–Moore The pattern is abcbccabc After the first loop the jump array contains After ...

274 APPENDIX C F G H K L F C E I D F G A B C E I B A 7 7 8 6 3 7 2 K F L H E I A B C D G 7 5 6 4 1 E I A B C D H F I J L E A B C ...

RESULTS OF CHAPTER STUDY SUGGESTIONS 275 Kruskal’s minimum spanning tree trace A B E C D K G L I H J F 5 3 4 A B A B C D E F G H ...

276 APPENDIX C Dijkstra’s shortest-path algorithm 2 A B C D E F G H I J K L 12 1 A B C D E F G H I J K L 21 14 4 3 4 2 3 2 2 3 3 ...

RESULTS OF CHAPTER STUDY SUGGESTIONS 277 5 K J 3 1 2 4 5 6 7 3 (^7) F G H L K (^8) I I B 3 7 8 3 5 F E C D 1 2 4 5 6 3 G H L E C ...

278 APPENDIX C I F J 7 3 3 8 5 (^12) 5 6 3 4 H L E C G D A B K I F J 7 3 3 8 5 5 (^12) 3 4 E C G D A B K (^6) L H I F J K 7 3 3 ...

Appendix D References Chapter 1. Analysis Basics Aho, A., Hopcroft, J., and Ullman, J. The Design and Analysis of Computer Algo- ...

280 APPENDIX D Chapter 4. Numeric Algorithms Strassen, V. “Gaussian Elimination Is Not Optimal,” Numerische Mathematik, 13, pp. ...

REFERENCES 281 Tarjan, R. “Depth-First Search and Linear Graph Algorithms,” SIAM Journal on Computing, 1(2), pp. 146–160, 1972. ...

282 APPENDIX D Karp, R. “Reducibility Among Combinatorial Problems,” in Miller, R. and Thatcher, J. (eds.), Complexity of Comput ...