Andrew Gaun

Betson Thomas

I would like to thank Andrew Gaun and Betson Thomas for helping to update the Algorithm Repository and for various odd jobs in the creation of this book.

Also thanks to all the people who helped create the Algorithm Repository for the first edition.

David Gries offered valuable feedback well beyond the call of duty. Himanshu Gupta and Bin Tang bravely taught courses using a manuscript version of this edition. Thanks also to my Springer-Verlag editors, Wayne Wheeler and Allan Wylde

A select group of algorithmic sages reviewed sections of the Hitchhiker's
guide, sharing their wisdom and alerting me to new developments.

Thanks to:

Ami Amir, Herve Bronnimann, Bernard Chazelle, Chris Chu, Scott Cotton,

Yefim Dinitz, Komei Fukuda, Michael Goodrich, Lenny Heath, Cihat Imamoglu,

Tao Jiang, David Karger, Giuseppe Liotta, Albert Mao, Silvano Martello,

Catherine McGeoch, Kurt Mehlhorn, Scott A. Mitchell, Naceur Meskini, Gene Myers,

Gonzalo Navarro, Stephen North, Joe O'Rourke, Mike Paterson, Theo Pavlidis,

Seth Pettie, Michel Pocchiola, Bart Preneel, Tomasz Radzik, Edward Reingold,

Frank Ruskey, Peter Sanders, Joao Setubal, Jonathan Shewchuk, Robert Skeel,

Jens Stoye, Torsten Suel, Bruce Watson, and Uri Zwick.

Several exercises in this book were originated by colleagues or inspired by other texts. Reconstructing the original sources years later can be challenging, but credits for each problem (to the best of my recollection) appear below. Thanks to all, and I apologize in advance for any errors or omissions.

Chapter 1

1.7 | Parberry, section 5.2 problem 267 and section 6.2 problem 305 |

1.10 | Parberry, section 2.1 problem 1 |

1.11 | Parberry, section 2.1 problem 2 |

1.12 | Parberry, section 2.1 problem 3 |

1.13 | Parberry, section 2.1 problem 6 |

1.14 | Parberry, section 2.1 problem 9 |

1.15 | Parberry, section 2.1 problem 12 |

1.16 | Parberry, section 2.4 problem 27 |

1.17 | Parberry, section 2.11 problem 76 |

1.18 | Brassard and Bratley, problem 1.21 |

1.19 | Schaffer, chapter 2 problem 2.21 |

1.20 | Shaffer, chapter 2 problem 2.22 |

1.21 | Shaffer, chapter 2 problem 2.23 |

1.22 | Shaffer, chapter 2 problem 2.24 |

1.23 | Shaffer, chapter 2 problem 2.18 |

1.24 | Shaffer, chapter 2 problem 2.20 |

1.25 | Brassard and Bratley, problem 2.6 |

1.30 | http://www.techinterviews.com/?p=325 |

1.31 | http://www.gamedev.net/community/ forums/topic.asp?topic_id=299692 |

1.32 | http://www.acetheinterview.com/ questions/cats/index.php/ microsoft_google/page/2/ |

1.33 | http://www.acetheinterview.com/ questions/cats/index.php/ microsoft_google/page/4/ |

1.34 | http://www.acetheinterview.com/ questions/cats/index.php/ microsoft_google/page/4/ |

Chapter 2

2.1 | Parberry, section 6.1, problem 280. |

2.2 | Parberry, section 6.1 problem 281 |

2.3 | Parberry, section 6.1 problem 282 |

2.4 | Parberry, section 6.1 problem 283 |

2.5 | Baase, problem 1.13 |

2.6 | Parberry, section 5.1 problem 260 |

2.7 | CLR, problem 2.1-4 |

2.8 | Shaffer, chapter 3, problem 3.8 |

2.9 | Parberry, section 3.1 problem 100-107 |

2.10 | Parberry, section 3.3 problem 139 |

2.11 | Parberry, section 3.3 problem 140 |

2.12 | Parberry, section 3.3 problem 165, 166,168 |

2.13 | Parberry, section 3.4 problem 171 |

2.14 | Parberry , section 3.4 problem 172 |

2.15 | Parberry, section 3.4 problem 177 |

2.16 | Parberry, section 3.3 problem 135 |

2.17 | CLR, problem 2.1-2 |

2.18 | Baase, problem 1.16 |

2.19 | Parberry, section 3.1 problem 1 |

2.20 | Parberry, section 3.6 problem 197-200 |

2.21 | Parberry, section 3.3 problem 110 |

2.22 | Parberry, section 3.2 problem 127 |

2.32 | Manber, problem 2.6 |

2.33 | Manber problem 2.11 |

2.39 | Brassard and Bratley, problem 1.15 |

2.40 | Baase, problem 1.27 |

2.41 | Parberry, section 2.13 problem 92 |

2.42 | Skiena, problem 2-8 |

2.48 | http://www.techinterviews.com/?p=325 |

2.49 | http://www.ocf.berkeley.edu/~wwu/ cgi-bin/yabb/YaBB.cgi?board=riddles_cs; action=display;num=1163814740 |

Chapter 3

3.1 | Shaffer, chapter 1 problem 1.13 |

3.2 | Manber problem 4.2 |

3.3 | Modified from Shaffer, problem 14.16 |

3.4 | Parberry, section 11.5 problem 565 |

3.5 | Shaffer, chapter 5 problem 5.4 |

3.8 | Parberry, section 11.5 problem 567 |

