7 Algorithm Design Paradigms

2020 by Sung-Hyuk Cha

available in (Click here for GoogleBooks Preview)

Ebook (PDF)
ISBN 978-1-7351680-0-5
available at

Softcover
ISBN 978-1-7351680-4-3
available at

Hardcover
ISBN 978-1-7351680-1-2
available at

Solution Manual is also available in (Click here for GoogleBooks Preview)

Ebook (PDF)
ISBN 978-1-7351680-2-9
available at

Softcover
ISBN 978-1-7351680-3-6
available at

Description

The intended readership includes both undergraduate and graduate students majoring in computer science as well as researchers in the computer science area. The book is suitable either as a textbook or as a supplementary book in algorithm courses. Over 400 computational problems are covered with various algorithms to tackle them. Rather than providing students simply with the best known algorithm for a problem, this book presents various algorithms for readers to master various algorithm design paradigms. Beginners in computer science can train their algorithm design skills via trivial algorithms on elementary problem examples. Graduate students can test their abilities to apply the algorithm design paradigms to devise an efficient algorithm for intermediate-level or challenging problems.

Key Features

Dictionary of Computational Problems: A table of over 400 computational problems with more than 1500 algorithms is provided. (click here for pdf)
Indices and Hyperlinks: Algorithms, computational problems, equations, figures, lemmas, properties, tables, and theorems are indexed with unique identification numbers and page numbers in the printed book and hyperlinked in the e-book version.
Extensive Figures: Over 435 figures illustrate the algorithms and describe computational problems.
Comprehensive Exercises: More than 352 exercises help students to improve their algorithm design and analysis skills. The answers for most questions are available in the accompanying solution manual.

Errata on 7 Algorithm Design Paradigms

Date Contributor Page Identifier Comment Author's response

8/2/2023 Nuvorish Paul 20 Algorithm 1.10 line 3 Infinite while loop While Flag = F & i <= n

8/2/2023 Nuvorish Paul 101 Algorithm 3.7 line 7 The search is repeated. Only "o = search(b, m-1)"

5/28/2020 Prof. Teryn Cha 156 line 12 Citation problem [?]. It should be [139].

7/19/2020 Param Puneet Kaur Thind 186 line 4 from bottom It does not match with Figure 4.29. path(v2,v6) = <v2,v3,v6>, <v2,v3,v4,v6>, <v2,v4,v6>' should be 'path(v2,v7) = <v2,v4,v7>, <v2,v4,v5,v7>, <v2,v5,v7>'

7/19/2020 Param Puneet Kaur Thind 187 line 3 It does not match with Figure 4.29. pc(<v2,v3,v4,v6>) = w(v2,v3) + w(v3,v4) + w(v4,v6)' should be 'pc(<v2,v4,v5,v7>) = w(v2,v4) + w(v4,v5) + w(v5,v7)'

7/19/2020 Param Puneet Kaur Thind 187 line 3 from bottom Dikstra' should be 'Dijkstra' Thank you.

7/19/2020 Vaibhav Kumar Katturu 217 Algorithm 5.1 Incorrect algorithm 'and j divides i' is missing in line 7.

10/11/2022 Refferty Leung 218 Theorem 5.3 line 5 in the proof(a) '16 < k-2' should be '16 <= k-2' Thank you.

7/19/2020 Vaibhav Kumar Katturu 218 Figure 5.3 (a) 'x(27) = x(24) = 3' shoud be 'y(27) = y(24) = 3' Thank you.

7/19/2020 Param Puneet Kaur Thind 221 Algorithm 5.3 Incorrect algorithm line 5: 'i - a_j > 0' should be 'i - a_j >= 0'

11/27/2022 Prof. Teryn Cha 314 Problem 6.7 eqn(6.14) "+1"'s are missing for insertion and deletion. Thank you. click here for the correct answer.

12/10/2023 Ray Jennings 315 Figure 6.13 Table cell value errors: From "T(6,6) = 4, T(7,7) = 5, and T(8,8) = 6" to "T(6,6) = 3, T(7,7) = 4, and T(8,8) = 5" Thank you. click here for the correct answer.

9/4/2020 Param Puneet Kaur Thind 363 Line 3 The string <11> is not acceptable, but <10> is possible. Thank you.

9/4/2020 Vaibhav Kumar Katturu 366 Figure 7.11 The node r should be rectangle rather than circle. click here. Thank you.

9/4/2020 Param Puneet Kaur Thind 370 Algorithm 7.12 negation symbol case is missing. Thank you. A new version with negation case will be added here soon.

