Data Structures and Algorithmic Thinking With Python
Narasimha Karuminchi
0. Organization of Chapters -------------------------------------------------------------------------- 13
0. 1 Whal ls This Book About':' ------------------------------------------------------------------------------- 13
0.2 Should I Buy This Book? -------------------------------------------------------------------------------- 13
0.3 Organization of Chapters -------------------------------------------------------------------------------- 14
0.4 Some Prcrequisites --------------------------------------------------------------------------------------- 17
1. In trodu c Lion ----------------------------------------------------------------------------- ------------- 18
l. 1 Varia blcs --------------------------------------------------------------------------------------------------- 18
1.2 Datu 1'ypcs --------------- ---------------- ----------------- ------------------------------------------------- I8
1.3 Data Structures------------------------------------------------------------------------------------------- 19
1.4 Abstract Data Types {ADTs) ----------------------------------------------------------------------------- 19
l.5 Whal is an Algorithm? ----------------------------------------------------------------------------------- 19
l.6 Why the Analysis of Algorithms? ----------------------------------------------------------------------- 20
1.7 Goal or the Analysis or Algorithms --------------------------------------------------------------------- 20
1.8 Wha t is Running Time Ana lys is?----------------------------------------------------------------------- 2 0
1.9 1-fow to Compare Algorithms ---------------------------------------------------------------------------- 20
1. 10 Whal is Rate or Growth"? ------------------------------------------------------------------------------- 20
l. 11 Commonly Used Rates or Growlh--------------------------------------------------------------------- 2 1
1.1 2 Types of Ana lysis ---------------------------------------------------------------------------------------- 22
1. I3 Asymptotic Nola tion --------------------------------- --------------------------------------------------- 22
1. 14 Big-0 Notation ------------------------------------------------------------------------------------------- 22
1. 15 Omega-n Notation--------------------------------------------------------------------------------------- 24
1.16 Thela-0 Notation ---------------------------------------------------------------------------------------- 24
l.17 Why is it called Asymptotic Analysis?---------------------------------------------------------------- 25
l. 18 Guiclclincs for Asymptotic Analysis------------------------------------------------------------------- 25
l. 19 Properties or Notations --------------------------------------------------------------------------------- 27
1.20 Commonly used Logarithms and Summations----------------------------------------------------- 27
1.21 Master Theorem for Divide a nd Conquer ------------------------------------------------------------ 27
1.22 Divide and Conqu er Master Theorem: Problems & Solutions ------------------------------------ 28
1.23 Master Thcorcm for Subtrocl and Conquer Recurrences ----------------------------------------- 29
l.24 Va riant or Subtraction and Conquer Master Theorem --------------------------------------------- 29
l.25 Method or Gucssi ng and Confirming ----------------------------------------------------------------- 29
1.26 Amortized Analysis ------------------------------------------------------------------------------------- 30
1.27 Algorithms Analysis: Problcms &. Solu tions--------------------------------------------------------- 31
2. Recursion and Backtracking ----------------------------------------------------------------------42
2. l In trod uclion ------------------------------------------------------------------------------------------------ 42
2.2 What is Recursion? --------------------------------------------------------------------------------------- 42
2 .3 Why Rccu rsion? -------------------------------------------------------- ----------------------------- ------ 42
2.4 Format or a Recursive F'unction ------------------------------------------------------------------------ 42
2.5 Recursion and Memory (Visualization) ---------------------------------------------------------------- 43
2.6 Recursion versus ILeration ------------------------------------------------------------------------------ 43
2 .7 Notes on Recursion--------------------------------------------------------------------------------------- 44
2.8 Example /\lgorithms of Recursion ---------------------------------------------------------------------- 44
2.9 Recursion: Problems & Solul ions ---------------------------------------------------------------------- 44
2. I 0 What is Bucktracking?---------------------------------------------------------------------------------- 45
2 . I I Exnrnplc Algorithms of Backtracking ---------------------------------------------------------------- 45
2 . 12 Backtracking: Problems & Solutions----------------------------------------------------------------- 45
3. Linkcd Lists ----------------------------------------------------------------------------------------- 48
3.1 Whal is a Linked List?------------------------------------------------------------------------------------ 48
3.2 Li nkcd Lisls /\OT------------------------------------------------------------------------------------------ 48
3.3 Why IJinked Lisls',> ---------------------------------------------------------------------------------------- 48
3.4 /\rruys Overview -------------------------------------------- ------ --------------------------------------- 48
3.5 Compar ison of Linked Lisl s with Arrays and Dynamic Arrays------------------------------------- 50
3.6 Singly Linkeel Lists---------------------------------------------------------------------------------------- 50
3.7 Dou bly Linked Lists-------------------------------------------------------------------------------------- 56
3.8 Circular Linked Lists ------------------------------------------------------------------------------------- 6 1
3.9 A Memory efficient Doubly Linked List ---------------------------------------------------------------- 66
3. I0 Unrollccl Linked Lists ----------------------------------------------------------------------------------- 68
3. 11 Skip Lists ------------------------------------------------------------------------------------------------- 72
3. 12 Linked Lists: Problems & SoluLions ------------------------------------------------------------------ 75
4. Stack s ------------------------------------------------------------------------------------------------ 96
4. l What is a 8tuck? ------------------------------------------------------------------------------------------ 96
4.2 I low Stacks urc Used ------------------------------------------------------------------------------------- 96
4.3 Stack ADT ---------------------------------------------------------·---------------------------------------- 97
4.4 AppIiculions------------------------------------------------------------------------------------------------ 97
4.5 lmplemcnlolion -------------------------------------------------------------------------------------------- 97
4 .6 Cornparison of Implem entations----------------------------------------------------------------------- l Ol
4.7 SInckl:l: Problems & SoluLions-------------------------------------------------------------------------- 102
5. Q ucues ---------------------------------------------------------------------------------------- 1 I9
5. 1 What is u Queue? ----------------------------------------------------------------------------------------119
5.2 How arc Queues Used----------------------------------------------------------------------------------119
5.3 Queue /\OT ------------------------------------------------------------------------------------------------ 11 9
5.4 Exceptions ------------------------------------------------------------------------------------------------ 120
5.5 AppIications----------------------------------------------------------------------------------------------- l20
5.6 Implcmcn to tion-------------------------------------------------- ----------------------------------------- J20
5.7 Queues: Problems & Solutions ------------------------------------------------------------------------ 125
6. Trees ------------------------------------------------------------------------------------------------- 135
6.1 What is n Tree? ------------------------------------------------------------------------------------------- 135
6.2 GIossary --- ---------------------------------------------------------------------------- ----------------- 135
6. 3 Binary Trees ---------------------------------------------------------------------------------------------- I 36
6.4 Ty pcs of 13inury Trees ----------------------------------------------------------------------------------- 137
6.5 Propcnies of Binary Trees ----------------------------------------- ------------- ------------------ ------ 137
6.6 Binary Tree Traversals ---------------------------------------------------------------------------------- 139
6.7 Generic Trees (N-ary Trees)-------------------------------- --------------------------------------------- 159
6.8 Threaded Binary Tree Traversa ls (Stack or Queue-less Traversals)------------------------------ 166
6.9 Expression Trees ----------------------------------------------------------------------------------------- 171
6. 10 XOR Trees ----------------------------------------------------- ------------ ----------------------- ------- l 7 4
6.1 1 Binary Search Trees (BSTs) --------------------------------------------------------------------------- l 74
6.12 Ba la nced Binary Search Trees ----------------------------------------------------------------------- 189
6. 13 AVL (Adelson-Velskii and Landis) Trees ------------------------------------------------------------ 189
6.14 Other Variations on Trees -----------------------------------------------------------------------------207
7. Priority Queues and Heaps ---------------------------------------------------------------------- 211
7. 1 Whal is a Priority Queue? ------------------------------------------------------------------------------2 1 l
7. 2 PrioriLy Queue I\ OT ----------------------------------- ------------------ ---------------------------------2 L1
7.3 Priorily Queue Applications ----------------------------------------------------------------------------2 12
7.4 Priority Queue Implementations-----------------------------------------------------------------------21 2
7.5 Heaps a nd Binary Heaps -------------------------------------------------------------------------------213
7.6 Binary I leaps ---------------------------------------------------------------------------------------------2 14
7.7 Hcapsorl---------------------------------------------------------------------------------------------------2 l8
7.8 Priority Queues IHeaps): Problems & SoluLions ----------------------------------------------------- 21 9
8. Disjoint Sets ADT --------------------------------------------------------------------------------- 233
8. 1 In troduc tion-----------------------------------------------------------------------------------------------233
8 .2 Equivalence Relations and Equ ivulcncc Classes---------------------------------------------------- 233
8.3 Disjoint Scls /\OT ---------------------------------------------------------------------------------------- 234
8.4 AppIicalions----------------------------------------------------------------------------------------------- 234
8.5 Tradcoffs in Im plcmcnting Disjoint Sets /\OT ------------------------------------------------------- 234
8.8 f?ast UNION Implementation (Slow F'IND) ------------------------------------------------------------235
8.9 F'ast UNION Implementations (Quick F'IND) ---------------------------------------------------------237
8.10 Summary ------------------------------------------------------------------------------------------------240
8. I 1 Disjoint Sets: Problems & Solutions-----------------------------------------------------------------240
9. Graph J\ lgorithms --------------------------------------------------------------------------------- 242
9. 1 Introduction -----------------------------------------------------------------------------------------------242
9.2 Glossary --------------------------------------------------------------------------------------------------- 242
9. 3 Applica lions of Graphs--------- ------------------------------------------------------------------------- 245
9.4 Graph Rcprescntation ---------------------------------------------------- ------------------------------- 24 5
9.5 Graph Trave rsa ls----------------------------------------------------------------------------------------- 250
9.6 TopologicaI Sort ------------------------------------------------------------------------------------------ 2!'>6
9 .7 Shortest Pa th Algorithms ------------------------------------------------------------------------------- 258
9.8 Minimal Spanning Tree --------------------------------------------------------------------------------- 263
9. 9 Gra ph Algorithms: Problems & Solu Lions ------------------------------------------------------------267
10. Sorting ---------------------------------------------------------------------------------------------- 287
l 0. I What is 8oning? --- ------------------------------------------------------------------------------------- 287
l0.2 Why is Sorting Necessary? ----------------------------------------------------------------------------287
10 .3 Classification of Sorting Algorithms ----------------------------------------------------------------- 287
I0.4 OLhcr Classifications----------------------------------------------------------------------------------- 288
I0. 5 Bubble Sorl---------------------------------------------------------------------------------------------- 288
1O.6 ScIection Sort ------------------------------------------------------------------------------------------- 289
I0.7 Inscrtion Sort ------------------------------------------------------------------------------------------- 290
I0.8 Shell Sort --------------------------------------------------------------------------------------------- 29 I
I0.9 Merge Sort -- ------------------------------------------------------------------ --------------------------- 292
I0. I0 Hca p Sort----------------------------------------------------------------------------------------------- 294
I0.11 Quick Sort---------------------------------------------------------------------------------------------- 294
10. 12 Tree Sort------------------------------------------------------------------------------------------------ 296
I0. 13 Com pu rison of Sorting Algorilh ms -----------------------------------------------------------------296
I0.14 Lincm Sorting Algorithms --------------------------------------------------------------------------- 297
I0. I5 Counting Sort------------------------------------------------------------------------------------------ 297
J0. 16 Buckel Sort (or Bin Sort) ----------------------------------------------------------------------------297
I0. 17 Radix Sort---------------------------------------------------------------------------------------------- 298
10. 18 Topological Sort ---------------------------------------------------------------------------------------299
I0. I9 Extcrnn I Sorting---------------------------------------------------------------------------------------299
I0.20 Sorting: Problems & Solulions ----------------------------------------------------------------------300
11. Searching ------ ------------------------------------------------------------------------------------- 3 10
I I. I \Vhal is Sc:.i rch ing?-------------------- ---- -------------------------------------------------------------310
l I.2 Why do we need Searching? --------------------------------------------------------------------------310
I I. 3 Types of Searching ------------------------------------------------------------------------------------- 310
1 1.4 Unordercd Linear Search------------------------------------------------------------------------------ 3 I0
I I. 5 Sorted/Ordered Linea r Search -----------------------------------------------------------------------310
1 J. 6 Bi no ry Search ---------------------------------------------------- --------------------------------------- 3 l I
I I.7 lntcrpolation Search ----------------------------------------------------------------------------------- 312
11.8 Comparing Basic Searching Algorithms ------------------------------------------------------------312
11.9 Symbol Ta blcs a nd Hashing --------------------------------------------------------------------------3 13
I I. I0 String Scorching Algorithms ------------------------------------------------------------------------3 13
I 1.1 I Searching: Problems & SolL1lions ------------------------------------------------------------------ 3 13
12. Selection Algorilhm s IMedians] ----------------------------------------------------------------- 335
12. 1 What a rc Selection Algorithms? ----------------------------------------------------------------------335
12.2 Selection by Soni ng --------------------------------------------------------------------------- --------- 335
I2.3 Partition-based Selection Algorithm -----------------------------------------------------------------335
12.4 Linear Selccuon Algorithm - Median of Medians Algorithm -------------------------------------335
12.5 Finding the I< Smallest Elements in Sorted Order ------- ---------------------------------------- 335
12 .6 Selection Algorithms: Problems & Solu Lions -------------------------------------------------------336
13. Symbol Tables-------------------------------------------------------------------------------------- 345
l3. I Introduction ---------------------------------------------------------------------------------------------345
13.2 What arc Symbol Tables? -----------------------------------------------------------------------------345
13.3 Symbol Tubk~ ImplcmcnLatiom; ----------------------------------------------------------------------345
L3.4 Com pn rison Table of Symbols for Im plcmcnta tions ----------------------------------------------346
14. Tl ashing --------------------------------------------------------------------------------------------- 347
14. l What is Hashing?---------------------------------------------------------------------------------------347
14.2 Why Hashing?-------------------------------------------------------------------------------------------347
14.3 Has hTa ble ADT -----------------------------------------------------------------------------------------347
14.4 U nclcrsta ncling Hashing ------------------------------------------------------------------------------- 347
14.5 Com ponen ls of Hashing ------------------------------------------------------------------------------- 348
14. 6 Hash Tablc ---------------------------------------------------------------------------------------------- 348
14.7 Hash Func tion ------------------------------------------------------------------------------------------349
14.8 Load Factor----------------------------------------------------------------------------------------------350
14.9 Collisions ------------------------------------------------------------------------------------------------350
14. l 0 Collis ion Resolu Lion Techniques-------------------------------------------------------------------- 350
14. 11 Sepa ra tc Chaining ------------------------------------------------------------------------------------350
I 4. 12 0 pen Addrcssi ng --------------------------------------------------------------------------------------350
14.13 Compa rison of Collision Resolution Techniques ---------------------------------- --------------- 352
14. 14 How Hashing Gets 0(1) Complexity----------------------------------------------------------------352
14. 15 Hashing Techniques --------------- -------------------------------------------------------------------353
14.16 Proble ms for which Hash Tables a rc not ::;uitablc -----------------------------------------------353
14. 17 Bloo1n Fil lcrs ------------------------------------------------------------------------------------------ 353
14. 18 Hashing: Proble ms & Solu Lions --------------------------------------------------------------------354
15. String Algorithms --------------------------------------------------------------------------------- 362
15. l Introduction ----------- ----------------------------------------------------------------------------------362
15.2 String Match ing Algorithm::; --------------------------------------------------------------------------362
15.3 Bru tc Force Method ------------------------------------------------------------------------------------362
I 5 .4 Robin -Karp S tring Ma tc hing J\lgori thm ------------------------------------------------------------- 363
15.5 String Ma tc hing with Fin itc J\u torna ta -------------------------------------------------------------- 364
15.6 KM P Algorithm--------- --------------------------------------------------------------------------------- 365
15.7 Boyce-Moore Algorithm -------------------------------------------------------------------------------- 368
15.8 Data Struc tures for Storing Strings ----------------------------------------------------------------- 369
15.9 I lash Tables for Stri ngs-------------------------------------------------------------------------------- 369
15.1 0 Binary Sea rc h Trees for Strings --------------------------------------------------------------------369
15.11 Tries -----------------------------------------------------------------------------------------------------369
15.12 Terna ry Search Trees--------------------------------------------------------------------------------- 371
15.13 Comparing BSTs, Tries and TSTs ------------------------------------------------------------------377
15.14 Suffix Trees -------------------------------------------------------- ------------------------------------377
15. I5 String Algorithms: Problem s & Solu Lio ns ---------------------------------------------------------380
16. Algori Lh ms Design Techniques------------------------------------------------------------------ 387
16. l Introduc tion ---------------------------------------------------------------------------------------------387
16.2 Classifica lion --------------------------------------------------------------------------------------------387
16.3 Classifica Lion by Impleme nlation Me thod ----------------------------------------------------------387
16.4 Classification by Design McU1od ---------------------------------------------------------------------388
16.5 Other Classifications ----------------------------------------------------------------------------------- 389
17. Greedy Algori Ihm s -------------------------------------------------------------------------------- 390
17. I Introduction --------------------------------------------------------------------------------------------- 390
L7.2 Greedy Stra tegy-----------------------------------------------------------------------------------------390
I7.3 Elemcntl:l of Greedy Algorithms ----------------------------------------------------------------------390
17.4 Docs Greedy Always Work? ---------------------------------------------------------------------------390
17.5 Advan tages a nd Disadva ntages of Greedy Method ------------------------------------------------ 390
I 7.6 Greedy Applications------------------------------------------------------------------------------------39 1
I 7.7 Unclcrswnd ing Greedy Technique ------------------------------------------·------------------------39 1
17 .8 Greedy Algorithms: Problems & Solutions--------------------------·----------------------------·-·393
18. Divide and Conquer Algorithms----------------------------------------------------------------- 399
18. I Introduction -------------------------------------------------------------·-----·-------------------------399
18.2 Whut is Divide a nd Conquer Stratcgy?------------------------------------------·--------·-·--------399
18 .3 Docs Divide and Conquer Always Work? --------------------------------------·-··-··--------------399
18.4 Divid e t1 ncl Conquer Visun lizulion -------------------------------------------------------------------399
18.5 Underslu nd ing Divide u ncl Conquer ----------------------------------------------------------------- 400
18.6 Adva ntagcs of Divide and Conquer ------------------------------------------------------------------400
18.7 Disad vuntages of Divide and Conquer --------------------------------------------------------------4 0 I
18.8 Mnstcr Theorem ------------------------------- ---------------------------------------------------------40 I
18.9 Divide und Conquer Applications -------------------------------------------------------------------- 40 I
18. I0 Divide nnd Conquer: Problems &. Solution::; ------------------------------------------------------ 40 I
19. Dynamic Programming ---------------------------------------------------------------------------416
19. l Introduction --------------------------------------------------------------------------------------------- 4 16
19.2 Wha t is Dynamic Progra mming SLrategy? ---------------------------------------------------------- 416
19 .3 Propcrtici; of Dyna mic Programming Su·ategy -----------------------------------------------------4 16
19.4 Can Dy namic Programming Solve AU Problem :<~ -----------------------·--·----------------------- 4 16
19.5 Dynn mic Programming Approachcs ----------------------------------------------------------------- 416
19.6 Example::; of Dynamic Progra mming Algorithms --------------------------------------------------417
19.7 Understa nding Dynamic Programming ------------------------------------------------------------- 417
19.8 Longest Common Subl:lcquence ---------------------------------------------------------------------- 4 19
I 9.9 Dy namic Programming: Problems & Solutions ---------------------------------------------------- 42 1
20. ComplcxiLy Classcs--------------------------------------·----------------------·------------------ 453
20. I In I rod uc tion ---------------------------------------------------------------------·············-·········- 453
20.2 Polynomia l/ Exponential Time------------------------------------------------------------------------ 453
20. 3 What is u Decision Problem? ------------------------------------------------------------------------- 453
20.4 Decision Proced urc -------------------------------------------------------------------------------------454
20. 5 What is ::i Complexity Class? -------------------------------------------------------------------------4 54
20.6 Types of Complexity Classes -------------------------------------------------------------------------- 454
20. 7 Reductions----------------------------------------------------------------.-----------..----------------- 4 56
20.8 Complexity Classes: Problems & Solutions---------------------------------------------------------458
21. MisccI lancous Concepts -------------------------------------------------------------------------- 460
2 I . I Introduction ---------------------------------------------------------··-··········· ------------ ---------- 460
21. 2 Ilnt:l<s on Bitwi::;c Progrnmming ----------------------------------------------------------------------460
21.3 Other Programming Quc::;Lions with Solutions ----------------··-·········---------- -------------- 464
Referenccs -----------------------------------------------------------------------------------------------4 7
- Log in to post comments