3.9 | Manber, problem 4.19 |

3.10 | Parberry, section 11.5 problem 570 |

3.11 | Parberry, section 11.5 problem 575-576 |

3.12 | Manber, problem 5.21 |

3.13 | Manber, problem 4.27 |

3.14 | Manber problem 4.28 |

3.18 | http://www.techinterviews.com/?p=325 |

3.19 | http://www.techinterviews.com/?p=325 |

3.20 | http://www.ocf.berkeley.edu/~wwu/ cgi-bin/yabb/YaBB.cgi?board=riddles_cs; action=display;num=1163814740 |

3.21 | http://www.ocf.berkeley.edu/~wwu/ cgi-bin/yabb/YaBB.cgi?board=riddles_cs; action=display;num=1163814740 |

3.23 | www.sellsbrothers.com/fun/msiview/ question.htm |

3.26 | www.sellsbrothers.com/fun/msiview/ question.htm |

3.28 | http://gurus.wordpress.com/2007/06/28/ algorithm-challenge-1-no-division/ |

Chapter 4

4.7 | Baase, problem 2.30 |

4.8 | Manber, problem 6.22 |

4.9 | Manber, problem 6.25 |

4.11 | Manber, problem 6.61 and Brassard and Bratley, problem 7.35 |

4.12 | Parberry, section 13.1 problem 608 |

4.14 | CLR, problem 7.5-6 |

4.15 | Baase, problem 1.11 and 3.7 |

4.17 | Parberry, section 7.5 problems 344, 345. |

4.18 | Baase, problem 2.38 |

4.19 | Baase, problem 2.9 |

4.20 | Baase, problem 2.33 |

4.22 | Parberry, section 13.1 problem 607 |

4.23 | Manber, problem 6.32 |

4.32 | Manber, problem 6.1 and 6.2 |

4.35 | Baase, problem 2.41 |

4.38 | Shaffer, project 9.3 |

4.40 | http://careers.cse.sc.edu/googleinterview |

4.41 | http://www.sellsbrothers.com/fun/msiview /default.aspx?content=question.htm |

4.42 | www.sellsbrothers.com/fun/msiview/ question.htm |

4.44 | http://www.ocf.berkeley.edu/~wwu/ cgi-bin/yabb/YaBB.cgi?board=riddles_cs; action=display;num=1163814740 |

Chapter 5

5.3 | Parberry, section 2.11 problem 80 |

5.4 | Baase, problem 4.23 |

5.5 | Baase, problem 9.16 |

5.12 | CLR, problem 23.1-5 |

5.13 | Manber, problem 7.108 and 7.109. and CLR, problem 37.1-3 |

5.16 | Manber, problem problem 7.113 |

5.17 | Baase, problem 8.24 |

5.21 | Manber, problem 7.42 |

5.22 | Manber, problem 7.82 |

5.23 | Parberry, section 13.6 problem 667-668 |

5.24 | Corman new edition |

5.26 | Baase, problem 4.57 |

5.27 | Parberry, section 2.10 problem 68 and Brassard and Bratley, problem 9.39 |

Chapter 6

6.1 | Parberry, section 9.3 problem 438-440. |

6.4 | Shaffer, chapter 7 problem 7.20 |

6.5 | Shaffer, chapter 7 problem 7.22 |

6.10 | Manber, problem 7.71 and 7.72. |

6.11 | Parberry, section 9.3 problem 449 |

6.13 | Parberry, section 11.4 problem 562 |

6.14 | Shaffer, chapter 7 problem 7.13 |

6.15 | Manber, problem 7.7 |

6.16 | Manber, problem 7.12 |

6.17 | Parberry, section 9.3 problem 448 |

6.20 | Parberry, section 9.2 problem 436 |

6.21 | Manber, problem 7.50 |

6.22 | Manber, problem 7.48 |

6.23 | Parberry, section 8,5 problem 416 |

6.24 | Manber, problem 7.95 |

6.25 | Manber, problem 7.107 |

Chapter 7

7.14 | http://careers.cse.sc.edu/googleinterview |

7.18 | http://www.techinterviews.com/?p=325 |

Chapter 8

8.2 | Baase, problem 6.17 |

8.3 | Baase, problem 6.16 |

8.4 | Manber, problem 6.51 |

8.5 | Brassard and Bratley, problem 6.21 |

8.8 | Parberry, section 9.5 problem 473 |

8.10 | Baase, problem 6.18 |

8.11 | Bill Gasarch |

8.12 | Parberry, section 8.5 problem 410 |

8.14 | Bill Gasarch |

8.15 | Bill Gasarch |

8.20 | Parberry, section 13.6 problem 656 |

8.23 | Bill Gasarch |

8.24 | http://www.ocf.berkeley.edu/~wwu/ cgi-bin/yabb/YaBB.cgi?board=riddles_cs; action=display;num=1163814740 |

Chapter 9

9.1 | Manber, problem 11.4 |

9.2 | Manber, problem 11.5 |

9.13 | Garey and Johnson, pg. 64 |

9.14 | Garey and Johnson, pg. 64 |

9.15 | Garey and Johnson, pg. 75 |

9.16 | Garey and Johnson, pg. 75 |

9.17 | Garey and Johnson, pg. 75 |

9.19 | Garey and Johnson, pg. 75 |

9.20 | Garey and Johnson, pg. 75 |

9.27 | Vazirani, problem 2.1 |

9.29 | Vazirani 9.1 |

9.30 | Vazirani, problem 2.6 |