9/4/2020 Param Puneet Kaur Thind 373 Algorithm 7.16 line 6: indentation not required. Thank you.

9/4/2020 Param Puneet Kaur Thind 380 Figure 7.19 The popped item in 4th Figure is v3 not v6. click here. Thank you.

9/4/2020 Param Puneet Kaur Thind 380 Figure 7.19 The popped item in 4th Figure is v3 not v6. click here. Thank you.

9/4/2020 Param Puneet Kaur Thind 389 Figure 7.19 Switch v5 and v6. click here. Thank you.

9/4/2020 Vaibhav Kumar Katturu 398 Algorithm 7.33 Line 6 the function name, KIB2 should be KB2. Thank you.

6/26/2020 Prof. Soon Ae Chun 714 Bibliographic footnote Ulam's bio has some phrases being repeated. Thank you.

5/17/2020 Prof. Teryn Cha 744 line 2 Problem title should match with Eqn (8.4). Thank you.

Date	Contributor	Page	Identifier	Comment	Author's response
8/2/2023	Nuvorish Paul	20	Algorithm 1.10 line 3	Infinite while loop	While Flag = F & i <= n
8/2/2023	Nuvorish Paul	101	Algorithm 3.7 line 7	The search is repeated.	Only "o = search(b, m-1)"
5/28/2020	Prof. Teryn Cha	156	line 12	Citation problem [?].	It should be [139].
7/19/2020	Param Puneet Kaur Thind	186	line 4 from bottom	It does not match with Figure 4.29.	path(v2,v6) = <v2,v3,v6>, <v2,v3,v4,v6>, <v2,v4,v6>' should be 'path(v2,v7) = <v2,v4,v7>, <v2,v4,v5,v7>, <v2,v5,v7>'
7/19/2020	Param Puneet Kaur Thind	187	line 3	It does not match with Figure 4.29.	pc(<v2,v3,v4,v6>) = w(v2,v3) + w(v3,v4) + w(v4,v6)' should be 'pc(<v2,v4,v5,v7>) = w(v2,v4) + w(v4,v5) + w(v5,v7)'
7/19/2020	Param Puneet Kaur Thind	187	line 3 from bottom	Dikstra' should be 'Dijkstra'	Thank you.
7/19/2020	Vaibhav Kumar Katturu	217	Algorithm 5.1	Incorrect algorithm	'and j divides i' is missing in line 7.
10/11/2022	Refferty Leung	218	Theorem 5.3 line 5 in the proof(a)	'16 < k-2' should be '16 <= k-2'	Thank you.
7/19/2020	Vaibhav Kumar Katturu	218	Figure 5.3 (a)	'x(27) = x(24) = 3' shoud be 'y(27) = y(24) = 3'	Thank you.
7/19/2020	Param Puneet Kaur Thind	221	Algorithm 5.3	Incorrect algorithm	line 5: 'i - a_j > 0' should be 'i - a_j >= 0'
11/27/2022	Prof. Teryn Cha	314	Problem 6.7 eqn(6.14)	"+1"'s are missing for insertion and deletion.	Thank you. click here for the correct answer.
12/10/2023	Ray Jennings	315	Figure 6.13	Table cell value errors: From "T(6,6) = 4, T(7,7) = 5, and T(8,8) = 6" to "T(6,6) = 3, T(7,7) = 4, and T(8,8) = 5"	Thank you. click here for the correct answer.
9/4/2020	Param Puneet Kaur Thind	363	Line 3	The string <11> is not acceptable, but <10> is possible.	Thank you.
9/4/2020	Vaibhav Kumar Katturu	366	Figure 7.11	The node r should be rectangle rather than circle. click here.	Thank you.
9/4/2020	Param Puneet Kaur Thind	370	Algorithm 7.12	negation symbol case is missing.	Thank you. A new version with negation case will be added here soon.
9/4/2020	Param Puneet Kaur Thind	373	Algorithm 7.16	line 6: indentation not required.	Thank you.
9/4/2020	Param Puneet Kaur Thind	380	Figure 7.19	The popped item in 4th Figure is v3 not v6. click here.	Thank you.
9/4/2020	Param Puneet Kaur Thind	380	Figure 7.19	The popped item in 4th Figure is v3 not v6. click here.	Thank you.
9/4/2020	Param Puneet Kaur Thind	389	Figure 7.19	Switch v5 and v6. click here.	Thank you.
9/4/2020	Vaibhav Kumar Katturu	398	Algorithm 7.33	Line 6 the function name, KIB2 should be KB2.	Thank you.
6/26/2020	Prof. Soon Ae Chun	714	Bibliographic footnote	Ulam's bio has some phrases being repeated.	Thank you.
5/17/2020	Prof. Teryn Cha	744	line 2	Problem title should match with Eqn (8.4).	Thank you.

Errata on 7 Algorithm Design Paradigms - Solution Manual

Date Contributor Page Identifier Comment Author's response

9/2/2020 Mun Jeong Lee S-8 Q 1.9 d) "Base case h = 1" should be h = 0 Thank you.

2/16/2022 Boyi Zhang S-54 Q 3.2 g) c =3/2 violates c > 1 condition "c = 3/2" should be "c = 1.5/2"

2/23/2022 Abdimanapov, Bekzhan S-102 Algorithm S-4.11. 'wi' should be 'qi'. Thank you.
2/23/2022 Liu, Kelly S-103 Problem S-4.9. '<= m' should be '>= m'. Thank you.
9/23/2020 Mun Jeong Lee S-104 Q 4.13 c) "Crab column should have amt. = 150g and fat = 13. Thank you.

8/2/2023 Nuvorish Paul S-110 Algorithm S-4.18 line 8 Invalid variable m(should be n). Thank you.

3/1/2022 Houqi Zhan S-159 Q 5.19 a) Algorithm S-5.16 line 4 should be "L(i) = L(floor((i-1)/2)+L(ceil((i-1)/2)+ floor(log i) +1" Thank you

5/21/2021 Prof. Teryn Cha S-193 Q 5.30 e) Algorithm S-5.42 line 6 should be "L[i] = 2 L[i-1] - L[i-k-1]" Thank you

5/21/2021 Prof. Teryn Cha S-193 Q 5.30 h) eqn (S-5.68) line 4 should be "T[n] = 2KBF2(n-1, k) - KBF2(n-k-1, k)" Thank you

8/2/2023 Nuvorish Paul S-198 Algorithm S-5.46 line 3 Table LT is already initialised as 0's. Either remove it or initialize LT with nil.

11/27/2022 Prof. Teryn Cha S-234 Q 6.15 d) click here for the correct answer. Thank you.

11/27/2022 Prof. Teryn Cha S-236 Q 6.16 d) click here for the correct answer. The original one is also a possible answer but the provided one matches with the table in c). Thank you.

5/1/2022 Liu, Kelly S-264 Q 7.1 b) click here for the correct answer. Thank you.

5/1/2022 Liu, Kelly S-266 Q 7.2 b) click here for the correct answer. Thank you.

8/2/2023 Nuvorish Paul S-302 Algorithm S-7.41 line 1 Illustration in b) is - inf while it states 0. Change line 1 to initially - inf from 0.

4/10/2022 Liu, Kelly S-375 Q 9.7 a) The second tree in the second row. The node 20 should be 12. Thank you

4/6/2022 Liu, Kelly S-377 Q 9.8 e) min_k(A_{1~i}) column has wrong answers. They should be the same as the first element in the array or the root node.

4/10/2022 Liu, Kelly S-411 Q 10.2 f) The toy example does not match. Change "A = <2.0, 0.5, 4.0" to "A = <2.0, 0.5, 5.0"

4/10/2022 Liu, Kelly S-412 Algorihtm S10.7 Method name should be 'SKSSmin' and line 3 should 'SKSPmin'. Thank you

10/28/2020 Mun Jeong Lee S-417 Algorithm S-10.21 does not match with Figure S-10.1. line 5 should be o_{3i-1} = a'_{r + \floor{n/3} + i} line 6 should be o_{3i} = a'_{r + 2\floor{n/3} + i}

11/4/2020 Mun Jeong Lee S-497 eqn S-11.3 Wrong equation. Oplus symbol should be biconditional symbol. O = CEU_algox should be removed as well.

4/27/2022 Liu, Kelly S-547 Q 12.13 b) The pivot is 17 in the odd length case: A. click here for the correct answer. Thank you.

4/27/2022 Liu, Kelly S-548 Algorithm S-127 "quick_updown" should be "quick_downup" in lines 12 and 15. Thank you.

4/27/2022 Liu, Kelly S-549 Q 12.14 c) 10 is not in the list. Change the pivot to be 17. After partitioning, <15, 12, 2, 1, 17, 35, 80, 30, 20> and after the interweaving, it should be <17, 15, 35, 12, 80, 2, 30, 1, 17>.

4/27/2022 Liu, Kelly S-549 Q 12.14 e) 10 is not in the list. Change the pivot to be 15. After partitioning, <1, 12, 2, 15, 20, 35, 17, 30, 80> and after the interweaving, it should be <20, 1, 35, 12, 17, 2, 30, 15, 80>.

Date	Contributor	Page	Identifier	Comment	Author's response
9/2/2020	Mun Jeong Lee	S-8	Q 1.9 d)	"Base case h = 1" should be h = 0	Thank you.
2/16/2022	Boyi Zhang	S-54	Q 3.2 g)	c =3/2 violates c > 1 condition	"c = 3/2" should be "c = 1.5/2"
2/23/2022	Abdimanapov, Bekzhan	S-102	Algorithm S-4.11.	'wi' should be 'qi'.	Thank you.
2/23/2022	Liu, Kelly	S-103	Problem S-4.9.	'<= m' should be '>= m'.	Thank you.
9/23/2020	Mun Jeong Lee	S-104	Q 4.13 c)	"Crab column should have amt. = 150g and fat = 13.	Thank you.
8/2/2023	Nuvorish Paul	S-110	Algorithm S-4.18 line 8	Invalid variable m(should be n).	Thank you.
3/1/2022	Houqi Zhan	S-159	Q 5.19 a) Algorithm S-5.16	line 4 should be "L(i) = L(floor((i-1)/2)+L(ceil((i-1)/2)+ floor(log i) +1"	Thank you
5/21/2021	Prof. Teryn Cha	S-193	Q 5.30 e) Algorithm S-5.42	line 6 should be "L[i] = 2 L[i-1] - L[i-k-1]"	Thank you
5/21/2021	Prof. Teryn Cha	S-193	Q 5.30 h) eqn (S-5.68)	line 4 should be "T[n] = 2KBF2(n-1, k) - KBF2(n-k-1, k)"	Thank you
8/2/2023	Nuvorish Paul	S-198	Algorithm S-5.46 line 3	Table LT is already initialised as 0's.	Either remove it or initialize LT with nil.
11/27/2022	Prof. Teryn Cha	S-234	Q 6.15 d)	click here for the correct answer.	Thank you.
11/27/2022	Prof. Teryn Cha	S-236	Q 6.16 d)	click here for the correct answer.	The original one is also a possible answer but the provided one matches with the table in c). Thank you.
5/1/2022	Liu, Kelly	S-264	Q 7.1 b)	click here for the correct answer.	Thank you.
5/1/2022	Liu, Kelly	S-266	Q 7.2 b)	click here for the correct answer.	Thank you.
8/2/2023	Nuvorish Paul	S-302	Algorithm S-7.41 line 1	Illustration in b) is - inf while it states 0.	Change line 1 to initially - inf from 0.
4/10/2022	Liu, Kelly	S-375	Q 9.7 a)	The second tree in the second row. The node 20 should be 12.	Thank you
4/6/2022	Liu, Kelly	S-377	Q 9.8 e)	min_k(A_{1~i}) column has wrong answers.	They should be the same as the first element in the array or the root node.
4/10/2022	Liu, Kelly	S-411	Q 10.2 f)	The toy example does not match.	Change "A = <2.0, 0.5, 4.0" to "A = <2.0, 0.5, 5.0"
4/10/2022	Liu, Kelly	S-412	Algorihtm S10.7	Method name should be 'SKSSmin' and line 3 should 'SKSPmin'.	Thank you
10/28/2020	Mun Jeong Lee	S-417	Algorithm S-10.21	does not match with Figure S-10.1.	line 5 should be o_{3i-1} = a'_{r + \floor{n/3} + i} line 6 should be o_{3i} = a'_{r + 2\floor{n/3} + i}
11/4/2020	Mun Jeong Lee	S-497	eqn S-11.3	Wrong equation.	Oplus symbol should be biconditional symbol. O = CEU_algox should be removed as well.
4/27/2022	Liu, Kelly	S-547	Q 12.13 b)	The pivot is 17 in the odd length case: A. click here for the correct answer.	Thank you.
4/27/2022	Liu, Kelly	S-548	Algorithm S-127	"quick_updown" should be "quick_downup" in lines 12 and 15.	Thank you.
4/27/2022	Liu, Kelly	S-549	Q 12.14 c)	10 is not in the list.	Change the pivot to be 17. After partitioning, <15, 12, 2, 1, 17, 35, 80, 30, 20> and after the interweaving, it should be <17, 15, 35, 12, 80, 2, 30, 1, 17>.
4/27/2022	Liu, Kelly	S-549	Q 12.14 e)	10 is not in the list.	Change the pivot to be 15. After partitioning, <1, 12, 2, 15, 20, 35, 17, 30, 80> and after the interweaving, it should be <20, 1, 35, 12, 17, 2, 30, 15, 80>.