Alt Text Long Description

Figure 1.1: Line graph comparing two mathematical functions over an x-axis ranging from 1 to 5 and a y-axis ranging from 0 to 30. A solid black line represents the quadratic function $n^2+1$, which starts near 2 at $n=1$ and curves sharply upward to nearly 30 at $n=5$. A dotted black line represents the linear function $2n+1$, which increases steadily from 3 at $n=1$ to about 10 at $n=5$. The two lines intersect at $n=2$ with a y-value of 5.

Figure 1.2: A is a Line graph comparing a quadratic function and a linear function over an x-axis ranging from 1 to roughly 200, with labeled increments every 8 units (e.g., 1, 9, 17, 25… up to 193). The y-axis ranges from 0 to 45,000 in increments of 5,000. A solid black line represents the quadratic function $n^2$, which starts at 1, curves upward, and reaches nearly 40,000 by the end of the chart. A dotted black line represents the linear function $64n$, which increases at a constant, steady rate from 64 to approximately 13,000. The two lines intersect near $n = 64$ at a y-value of approximately 4,096. B is a Line graph comparing a quadratic function and a linear function over a short range where the x-axis runs from 1 to 10 in increments of 1. The y-axis ranges from 0 to 700 in increments of 100. A dotted black line represents the linear function $64n$, which climbs steeply and steadily from 64 at $n = 1$ to 640 at $n = 10$. A solid black line represents the quadratic function $n^2$, which remains very low, curving slowly from 1 at $n = 1$ to just 100 at $n = 10$, tracking far below the linear line across the entire displayed range.

Figure 2.2: A diagram illustrating a computer memory stack. It shows a single rectangular block representing a call stack frame, labeled on the left as ‘main’. Inside the block, the text reads ‘result: 0’. To the right of the block, a bracket encompasses it with the explanatory label, ‘Stack frame for “main”‘.

Figure 2.3: A diagram showing a call stack with two stack frames stacked vertically. The bottom frame is labeled ‘main’ on the left, contains the variable ‘result: 0’, and has a bracket on the right labeled ‘Stack frame for “main”‘. Directly above it sits a second rectangular frame labeled ‘recursiveMultiplyBy2’ on the left. This top frame contains the parameter ‘n: 3’ and has a bracket on the right labeled ‘Stack frame for recursiveMultiplyBy2’.

Figure 2.4: A diagram showing a call stack with three stack frames stacked vertically, demonstrating recursive function calls. The bottom frame is labeled ‘main’ on the left, containing the variable ‘result: 0’. The middle frame is labeled ‘recursiveMultiplyBy2’ on the left, containing the parameter ‘n: 3’. The top frame is also labeled ‘recursiveMultiplyBy2’ on the left, containing the parameter ‘n: 2’.

Figure 2.5: A diagram showing a call stack with five stack frames stacked vertically, illustrating a recursive function reaching its base case. The bottom frame is labeled ‘main’ on the left, containing ‘result: 0’. The second frame from bottom is labeled ‘recursiveMultiplyBy2’ on the left, containing ‘n: 3’. The third frame from bottom is labeled ‘recursiveMultiplyBy2’ on the left, containing ‘n: 2’. The fourth frame from bottom is labeled ‘recursiveMultiplyBy2’ on the left, containing ‘n: 1’. The top frame is labeled ‘recursiveMultiplyBy2’ on the left, containing ‘n: 0’. To the right of this top frame, text reads ‘Base Case 0 is returned’.

Figure 2.6: A diagram showing a call stack as a recursive function begins to unwind, captioned at the top with ‘Stack frame is popped’.The stack contains five levels stacked vertically. The bottom frame i labeled ‘main’ on the left, containing ‘result: 0’.The second, third, and fourth frames are each labeled ‘recursiveMultiplyBy2’ on the left, containing parameters ‘n: 3’, ‘n: 2’, and ‘n: 1’ respectively.The top frame is labeled ‘recursiveMultiplyBy2’ with ‘n: 0’ and the note ‘Base Case 0 is returned’. This entire top level is greyed out to indicate it is being removed from the stack. A curved grey arrow points from the greyed-out base case down to the level beneath it (n: 1), where text notes ‘2 + 0 is calculated’.

Figure 2.7: A diagram showing a call stack as a recursive function continues to unwind, captioned at the top with ‘Stack frame is popped’. The stack contains four levels stacked vertically. The bottom frame is labeled ‘main’ on the left, containing ‘result: 0’. The middle frames are abeled ‘recursiveMultiplyBy2’ on the left, containing parameters ‘n: 3’ and ‘n: 2’ respectively. The level for ‘n: 2’ has a note on the right stating ‘2 + 2 is calculated’. The top frame is labeled ‘recursiveMultiplyBy2’ with ‘n: 1’ and the note ‘2 + 0 is calculated’. This entire top level is greyed out to indicate it has been popped from the stack. A curved grey arrow points from the popped level (n: 1) down to the level beneath it (n: 2), highlighting the progression of the return value through the recursive call stack.

Figure 2.8: A diagram showing the final step of a recursive function call stack unwinding, captioned at the top with ‘Stack frame is popped’. The stack shows the final transition back to the main program. The bottom frame is labeled ‘main’ on the left, now updated to contain the variable ‘result: 6’. To its right, text reads ‘6 is returned’. The top frame is labeled ‘recursiveMultiplyBy2’ with ‘n: 3’ and the note ‘2 + 4 is calculated’. This entire level is greyed out to indicate it has been popped from the stack. A curved grey arrow points from the popped function level (n: 3) down to the ‘main’ frame below it.

Figure 2.9: A diagram showing a call stack with five stack frames stacked vertically, capturing a recursive function named ‘recursivePowerOf2’ that has reached its base case. The chart is captioned at the top with ‘Stack frame is popped’. The bottom frame is labeled ‘main’ on the left, containing ‘result: 0’. The second, third, and fourth frames are each labeled ‘recursivePowerOf2’ on the left, containing parameters ‘n: 3’, ‘n: 2’, and ‘n: 1’ respectively from bottom to top. The top frame is labeled ‘recursivePowerOf2’ on the left, containing the base case parameter ‘n: 0’. To the right of this frame, text reads ‘Base Case 1 is returned’.

Figure 2.10: A diagram showing a call stack with five stack frames stacked vertically, demonstrating a tail-recursive or accumulator-based implementation of a function named ‘recursivePowerOf2’. The bottom frame is labeled ‘main’ on the left, containing ‘result = 0’. The second frame from bottom is labeled ‘recursivePowerOf2’ on the left, containing variables ‘product: 1’ and ‘n: 3’. The third frame from bottom is labeled ‘recursivePowerOf2’ on the left, containing variables ‘product: 2’ and ‘n: 2’. The fourth frame from bottom: is labeled ‘recursivePowerOf2’ on the left, containing variables ‘product: 4’ and ‘n: 1’. The top frame is labeled ‘recursivePowerOf2’ on the left, containing variables ‘product: 8’ and ‘n: 0.’

Figure 2.11: A side-by-side diagram demonstrating the mechanics of Tail-Call Optimization (TCO) compared to a standard call stack growth. The left Side (Standard Growth Model) shows a three-level stack. The bottom frame is ‘main’ with ‘result= 0’. Above it is ‘recursivePowerOf2’ with ‘product: 1, n: 3’. A third frame on top (‘product: 2, n: 2’) is greyed out. The right side (Tail-Call Optimization Model): shows how the stack behaves with TCO enabled, captioned with ‘Tail-call optimization reuses the current stack frame’. Instead of adding a third frame, the middle frame for ‘recursivePowerOf2’ is updated in place, reusing the memory space to change the variables from their previous state to ‘product: 2, n: 2’. The total height of the stack stays constant.”

Figure 3.12: A side-by-side diagram demonstrating an execution state of an insertion sort algorithm. The left side (“Array and Index View”) shows an 8-element integer array with indices from 0 to 7 containing the values [43, 27, 45, 24, 35, 47, 22, 48]. An arrow labeled “endSorted” points down to index 1 (value 27). An arrow labeled index points up to index 1 (value 27). Floating above the array is a standalone box labeled “currentValue” containing the number 27. An arrow labeled end points down to the space just past the end of the array (index 8). The right side (‘Variables and Values’) is a text box listing the current state of four program variables: end is 8, endSorted is 1, currentValue is 27, and index is 1.

Figure 3.13: A side-by-side diagram demonstrating a subsequent execution step of the insertion sort algorithm, showing a value shift. The left side (“Array and Index View”) shows the 8-element integer array with indices 0 to 7. The array values are now [43, 43, 45, 24, 35, 47, 22, 48]. The value at index 1 has been overwritten by the 43 shifted from index 0. An arrow labeled “endSorted” points down to index 1. A standalone box labeled “currentValue” still holds the number 27 safely above the array. An arrow labeled index has shifted left and now points up to index 0 (value 43). An arrow labeled “end” points down past the end of the array. The right side (“Variables and Values”) is a text box listing the updated state of the program variables: end is 8, endSorted is 1, currentValue is 27, and index has decremented to 0.

Figure 3.14: A side-by-side diagram demonstrating another step in the insertion sort algorithm execution, where the first two elements have been successfully ordered. The left side (“Array and Index View”) shows the 8-element integer array with indices 0 to 7. The array values are now [27, 43, 45, 24, 35, 47, 22, 48]. The first two elements are sorted relative to each other. An arrow labeled “endSorted” points down to index 2 (value 45). An arrow labeled index points up to index 2 (value 45). Floating above the array is a standalone box labeled “currentValue” containing the number 45. An arrow labeled end points down past the end of the array. The right side (“Variables and Values”) is a text box listing the state of the program variables for this iteration: end is 8, endSorted is 2, currentValue is 45, and index is 2.

Figure 3.15: A side-by-side diagram demonstrating a new iteration step of the insertion sort algorithm, where a new out-of-order element is selected to be inserted. The left side (“Array and Index View”) shows the 8-element integer array with indices 0 to 7. The array values are [27, 43, 45, 24, 35, 47, 22, 48]. The elements up to index 2 are sorted. An arrow labeled “endSorted” points down to index 3 (value 24). An arrow labeled index points up to index 3 (value 24). Floating above the array to the left is a standalone box labeled “currentValue” containing the number 24, which is the value about to be sorted. An arrow labeled end points down past the end of the array. The right side (“Variables and Values”) is a text box listing the state of the program variables for this step: end is 8, endSorted is 3, currentValue is 24, and index is 3.

Figure 3.16: A side-by-side diagram demonstrating a shifting step during an insertion sort algorithm iteration. The left side (“Array and Index View”) shows the 8-element integer array with indices 0 to 7. The array values are now [27, 43, 45, 45, 35, 47, 22, 48]. The value 45 from index 2 has been copied and shifted right into index 3, overwriting the original 24. An arrow labeled “endSorted” points down to index 3. An arrow labeled index has decremented and points up to index 2 (value 45). A standalone box labeled “currentValue” continues to hold the number 24 safely above the array. An arrow labeled end points down past the end of the array. The right side (“Variables and Values”) is a text box listing the state of the program variables for this step: end is 8, endSorted is 3, currentValue is 24, and index has decremented to 2.

Figure 3.17: A side-by-side diagram demonstrating another shifting step during an insertion sort algorithm iteration, where multiple larger elements are being shifted right. The left side (“Array and Index View”) shows the 8-element integer array with indices 0 to 7. The array values are now [27, 43, 43, 45, 35, 47, 22, 48]. The value 43 from index 1 has been copied and shifted right into index 2, following the previous shift of 45. An arrow labeled “endSorted” points down to index 3. An arrow labeled index has decremented again and points up to index 1 (value 43). A standalone box labeled “currentValue” continues to hold the number 24 safely above the array. An arrow labeled end points down past the end of the array. The right side (‘Variables and Values’) is a text box listing the state of the program variables for this step: end is 8, endSorted is 3, currentValue is 24, and index has decremented to 1.

Figure 3.18: A side-by-side diagram demonstrating the completion of an insertion sort algorithm iteration, where the selected value is finally placed into its correct sorted position. The left side (“Array and Index View’): Shows the 8-element integer array with indices 0 to 7. The array values are now [24, 27, 43, 45, 35, 47, 22, 48]. The currentValue of 24 has been inserted into index 0, meaning the sub-array from index 0 to 3 is now fully sorted. An arrow labeled “endSorted” points down to index 3. An arrow labeled “index” points up to index 0. A standalone box labeled “currentValue” still holds the number 24 above the array. An arrow labeled “end” points down past the end of the array. The right side (“Variables and Values”) is a text box listing the final state of the program variables for this loop cycle: end is 8, endSorted is 3, currentValue is 24, and index is 0.

Figure 3.19: A side-by-side diagram demonstrating the start of a subsequent loop iteration in the insertion sort algorithm. The left side (“Array and Index View”) shows the 8-element integer array with indices 0 to 7. The current array values are [24, 27, 43, 45, 35, 47, 22, 48]. The sub-array from index 0 to 3 is sorted. An arrow labeled “endSorted” points down to index 4 (value 35), indicating that 35 is the next element chosen to be sorted. An arrow labeled “index” also points up to index 4. Floating above the array to the left is a standalone box labeled “currentValue” containing the number 35. An arrow labeled end points down past the end of the array. The right side (“Variables and Values”) is a text box listing the state of the program variables at the beginning of this new iteration step: end is 8, endSorted is 4, currentValue is 35, and index is 4.

Figure 3.21: Array of numbers being halved each time. 43, 27, 45, 24 to the left and 35, 47, 22, 48 to the right. 43, 27, 45, 24 is split into 43 and 27 to the left and 45 and 24 to the right. 43 and 27 split further down into 43 to the left and 27 to the right. 45 and 24 split apart, 45 to the left and 24 to the right. Back up to the top, 35, 47, 22, and 48 split into two groups. 35 and 47 to the left, further split up to 35 on the left and 47 on the right. 22 and 48 are split with 22 on the left and 48 on the right.

Figure 3.23: A two-part diagram demonstrating the merging step of a merge sort algorithm, illustrating how two sorted 2-element sub-arrays are combined into a single sorted 4-element array. The top diagram shows two separate, sorted 2-element arrays side-by-side—the left containing [27, 43] and the right containing [24, 45]. Straight lines connect them down to a single, combined 4-element array below containing the fully sorted result: [24, 27, 43, 45]. The bottom diagram displays the exact same arrays, but uses four distinct, curved pointer arrows to trace individual element placement. The arrows trace how the elements are compared and copied down to the final array: 24 is placed first, followed by 27, then 43, and finally 45.

Figure 3.24: An array section contains four contiguous data blocks with the values 27, 43, 24, and 45. Three labeled arrows point to specific indices within this data block. An arrow labeled “Start of left side” points down to the first element containing the value 27. An arrow labeled “End of left side'” points down to the second element containing the value 43. An arrow labeled “End of the data” points up to the fourth element containing the value 45.

Figure 3.25: A side-by-side diagram showing the beginning of the sorting phase in a merge sort operation using external temporary storage. The left side (“Temporary storage”) shows a main array containing values [27, 43, 24, 45]. Four downward-pointing arrows indicate these elements are being copied out into two separate sub-arrays in a dedicated block labeled “Temporary Storage” below, splitting them into [27, 43] and [24, 45]. The right side (“Merge in order”) shows the merging process back into the original main array. Curved arrows trace elements from the “Temporary Storage’ sub-arrays being compared and written back in ascending order. The element 24 from the right sub-array is moved to index 0, and the element 27 from the left sub-array is moved to index 1, resulting in the main array starting with values [24, 27, 24, 45] midway through the merge.

Figure 3.26: A diagram illustrating the divide-and-conquer recurrence tree of a merge sort algorithm on an 8-element array, along with its mathematical cost analysis. At the top sits the original unsorted 8-element array [43, 27, 45, 24, 35, 47, 22, 48]. Two large circles contain the split execution paths. The left circle shows successive binary subdivisions of the left half: from a 4-element sub-array [43, 27, 45, 24], down to two 2-element sub-arrays [43, 27] and [45, 24], down to individual 1-element arrays at the base level. The right circle parallels the same process for the right half, splitting [35, 47, 22, 48] into 2-element blocks and ultimately single-element blocks. The text at the bottom defines the Cost of sorting = cost of sorting the left T(n/2) + cost of sorting the right T(n/2) + cost of merging c times n.

Figure 3.27: A diagram illustrating the divide-and-conquer recurrence tree of a merge sort algorithm on an 8-element array, focused on the cost of sorting the two halves. At the top sits the original unsorted 8-element array [43, 27, 45, 24, 35, 47, 22, 48]. Two large circles contain the split execution paths. The left circle shows successive binary subdivisions of the left half: from a 4-element sub-array [43, 27, 45, 24], down to two 2-element sub-arrays [43, 27] and [45, 24], down to individual 1-element arrays at the base level. The right circle parallels the same process for the right half, splitting [35, 47, 22, 48] into 2-element blocks and ultimately single-element blocks. Cost Analysis Formulas are at the bottom and breaks down the algorithm’s recursive breakdown costs. The cost of sorting left equals T(n/4) + T(n/4) + c times (n/2). The cost of sorting right equals T(n/4) + T(n/4) + c times (n/2).

Figure 3.28: A tree diagram showing the breakdown of merging costs per level in a merge sort recurrence tree analysis. At the root level of the tree sits a single node representing the total cost of merging the full array, labeled c times n. This root splits into two child nodes at the second level, each representing half the problem size and labeled c times n divided by 2. Each of those second-level nodes splits once more into the third level, producing four leaf nodes each labeled c times n divided by 4.

Figure 3.30: Array and Index View displays an 8-element integer array with indices 0 to 7 containing the values [43, 27, 45, 24, 35, 47, 22, 48]. Pointers track elements relative to the boundaries. An arrow labeled “start” and an arrow labeled “smallIndex” both point to index 0. An arrow labeled “index” points up to index 1. Above index 4, a standalone box labeled “pivotValue” safely stores the chosen pivot element, 43. An arrow labeled “end” points down to index 7 (value 48). A text box in the bottom right corner states the rule for the upcoming evaluation step: “Increment ‘smallIndex’ and exchange with ‘index'”.

Figure 3.31: Array and Index View displays an 8-element integer array with indices 0 to 7 containing the values [43, 27, 45, 24, 35, 47, 22, 48]. An arrow labeled “start” points to index 0. An arrow labeled “smallIndex” points to index 1. An arrow labeled “index” points up to index 2. Above, a standalone box labeled “pivotValue” safely stores the chosen pivot element, 43. An arrow labeled “end” points down to index 7 (value 48).

Figure 3.32: Array and Index View displays an 8-element integer array with indices 0 to 7 containing the values [43, 27, 45, 24, 35, 47, 22, 48]. An arrow labeled “start” points to index 0. An arrow labeled “smallIndex” points to index 1. An arrow labeled “index” points up to index 3. Above, a standalone box labeled “pivotValue” safely stores the chosen pivot element, 43. An arrow labeled “end” points down to index 7 (value 48). A text box in the bottom right corner states the rule for the upcoming evaluation step: “Increment ‘smallIndex’ and exchange with ‘index'”.

Figure 3.33: Array and Index View illustrating a step in a partitioning algorithm. An array of 8 elements with indices 0 through 7 contains the values: 43, 27, 24, 45, 35, 47, 22, 48. Boxed value “pivotValue = 43” is shown above the array, referencing the value at index 0. Pointer labels with downward/upward arrows mark specific positions: start: points up to index 0 (value 43), from below the array. index: points up to index 3 (value 45), from below the array. smallIndex: points down to index 2 (value 24), from above the array. end: points down to index 7 (value 48), from above the array.

Figure 3.34: Array and Index view. Boxed value “pivotValue = 43” is shown at top left, referencing the value at index 0. An array of 8 elements with indices 0 through 7 contains the values: 43, 27, 24, 35, 22, 47, 45, 48. Pointer labels with arrows mark positions: start: points up to index 0 (value 43), from below the array. smallIndex: points down to index 4 (value 22), from above the array. end: points down to index 7 (value 48), from above the array. index: points up to index 7 (value 48), from below the array, indicating scanning has finished. A boxed instruction below reads: “Exchange smallIndex and pivot (first position),” indicating the next step is to swap the value at smallIndex (22) with the pivot value at the start of the array to complete the partition.

Figure 3.35: Next set in Array and Index view. An array of 8 elements with indices 0 through 7 contains the values: 22, 27, 24, 35, 43, 47, 45, 48. The value at index 4 (43) is shaded gray and labeled “pivotIndex” above with a downward arrow, marking it as the pivot now in its correct sorted position. Two oval outlines group the array into left and right partitions around the pivot: Left partition (indices 0–3, values 22, 27, 24, 35): marked below by “startL” (pointing to index 0) and “endL” (pointing to index 3). Right partition (indices 5–7, values 47, 45, 48): marked below by “startR” (pointing to index 5) and “endR” (pointing to index 7). A boxed instruction below reads: “Recursively sort left and right partitions,” indicating the next step in the algorithm is to apply the same partitioning process to each of the two sub-arrays on either side of the pivot.

Figure 3.36: Tree diagram illustrating the recursive partitioning structure of the Quicksort algorithm, shown as a call tree of arrays being split. The top level shows the full array [22, 27, 24, 35, 43, 47, 45, 48], with the value 43 shaded gray as the pivot. The second level shows that the array splits into two sub-arrays around the pivot: Left: [22, 27, 24, 35] and Right: [45, 47, 48]. The third level shows each sub-array splits further: Left sub-array splits into [22, 27] and [24, 35] and Right sub-array splits into [45, 47] and [48] (shown as one smaller box and one wider box). The fourth level shows each of those splits further into empty boxes, each with two more branch lines extending downward with no boxes, indicating the recursion terminating.

Figure 3.37: Tree diagram showing three levels of recursive Quicksort partitioning, with pivots highlighted in gray at each step. The top level shows the full array [22, 27, 24, 35, 43, 47, 45, 48], with 43 shaded as the pivot, splitting into left and right sub-arrays. The second level split shows on the Left: [22, 27, 24, 35] and Right: [47, 45, 48]. The third level shows each sub-array selects a new pivot (shaded gray) and partitions further: Left sub-array [22, 27, 24, 35] has 22 shaded as pivot, splitting into an empty left branch (no elements smaller than 22) and a right branch [27, 24, 35]. The Right sub-array [47, 45, 48] has 47 shaded as pivot, splitting into left branch [45] and right branch [48].

Figure 3.38: Tree diagram continuing the recursive Quicksort partitioning down a diagonal chain. Level 1 shows the array [22, 24, 27, 35], with 22 shaded as pivot that branches into an empty left side (no smaller elements) and right sub-array [24, 27, 35]. Level 2 shows the array [24, 27, 35], with 24 shaded as pivot that branches into an empty left side and right sub-array [27, 35]. Level 3 shows the array [27, 35], with 27 shaded as pivot that branches into an empty left side and right sub-array [35]. Level 4 shows a single-element array [35], the base case, ending the recursion.

Figure 3.39: Tree diagram showing a chain of shrinking partitions each reduced by one element. “partition n elements” shows the array [22, 24, 27, 35, 43, 45, 47, 48], with 22 shaded as pivot, arrow leading down to the next row. “partition n-1 elements” shows the array [24, 27, 35, 43, 45, 47, 48], with 24 shaded as pivot, arrow leading down to the next row. “partition n-2 elements” shows the array [27, 35, 43, 45, 47, 48], with 27 shaded as pivot. A vertical ellipsis (three dots) indicates the pattern continues. “partition 2 elements” shows the array [47, 48], the final, smallest partition. Each step removes exactly one element (the pivot) from the front of the array.

Figure 4.3: A diagram illustrating how an array stores references to object instances in noncontiguous memory. The top Section (‘contiguous array of references’) shows a horizontal array bounded from index 0 to 99. Index 0, index 1, and index 99 contain reference pointers (indicated by long downward arrows) pointing to discrete object blocks below. The bottom section (‘stored in noncontiguous memory’) shows three separate, grey memory blocks representing individual data objects scattered across system memory. The pointer from index 0 points to an object with fields: member_id: 19, name: “Rosa”, and email: “rgarcia@school.edu”. The pointer from index 1 points down to an object with fields: member_id: 13, name: “Samantha”, and email: “ssmith@school.edu”. The pointer from index 99 points to an object with fields: member_id: 24, name: “Dante”, and email: “djones@school.edu.”

Figure 4.4: A diagram illustrating the Search key: 27. The array and index view displays a 7-element integer array with visible index markings under specific boundaries. The array contains the sorted values [22, 24, 27, 35, 43, 47, 48]. Three downward-pointing arrows track the search boundaries: low points to index 0 (value 22),high points to index 7 (value 48), mid points to index 3 (value 35). The text at the bottom shows the mathematical floor operation used to establish the midpoint: floor( (0 + 7) / 2 ) = 3.

Figure 4.5: A diagram illustrating a step in a binary search algorithm for Search key: 27. An array of 7 elements is represented as a horizontal row of boxes containing the sorted integers: 22, 24, 27, 35, 43, 47, and 48. Underneath the first three boxes are their corresponding index labels: 0, 1, and 2. Three vertical arrows point down to the first three boxes: An arrow labeled “low” points to index 0 (value 22). An arrow labeled “mid” points to index 1 (value 24). An arrow labeled “high” points to index 2 (value 27). At the bottom, the calculation for the middle index is shown as: floor( (0 + 2) / 2 ) = 1.

Figure 4.6: A diagram illustrating the final step in a binary search algorithm where the target element is found. At the top, the text reads “Search key: 27”. Below it, an array of 7 elements is represented as a horizontal row of boxes containing the sorted integers: 22, 24, 27, 35, 43, 47, and 48. Underneath the third box (27) is its corresponding index label: 2. Three vertical arrows point down closely together, all targeting the exact same third box (value 27): The leftmost arrow is labeled “low”. The middle arrow is labeled “mid”. The rightmost arrow is labeled “high”. At the bottom, the calculation for the middle index is shown as: floor( (2 + 2) / 2 ) = 2.

Figure 5.3: A diagram illustrating a chain of four sequential nodes forming a singly linked list. From left to right, the nodes are labeled and connected as follows: Node a is a rectangular box containing the value 1 on the left and a pointer dot on the right with an arrow pointing to Node b. Node b is a rectangular box containing the value 3 on the left and a pointer dot on the right with an arrow pointing to Node c. Node c is a rectangular box containing the value 9 on the left and a pointer dot on the right with an arrow pointing to Node d. Node d is a rectangular box containing the value 27 on the left. The right section contains a diagonal line from the bottom-left corner to the top-right corner, representing a null pointer that terminates the list.

Figure 5.4: A detailed diagram illustrating the step-by-step process of inserting a new node into a singly linked list at a specific position (index 2). The process is broken down into 10 numbered steps:

1. Start with a list: Displays an initial three-node linked list containing the values 8 -> 9 -> 11. The last node (11) has a diagonal line representing a null pointer.

2. Insert 10 at position 2.
   

3. Create new node.
   

4. Position is not 0, so enter else block.
   

5. i=1: Shows the current position tracking pointer n pointing to the first node (8). The right-hand box has a black dot with an arrow to the right pointing to the next node. The next node contains 9 on the left and on the right, a black dot and arrow pointing to the third node. The third node has 11 on the left and on the right is a diagonal line through the box. A separate node is next with 10 in the left box, and a diagonal line in the right.
   

6. i < position, so follow next and increased i.
   

7. i=2: The tracking pointer n moves to point to the second node (9). The third node has 11 on the left and diagonal line on the right. The last node is separated from the other nodes. 10 is on the left and a diagonal line goes through the right box.
   

8. i == position, so loop is complete. Rearrange references.
   

9. Set new Node. Next to n.Next: Shows the pointer rearrangement starting. The new node (10) now points to node 11 (which was originally n.Next).
   

10. Set n.Next to new Node: Displays the finalized list structure. Node 9 (n) now points forward to the new node 10, which in turn points to node 11, successfully integrating it into the chain as 8 -> 9 -> 10 -> 11.

Figure 5.5: A detailed diagram illustrating the step-by-step process of removing a node. The process is broken down into 8 numbered steps:

1. Start with a list: Displays an initial three-node linked list containing the values 8 -> 9 -> 11. The last node (11) has a diagonal line representing a null pointer.
   

2. Remove at position 2.
   

3. Position is not 0, so enter else block.
   

4. i=1: Shows the current position tracking pointer n pointing to the first node (8). The right-hand box has a black dot with an arrow to the right pointing to the next node. The next node contains 9 on the left and on the right, a black dot and arrow pointing to the third node. The third node has 10 on the left and on the right is a dot an arrow pointing to the last node. The last node has 11 in the left box, and a diagonal line in the right.
   

5. i < position, so follow next and increased i.
   

6. i=2: The tracking pointer n moves to point to the second node (9). The third node has 10 on the left and a dot and arrow pointing to the last node. The last node has 11 is on the left and a diagonal line goes through the right box.
   

7. i == position, so loop is complete.
   

8. Set n.Next to n.Next. Next: Displays the finalized list structure. Node 8 points to node 9 (n), which points around node 10 to the node 11 (n.Next. Next). Node 10 (n.Next) is in numerical order between 9 and 11, but separated. It also points to Node 11.

Figure 6.1: A diagram illustrating the step-by-step process of enqueue and dequeue operations in a queue data structure implemented using a singly linked list. The process is broken down into 4 numbered steps, showing how tracking pointers (head and tail) shift as elements are added or removed.

1. Enqueue value 8. Since this is the first element, both the head and tail arrows point to a single node containing the value 8. The node’s next pointer has a diagonal line, indicating it is currently null.
2. Enqueue value 10: A new node containing 10 is added to the end of the queue. The first node (8) now points forward to the new node (10). The head arrow remains on node 8, while the tail arrow moves to point to the new end of the queue, node 10.
3. Enqueue value 12. Another node is added to the back. Node 10 now points forward to node 12. The head arrow stays anchored to node 8, while the tail arrow moves to point to node 12.
4. Dequeue – returns 8. Text indicates a removal operation from the front of the queue. The first node (8) is decoupled from the sequence. The head arrow advances to point to node 10 (the new front of the queue), while the tail arrow remains pointing to node 12.

Figure 6.2: A diagram illustrating the step-by-step process of enqueue and dequeue operations in a queue data structure implemented using a fixed-size array. The process is broken down into 4 numbered steps.

1. Enqueue value 8. headPos = 0 and tailPos = 0. The array shows the value 8 in the first slot (index 0), while the remaining four slots contain diagonal lines indicating they are empty.
2. Enqueue value 10: The value 10 is added to the next available slot. headPos remains 0 while tailPos increments to 1. The array now shows 8 and 10 in the first two slots.
3. Enqueue value 12: The value 12 is added. headPos remains 0 while tailPos increments to 2. The array now contains 8, 10, and 12 in the first three slots.
4. Dequeue – returns 8: Text indicates a removal operation from the front of the queue. tailPos remains 2, while headPos increments to 1 to point to the new front of the queue (10). The array elements remain visually unchanged in the diagram, but index 0 is now logically inactive.

Figure 6.3: A diagram illustrating the step-by-step operations of a circular queue implemented using an array of size 10 and modulo arithmetic (mod) to wrap tracking indices around. The diagram features a jagged break in the middle of each array graphic to indicate missing elements (indices 2 through 7), showing only indices 0, 1, 8, and 9. It is broken into 5 numbered steps.

1. Existing Queue: Array Size 10, headPos = 9, tailPos = 9. Index 9 contains the value 14. Indices 0 and 1 are blank.
2. Enqueue 16. headPos = 9, headPos mod array size = 9; tailPos = 10, tailPos mod array size = 0. The value 16 is inserted into index 0. Index 9 still contains 14.
3. Enqueue 18: headPos = 9, headPos mod array size = 9; tailPos = 11, tailPos mod array size = 1. No updated array is shown visually for this step, but text indicates that the next element would wrap around to index 1 (11 mod 10 = 1).
4. Requeue returns 14: headPos = 10, headPos mod array size = 0; tailPos = 11, tailPos mod array size = 1. The diagram shows the array with 16 at index 0 and 14 at index 9. The headPos has logically shifted to index 0.
5. Dequeue returns 16: headPos = 11, headPos mod array size = 1; tailPos = 11, tailPos mod array size = 1. The diagram shows the same array graphic with 16 at index 0 and 14 at index 9. Logically, the headPos has now shifted to index 1, making the queue empty as headPos == tailPos.

Figure 7.1: TEXT

Figure 7.2: TEXT

Figure 7.3: A diagram illustrating a hash collision occurring during an insertion into a hash table data structure. The diagram is split into two primary components: Incoming Data (Left) is a grey box that contains a student record to be inserted: key: 28, name: “Idrissa”, and email: “ielba@school.edu”. A solid black arrow points from this box down to index 8 of the hash table, labeled with the text “collision!”. Hash Table Array (Right): A vertical array structure representing the storage grid with defined indices: Index 0 is occupied by a grey box containing: key: 20, name: “Dante”, email: “djones@school.edu”. An ellipsis (…) indicates skipped indices between 1 and 7. Index 8 is already occupied by a grey box containing: key: 18, name: “Samantha”, email: “ssmith@school.edu”, which causes the incoming record with key 28 to collide with it. Index 9 is occupied by a grey box containing: key: 19, name: “Rosa”, email: “rgarcia@school.edu”.

Figure 7.4: On the right, there is a vertical column labeled “table” flanked by two parallel black lines. To the left of the table is a column of indices numbered from 0 to 9. Within the table, gray square placeholders are located next to indices 2, 7, and 9. To the left of the table, a separate gray square block containing the letter “A” has an arrow pointing diagonally downward toward index 2. Directly below block A, the word “collision” is written, indicating that a collision occurs because index 2 is already occupied by an existing element.

Figure 7.5: A sequential diagram illustrating collision resolution in a hash table using linear probing, broken into two steps labeled “1” and “2”. A vertical column labeled “table” is bounded by two black lines, with a column of indices numbered 0 through 9 on its left. Gray square placeholders permanently occupy indices 2, 7, and 9. Step 1: On the far left, a circled number “1” indicates the first phase. Next to it, a gray block labeled “A” has an arrow pointing diagonally down toward index 2. Below block A, the word “collision” is written, showing that block A attempts to insert at index 2 but encounters an occupied slot. Step 2: On the right side of the table, a circled number “2” indicates the resolution step. A curved gray arrow points from index 2 down to the next available slot at index 3. Inside the table at index 3, the block “A” is now successfully stored.

Figure 7.6: A sequential diagram illustrating the insertion of a new element into a hash table using linear probing to resolve subsequent collisions, broken into two steps labeled “1” and “2”. A vertical column labeled “table” is bounded by two black lines, with a column of indices numbered 0 through 9 on its left. Pre-existing gray square placeholders occupy indices 2, 7, and 9, while index 3 contains the block “A” (inserted previously). Step 1: On the left side, a circled number “1” indicates the first phase. A new gray block labeled “B” has an arrow pointing diagonally down toward index 2. Below block B, the word “collision” is written, indicating that block B hashes to index 2 but encounters an occupied slot. Step 2: On the right side of the table, a circled number “2” indicates the sequential resolution process. Two stacked, curved gray arrows show the probing steps: The first arrow curves from index 2 to index 3, which is already occupied by block “A”. The second arrow curves from index 3 down to the next available empty slot at index 4. Inside the table at index 4, block “B” is now successfully stored.

Figure 7.7: A sequential diagram illustrating a common issue with naive deletion in a hash table using linear probing, where removing an element breaks the search chain for subsequently inserted elements. The process is broken down into three steps. A vertical column labeled “table” is bounded by two black lines, with a column of indices numbered 0 through 9 on its left. Pre-existing gray square placeholders occupy indices 2, 7, and 9. Index 4 contains the block “B”. Step 1: On the upper left side, a circled number “1” is accompanied by the text “A is removed”. Correspondingly, at index 3 inside the table, block “A” has a large black “X” marked over it, indicating it has been naively deleted and left empty. Step 2: Below Step 1, a circled number “2” is accompanied by the text “Search for B’s key”. This initiates a search for element B, which originally hashed to index 2. Step 3: On the right side of the table, a circled number “3” is accompanied by the text: “Collision at position 2. Position 3 is empty. B is not in the table! Error.” A curved gray arrow on the right side of the table starts at index 2 and points down to index 3. Because the search algorithm encounters an empty slot at index 3 (due to A’s deletion), it prematurely terminates and incorrectly concludes that B does not exist in the table, ignoring the fact that B is stored right below it at index 4.

Figure 7.8: A sequential diagram illustrating the insertion of a third colliding element into a hash table using linear probing, broken down into two steps. A vertical column labeled “table” is bounded by two black lines, with a column of indices numbered 0 through 9 on its left. Pre-existing gray square placeholders occupy indices 2, 7, and 9. Index 3 contains block “A” and index 4 contains block “B” from previous insertions. Step 1: On the left side, a circled number “1” indicates the initial insertion phase. A new gray block labeled “C” has an arrow pointing diagonally down toward index 3. Below block C, the word “collision” is written, indicating that block C hashes to index 3 but encounters an occupied slot. Step 2: On the right side of the table, a circled number “2” indicates the sequential resolution process. Two stacked, curved gray arrows show the probing steps: The first arrow curves from index 3 down to index 4, which is already occupied by block “B”. The second arrow curves from index 4 down to the next available empty slot at index 5. Inside the table at index 5, block “C” is now successfully stored.

Figure 7.9: A sequential diagram illustrating collision resolution in a hash table using quadratic probing, broken down into two steps. A vertical column labeled “table” is bounded by two black lines, with a column of indices numbered 0 through 9 on its left. Pre-existing gray square placeholders occupy indices 2, 7, and 9. Step 1: On the upper left side, a circled number “1” indicates the initial insertion phase. A gray block labeled “A” has an arrow pointing diagonally down toward index 2. Below block A, the word “collision” is written, indicating that block A hashes to index 2 but encounters an occupied slot. Step 2: On the right side, a circled number “2” is accompanied by the text: “With one collision, A maps to 2 + 1^2 = 3.” A curved gray arrow on the right side of the table starts at index 2 and curves down to index 3 based on the quadratic formula step. Inside the table at index 3, block “A” is now successfully stored.

Figure 7.10: A sequential diagram illustrating collision resolution in a hash table using quadratic probing when a second collision is encountered, broken down into three steps labeled “1”, “2”, and “3”. A vertical column labeled “table” is bounded by two black lines, with a column of indices numbered 0 through 9 on its left. Pre-existing gray square placeholders occupy indices 2, 7, and 9. Index 3 contains block “A” from a previous insertion. Step 1: On the left side, a circled number “1” indicates the initial insertion phase. A new gray block labeled “B” has an arrow pointing diagonally down toward index 3, accompanied by the word “collision” because index 3 is already occupied by block “A”. (Note: The visual indicates B’s base hash position is index 2, matching the math in Step 3). Step 2: On the right side, a circled number “2” labeled “collision” marks the first probing attempt. A small curved gray arrow jumps from index 2 down to index 3. Because index 3 is occupied, a second collision occurs. Step 3: Below Step 2, a circled number “3” is accompanied by the text, “With 2 collisions, B maps to 2 + 2^2 = 6. A much larger curved gray arrow on the right side originates from index 3 and sweeps down to the open slot at index 6, skipping indices 4 and 5 based on the quadratic formula step. Inside the table at index 6, block “B” is now successfully stored.

Figure 7.11: A sequential diagram illustrating collision resolution in a hash table using quadratic probing, broken down into two steps. A vertical column labeled “table” is bounded by two black lines, with a column of indices numbered 0 through 9 on its left. Pre-existing gray square placeholders occupy indices 2, 7, and 9. Index 3 contains block “A” and index 6 contains block “B” from previous insertions. Step 1: On the left side, a circled number “1” indicates the initial insertion phase. A new gray block labeled “C” has an arrow pointing diagonally down toward index 3. Below block C, the word “collision” is written, indicating that block C hashes directly to index 3 but encounters an occupied slot. Step 2: On the right side, a circled number “2” is accompanied by the text, “With 1 collision, C maps to 3 + 1^2 = 4.” A curved gray arrow on the right side of the table starts at index 3 and points down to index 4 based on the first quadratic step. Inside the table at index 4, block “C” is now successfully stored.

Figure 7.15: A line graph titled “Expected Number of Probes by Load” that demonstrates how the load factor of a hash table impacts search efficiency. The horizontal axis (x-axis) is labeled “Load Factor” and ranges from 0.0 to 1.0. The vertical axis (y-axis) is labeled “Expected Probes” and ranges from 0 to 100. A single black line starts near zero on both axes, remaining very low and relatively flat as the load factor increases from 0.0 to approximately 0.7. Between a load factor of 0.7 and 0.9, the line begins to curve upward. As the load factor approaches 1.0 (a completely full hash table), the line turns nearly vertical, showing an exponential spike where the expected number of probes quickly approaches 100.

Figure 7.17: A sequential diagram illustrating collision resolution in a hash table using separate chaining (an array of linked lists), broken down into two steps. On the left, a vertical column lists indices from 0 through 9. To the right is the main structure labeled “Array of linked lists,” which consists of pointer heads (black dots) with arrows pointing to the right. Pre-existing nodes (represented by gray square placeholders) are attached to indices 2, 7, and 9. Step 1: On the upper left side, a circled number “1” marks the initial insertion phase. A new gray block labeled “A” has an arrow pointing diagonally down toward index 2, accompanied by the word “collision” because index 2 already contains a pre-existing block. Step 2: On the upper right side, a circled number “2” is accompanied by the text: “A is simply added to the linked list at position 2”. Looking across index 2, the horizontal pointer arrow connects to the pre-existing gray square node, and a subsequent arrow links directly to the newly added block “A”. Block “A” terminates with its own horizontal arrow, showing it is now the second node in the linked list chain for position 2.

Figure 7.18: A sequential diagram illustrating the insertion of another colliding element into a hash table using separate chaining (an array of linked lists), broken down into two steps. On the left, a vertical column lists indices from 0 through 9. To the right is the main structure labeled “Array of linked lists,” which consists of pointer heads (black dots) with arrows pointing to the right. Pre-existing nodes (represented by gray square placeholders) are attached to indices 7 and 9, while index 2 contains a chain with an initial unlabelled gray square followed by block “A”. Step 1: On the upper left side, a circled number “1” marks the initial insertion phase. A new gray block labeled “B” has an arrow pointing diagonally down toward index 2, accompanied by the word “collision” because index 2 is already occupied by a linked list chain. Step 2: On the upper right side, a circled number “2” is accompanied by the text: “B is added to the linked list”. Looking across index 2, the horizontal pointer arrow connects to the unlabelled gray square node, which links to block “A”, which now links directly to the newly appended block “B”. Block “B” terminates with its own horizontal arrow, showing it is now the third node in the linked list chain for position 2.

Figure 7.19: A sequential diagram illustrating the insertion of an element into an empty slot within a hash table using separate chaining (an array of linked lists), broken down into two steps. On the left, a vertical column lists indices from 0 through 9. To the right is the main structure labeled “Array of linked lists,” consisting of pointer heads (black dots) with horizontal arrows pointing to the right. Pre-existing nodes (represented by gray square placeholders) are attached to indices 7 and 9, while index 2 contains a linked list with three elements: an unlabelled gray square, block “A”, and block “B”. Step 1: On the left side, a circled number “1” marks the initial insertion phase. A new gray block labeled “C” has an arrow pointing diagonally down toward index 3, accompanied by the text “add C”. Step 2: On the right side, next to index 3, a circled number “2” is accompanied by the text: “C is inserted into the empty list at position 3.” Looking across index 3, the horizontal pointer arrow now connects directly to the newly inserted block “C”. Block “C” terminates with its own horizontal arrow, showing it is now the first and only node in the linked list chain for position 3.

Figure 8.1: A diagram of a tree data structure consisting of three vertical levels of circular nodes connected by black lines. At the top (level 0) is a single shaded gray root node labeled “R”. The root node connects to three shaded gray child nodes at level 1 below it. Moving from left to right across level 1: the first gray child node splits into two unshaded white leaf nodes at the bottom level (level 2); the second gray child node splits into two unshaded white leaf nodes at level 2; the third gray child node does not have any children, serving as a leaf node itself.

Figure 8.2: A diagram of a Binary Search Tree (BST) containing integer values arranged across three levels. At the top (level 0) is a shaded gray root node with the value 8. The root node connects to two shaded gray child nodes at level 1: a left child with the value 3 and a right child with the value 12. At the bottom (level 2), the child nodes split into four unshaded white leaf nodes. The node with value 3 connects to a left child of 1 and a right child of 5. The node with value 12 connects to a left child of 9 and a right child of 14.

Figure 8.3: A side-by-side transition diagram demonstrating node deletion in a Binary Search Tree (BST), separated by a large horizontal gray arrow labeled “Delete 4”. Before (Left): A small BST with a gray root node labeled 8. Node 8 has a left child node labeled 4 and a right child node labeled 9. After (Right): The resulting BST after deletion. The gray root node 8 remains at the top, but its left link is gone. It now only has a right child node labeled 9, showing that node 4 has been successfully removed from the tree structure.

Figure 8.4: A side-by-side transition diagram demonstrating the deletion of an internal node with one child in a Binary Search Tree (BST), separated by a large horizontal gray arrow labeled “Delete 4”. Before (Left): A BST with a gray root node labeled 8. Node 8 has a right child node labeled 9 and a left child node labeled 4. Node 4 itself has a single left child node labeled 1. After (Right): The resulting BST after deletion. The gray root node 8 remains at the top with its right child 9 unchanged. Because node 4 was deleted, its single child (node 1) has been promoted up to take its place, connecting directly as the new left child of the root node 8.

Figure 8.5: A side-by-side transition diagram demonstrating node deletion in a Binary Search Tree (BST) when the target node has two children, separated by a large horizontal gray arrow labeled “Delete 4”. Before (Left): A complex BST structure with a gray root node labeled 8. Node 8 has a right child node labeled 9 and a left child node labeled 4. Node 4 has two children: a left child node labeled 1 (which has its own right child node labeled 2) and a right child node labeled 6 (which has two child nodes labeled 5 and 7). After (Right): The resulting BST after deleting node 4. The root node 8 and its right child 9 remain unchanged. To fill the vacancy left by node 4, its in-order predecessor (node 2, the largest value in its left subtree) has been promoted to take its place. Node 2 now directly connects as the left child of the root node 8, maintaining its original left child (node 1) and its new right child subtree rooted at node 6 (which has two child nodes labeled 5 and 7).

Figure 8.6: Complete binary search tree with 7 nodes, three levels. Root node 4 (shaded) has left child 2 (shaded) and right child 6 (shaded). Node 2 has left child 1 and right child 3 (both unshaded). Node 6 has left child 5 and right child 7 (both unshaded).”

Figure 8.7: Diagonal chain of 7 nodes numbered 1 through 7, connected sequentially in a straight line from upper left to lower right. Nodes 2, 4, and 6 are shaded gray; nodes 1, 3, 5, and 7 are unshaded, showing an alternating pattern.

Figure 8.9: Two side-by-side tree diagrams comparing an unbalanced versus balanced structure with the same three shaded nodes (4, 5, 8). Left diagram: an unbalanced tree in a diagonal chain — node 8 at top labeled with height 3, connected down to node 5 labeled height 2, connected down to node 4 labeled height 1. Right diagram: a balanced tree with node 5 at top labeled height 2, with two children, node 4 (left) and node 8 (right), each labeled height 1.

Figure 8.10: Two side-by-side binary search trees, each with directed arrows from parent to child, comparing balanced versus unbalanced structures. Left diagram: a perfectly balanced tree with root 5, children 3 and 7, and four leaves 2, 4, 6, and 8 (no height labels shown). Right diagram: an unbalanced tree with root 4 labeled height 4, left child 3 labeled height 2 and right child 6 labeled height 3; node 3 has a single left child 2 labeled height 1; node 6 has children 5 (labeled height 1) and 7 (labeled height 2); node 7 has a single right child 8 labeled height 1.

Figure 9.2: Diagram illustrating a binary max-heap stored as an array. Tree view: root 12 (index 0) has left child 7 (index 1) and right child 4 (index 2); node 7 has children 3 (index 3) and 5 (index 4); node 4 has a single left child 2 (index 5). Below the tree, a 6-element array shows the same values in order: 12, 7, 4, 3, 5, 2, indexed 0 through 5. To the right, a text box gives the index formulas: for index i, parent is at (i-1)/2, left child at (i times 2)+1, and right child at (i times 2)+2.

Figure 9.3: Diagram of a complete binary max-heap with 7 nodes stored as an array. Tree view: root 12 (index 0) has children 7 (index 1) and 4 (index 2); node 7 has children 3 (index 3) and 5 (index 4); node 4 has children 2 (index 5) and 8 (index 6). Below the tree, a 7-element array shows the same values in level order: 12, 7, 4, 3, 5, 2, 8, indexed 0 through 6.

Figure 9.4: Diagram of a complete binary max-heap with 7 nodes stored as an array, after node 4 replaced node 8 at the root’s right child position. Tree view: root 12 (index 0) has children 7 (index 1) and 8 (index 2); node 7 has children 3 (index 3) and 5 (index 4); node 8 has children 2 (index 5) and 4 (index 6). Below the tree, a 7-element array shows the same values in level order: 12, 7, 8, 3, 5, 2, 4, indexed 0 through 6.

Figure 9.5: Diagram of a binary tree: root 4 (index 0) has children 7 (index 1) and 8 (index 2); node 7 has children 3 (index 3) and 5 (index 4); node 8 has a single left child 2 (index 5). Below the tree, a 6-element array shows the same values in level order: 4, 7, 8, 3, 5, 2, indexed 0 through 5.

Figure 9.7: Diagram illustrating binomial trees B0 through B3, showing how each is built by combining two copies of the previous one. B0 is a single node (2^0 = 1 node). B1 is two nodes connected vertically (2^1 = 2 nodes). B2 has a root with two children, one of which has its own child, forming 4 nodes total (2^2 = 4 nodes). B3 shows a root connected to two subtrees, each a copy of B2 (highlighted in gray ovals and labeled B2), together totaling 8 nodes (2^3 = 8 = 2×2^2).

Figure 9.8: Diagram of a binomial heap labeled heapA, showing a root list of three binomial trees connected by horizontal arrows: 18 (B0, no children), 20 (B1, one child: 1), and 19 (B3, three children: 16, 15, and 7). Under root 19: node 16 is the root of a B2 subtree with children 10 and 11, where 10 has its own child 9; node 15 has a single child 12 (B1); node 7 has no children (B0)

Figure 9.9: Diagram of a binomial heap labeled heapB, showing a root list of two binomial trees connected by a horizontal arrow: 25 (B1, one child: 13) and 17 (B2, two children: 14 and 6, where 14 has its own child 4)

Figure 9.10: Diagram showing binary place values and a binary addition example. Top table lists powers of two with their values: 2⁴=16, 2³=8, 2²=4, 2¹=2, 2⁰=1. Below, a binary addition is shown: 1011 plus 0110, with carried 1s written above the 2³ and 2² columns, giving a sum of 10001.

Figure 9.11: Diagram illustrating the merge step of combining two binomial heaps, heapA and heapB, into a single merged root list (before any consolidation). Top left, in a shaded box: heapA with root list 18 (B0), 20 (B1, child 1), and 19 (B3, children 16, 15, 7, where 16 is a B2 root with children 10 and 11, and 10 has child 9 and 15 has child 12). Top right, in a shaded box: heapB with root list 25 (B1, child 13) and 17 (B2, children 14 and 6, where 14 has child 4). Gray arrows point down from both shaded boxes to a ‘Merged List’ label. Bottom: the resulting merged root list labeled heap, showing all trees interleaved in order by degree: 18, 20 (child 1), 25 (child 13), 17 (children 14 and 6, with 14’s child 4), and 19 (children 16, 15, 7, with the same subtrees as before).

Figure 9.12: Diagram illustrating a tree or heap-like structure, with an arrow labeled “heap” pointing to the leftmost node. The top row of circular nodes are connected by rightward arrows: 18 → 20 → 25 → 17 → 19. A label “considering” sits above, with two diagonal arrows pointing down to nodes 20 and 25, indicating these two nodes are currently being considered/compared. Additional nodes branch downward from the top-row nodes, representing child relationships: 20 connects down to 1. 25 connects down to 13. 17 connects (via a diagonal line) to 14, and (via a vertical line) to 6. 14 connects down to 4. 19 connects (via diagonal lines converging from the left) to both 16 and 15; node 7 sits nearby without a visible connecting line. 16 connects (via a diagonal line) to 10, and (via a vertical line) to 11. 10 connects down to 9. 15 connects down to 12.

Figure 9.13: Diagram illustrating a tree or heap-like structure, with an arrow labeled “heap” pointing to the leftmost node. The top row of circular nodes are connected by rightward arrows: 18 → 20 → 25 → 17 → 19. A label “considering” sits above, with two diagonal arrows pointing down to nodes 20 and 25, indicating these two nodes are currently being considered/compared. Additional nodes branch downward from the top-row nodes, representing child relationships: 20 connects down to 1. 25 connects down to 13. 17 connects (via a diagonal line) to 14, and (via a vertical line) to 6. 14 connects down to 4. 19 connects (via diagonal lines converging from the left) to both 16 and 15; node 7 sits nearby without a visible connecting line. 16 connects (via a diagonal line) to 10, and (via a vertical line) to 11. 10 connects down to 9. 15 connects down to 12.

Figure 9.14: Diagram illustrating a subsequent step in the same tree/heap structure, showing the arrangement after node 20 has been removed from the main chain. The top row of circular nodes are connected by rightward arrows: 18 → 25 → 17 → 19 (node 18 leads via “heap” label arrow). A label “considering” sits above, with two diagonal arrows pointing down to nodes 25 and 17, indicating these two nodes are now being considered/compared. Additional nodes and connections: 20 sits below and to the left, connected by a diagonal arrow pointing up into 25. 1 connects down from 20. 13 connects down (vertically) from 25. 17 connects (via a diagonal line) to 14, and (via a vertical line) to 6. 14 connects down to 4. 19 connects (via diagonal lines converging from the left) to 16, 15, and 7. 16 connects (via a diagonal line) to 10, and (via a vertical line) to 11. 10 connects down to 9. 15 connects down to 12. The overall structure mirrors the earlier diagram, but node 20 has been repositioned off the main chain and now points into node 25 instead of preceding it.

Figure 9.15: Diagram illustrating a further step in the tree/heap structure, now shown as a two-level tree rooted at node 18. The top row of circular nodes are connected by rightward arrows: 18 → 25 → 19 (node 18 leads via “heap” label arrow). A label “considering” sits above, with two diagonal arrows pointing to nodes 25 and 19, indicating these two nodes are now being considered/compared. Children branching from 25 are 17, 20, and 13 (connected via diagonal and vertical lines). 17 connects further down to 14 and 6. 14 connects down to 4. 20 connects down to 1. Children branching from 19 are 16, 15, and 7 (connected via diagonal and vertical lines). 16 connects further down to 10 and 11. 10 connects down to 9. 15 connects down to 12. The structure now resembles a more balanced tree, with 25 and 19 each serving as parent nodes to their own three-node subtrees, all stemming from root node 18.

Figure 9.16: A diagram representing a binomial heap or similar tree-based data structure made of numbered circular nodes connected by lines. A horizontal arrow labeled “heap” points to a standalone node labeled 18. A long horizontal arrow points from node 18 to node 25, which acts as the root of a large tree structure. Node 25 has four direct children linked below it, arranged from left to right: Node 19 has three children, Node 16 (left) has children 10 (with child 9) and 11, Node 15 (middle) has child 12, and Node 7 (right). Node 17 has two children: Node 14 (left), which has child 4 and Node 6 (right). Node 20 has one child, node 1. Node 13: Has no children.

Figure 9.17: The diagram is split into two halves separated by a thick black rightwards arrow, showing a “before and after” state. Two separate binomial trees of order 2 (B₂) are shown side-by-side. The first B₂ Tree shows Node 17 is the root. It has an upward arrow labeled parent and a rightward arrow labeled sibling. A downward diagonal arrow labeled child points to node 14. Node 14 has a returning upward diagonal arrow back to node 17. Node 14 has a vertical arrow pointing up from its child, node 4. Node 14 also has a horizontal rightward arrow pointing to node 6. Node 6 has a vertical upward arrow pointing back to the root, node 17. Nodes 4, 6, and 14 all feature standard open structural arrows pointing downwards or outwards to indicate potential pointers. The second B₂ Tree shows Node 25 is the root, with an upward pointer and a rightward sibling pointer. It has double diagonal arrows connecting down to node 20. Node 20 has a vertical upward arrow from its child, node 1, and a horizontal rightward arrow pointing to node 13. Node 13 points vertically upward back to the root, node 25. On the right side, the two trees are merged into a single binomial tree of B₃, where the tree rooted at 17 becomes the leftmost child of the new root, 25. The new B₃ Tree shows Node 25 is now the overall root. Node 25 connects down to node 17 via double diagonal arrows. The subtree under node 17 (containing 14, 4, and 6) remains structurally identical to before but is labeled with a gray B₂ text above it. Node 17 has a horizontal rightward arrow pointing to node 20. Node 20 (and its child node 1) forms a subtree labeled with a gray B₁ text above it. Node 20 has a diagonal upward arrow pointing back to the root, node 25. Node 20 has a horizontal rightward arrow pointing to node 13. Node 13 forms a subtree labeled with a gray B₀ text above it. Node 13 has a vertical upward arrow pointing back to the root, node 25.

Figure 10.1: The main expression at the top reads: =((F₅+F₄) + (F₄+F₃)) + ((F₄+F₃) + (F₃ + F₂)). Below this equation, individual base terms (F₅, F₄, F₃, and F₂) are listed with upward-pointing arrows tracking their multiple occurrences in the expression above: F₅ points to 1 instance. F₄ points to 3 separate instances. F₃ points to 3 separate instances. F₂ points to 1 instance.

Figure 10.2: Diagram illustrating matrix multiplication, showing matrix A (2×3) multiplied by matrix B (3×2) equals matrix C (2×2). Matrix A (2 rows × 3 columns): Row 1: a₁₁, a₁₂, a₁₃. Row 2: a₂₁, a₂₂, a₂₃
Matrix B (3 rows × 2 columns): Row 1: b₁₁, b₁₂. Row 2: b₂₁, b₂₂. Row 3: b₃₁, b₃₂. Resulting matrix C (2 rows × 2 columns), where each entry is the sum of products of the corresponding row from A and column from B: C₁₁ = a₁₁ times b₁₁ + a₁₂ times b₂₁ + a₁₃ times b₃₁. C₁₂ = a₁₁ times b₁₂ + a₁₂ times b₂₂ + a₁₃ times b₃₂. C₂₁ = a₂₁ times b₁₁ + a₂₂ times b₂₁ + a₂₃ times b₃₁ .C₂₂ = a₂₁ times b₁₂ + a₂₂ times b₂₂ + a₂₃ times b₃₂.

Figure 10.3: A diagram showcasing three empty placeholder matrices side-by-side, labeled A, B, and C, typically used to introduce a matrix chain multiplication problem. The dimensions are clearly printed below each set of matrix brackets: Matrix A: 5 x 20, Matrix B: 20 x 10, and Matrix C: 10 x 100.

Figure 10.7: Diagram illustrating the matrix chain multiplication problem setup, given dimensions array [d₀, d₁, d₂, d₃, d₄, d₅]. Five matrices are shown, each labeled with its dimensions: M₀: d₀ × d₁ (labeled “Start”). M₁: d₁ × d₂. M₂: d₂ × d₃. M₃: d₃ × d₄. M₄: d₄ × d₅ (labeled “End”). The matrices are grouped by the “Split” point into two parenthesized sub-chains: (M₀ × M₁) and (M₂ × M₃ × M₄). Below, arrows show the resulting products of each sub-chain: (M₀ × M₁) collapses into a single matrix of dimensions d₀ × d₂. (M₂ × M₃ × M₄) collapses into a single matrix of dimensions d₂ × d₅

Figure 11.1: An unlabeled, undirected graph consisting of 6 circular gray nodes and 7 connecting edges. The structure forms two distinct triangular clusters connected by a central bridge: Left Cluster shows three nodes arranged in a triangle. The top-right node of this cluster serves as a hub. Right Cluster: Three nodes arranged in a triangle (one center-left, one bottom-middle, one far-right). The single edge (bridge) connects the top-right node of the left cluster to the center-left node of the right cluster, making the entire graph a single connected component.

Figure 11.2: A side-by-side comparison diagram showing two distinct 3-node graphs to illustrate the difference between undirected and directed edges. Left Graph (Undirected) consists of three circular gray nodes arranged in a triangle. The nodes are connected by standard, un-arrowed line segments. Right Graph (Directed) consists of three identically positioned circular gray nodes arranged in a triangle. The connections are represented by directional arrows (directed edges): One arrow points from the top-left node to the bottom node. One arrow points from the top-left node to the top-right node. One arrow points from the bottom node to the top-right node.

Figure 11.3: A 4×4 grid (including row and column headers) tracking edge existence from rows (source) to columns (destination). Row A shows “Exists” for columns A, B, and C. Row B shows “Exists” only for column C. Row C contains only blank cells. Directed Graph (Bottom) shows three circular gray nodes labeled A, B, and C arranged in a triangle, with arrows mapping exactly to the matrix above. Node A has a self-loop arrow curving back to itself, a directed arrow pointing down to Node B, and a directed arrow pointing right to Node C. Node B has a single directed arrow pointing up and right to Node C. Node C has no outgoing arrows.

Figure 11.4: On the left is a vertical stack of three dark-gray blocks representing the source nodes: A (top), B (middle), and C (bottom). To the right, light-gray blocks are connected horizontally by thick black arrows, showing the outgoing edges for each vertex. Row A: Node A points to a chain of neighbors: A right arrow to B with a right arrow to C. Row B: Node B points to a single neighbor, C. Row C: Node C has no arrows or attached blocks.

Figure 11.5: An undirected graph with 6 circular gray nodes labeled A through F, connected by 6 edges to form a single continuous loop or ring structure. The order is A, B, D, F, E, C, back to A. A rectangular box at the bottom textually displays two graph traversal sequences starting from Node A. Breadth First Traversal: A B C D E F. Depth First Traversal: A B D F E C

Figure 11.6: Diagram titled “Initial State” showing a graph with four nodes and a state table, illustrating the starting point of a shortest-path algorithm. Four circular nodes labeled A, B, C, and D are connected in a cycle: A to B, edge weight 4. B to C, edge weight 9. C to D, edge weight 5. D to A, edge weight 6. A table is below the graph, with columns for each node (A, B, C, D) and four rows: Node: A, B, C, D. Visited: F, F, F, F. Dist: 0, Inf, Inf, Inf. Pre: Nil, Nil, Nil, Nil.

Figure 11.7: Four-panel diagram showing Iterations 1 through 4 of a shortest-path algorithm (e.g., Dijkstra’s) on the same graph, each with the graph and its state table. Graph structure (identical in all four panels): Four nodes labeled A, B, C, D connected in a cycle: A–B (weight 4), B–C (weight 9), C–D (weight 5), D–A (weight 6). Iteration 1: Visited: A=T, B=F, C=F, D=F. Dist: A=0, B=4, C=6, D=Inf. Pre: A=Nil, B=A, C=A, D=Nil. Iteration 2: Visited: A=T, B=T, C=F, D=F
Dist: A=0, B=4, C=6, D=13. Pre: A=Nil, B=A, C=A, D=B. Iteration 3: Visited: A=T, B=T, C=T, D=F. Dist: A=0, B=4, C=6, D=11. Pre: A=Nil, B=A, C=A, D=C. Iteration 4: Visited: A=T, B=T, C=T, D=T. Dist: A=0, B=4, C=6, D=11. Pre: A=Nil, B=A, C=A, D=C. Progression shows the algorithm visiting A first, then B, then C, then D, updating D’s distance from infinity to 13 (via B) and then improving it to 11 (via C) before finalizing all nodes as visited with no further changes.

Figure 12.1: An unweighted, undirected graph with eight nodes labeled A through H, connected as follows: A connects to B, C, and E. B connects to A, C, D, and G. C connects to A, B, and E. D connects to B, E, and G. E connects to A, C, D, and H. F connects to G and H. G connects to B, D, and F. H connects to E and F. The layout places A, B, and C across the top; D and E in the middle; F to the right; and G and H along the bottom, with two crossing lines (D–E and B–G, and E–H and F–G) in the lower-middle portion of the diagram.

Figure 12.2: On the left, an unweighted, undirected graph with eight nodes labeled A through H, connected as follows: A connects to B, C, and E. B connects to A, C, D, and G. C connects to A, B, and E. D connects to B, E, and G. E connects to A, C, D, and H. F connects to G and H. G connects to B, D, and F. H connects to E and F. The layout places A, B, and C across the top; D and E in the middle; F to the right; and G and H along the bottom, with two crossing lines (D–E and B–G, and E–H and F–G) in the lower-middle portion of the diagram. The right diagram substitutes numbers for the letters where A=2, B=4, C=3, D=5, E=1, F=7, G=6, and H=8.

Figure 12.3: Diagram of three standard logic gate symbols in solid black, left to right. AND gate is a flat-backed shape with a rounded (D-shaped) front, two input lines on the left and one output line on the right, labeled “AND” below. OR gate is a curved-back shape tapering to a pointed front, two input lines on the left and one output line on the right, labeled “OR” below. NOT gate is a triangle pointing right with a small circle (bubble) at its tip, one input line on the left and one output line extending from the circle, labeled “NOT” below.

Figure 12.4: Logic circuit diagram combining an AND gate, a NOT gate, and an OR gate to compute the expression (X AND Y) OR (NOT Z). Inputs X and Y feed into an AND gate, producing the term “X AND Y.” Input Z feeds into a NOT gate (triangle with a bubble), producing “NOT Z.” The outputs of the AND gate and the NOT gate both feed into an OR gate. The OR gate’s output is the final output of the circuit.

Figure 12.5: Logic circuit diagram combining AND, NOT, and OR gates to compute the expression (X AND Y) OR ((NOT X) AND Z). Inputs X and Y feed into the top AND gate, producing “X AND Y.” The X input also branches downward to feed a NOT gate. The NOT gate’s output (NOT X) feeds, along with input Z, into a second AND gate below, producing “(NOT X) AND Z. The outputs of both AND gates feed into an OR gate on the right The OR gate’s output is the final output of the circuit, representing (X AND Y) OR ((NOT X) AND Z).

Figure 12.6: Diagram illustrating a bin packing problem. On the left is an empty rectangular bin outlined in black, labeled “Capacity 10” above and “Bin 0” below. To the right are ten gray item blocks of varying heights (sized proportionally to their labeled value), representing items to be packed into bins, arranged in three columns. Column 1: items sized 3, 2, and 7. Column 2: items sized 3, 2, and 5. Column 3: items sized 2, 3, 2, and 1. Each block’s height visually corresponds to its numeric size, with larger numbers (like 7 and 5) shown as taller rectangles.

Figure 12.7: Diagram showing a completed bin packing solution across four bins, each with capacity 10, labeled “Capacity 10” above the set. Each bin is a vertical rectangle divided into gray segments (one per packed item, labeled with its size) separated by thin white lines, with any remaining unused capacity shown as white space at the top of the bin. Bin 0: filled with items 1, 2, 3, and 3 (stacked top to bottom), totaling 9 of 10 capacity, with a small unused gap at the top. Bin 1: filled with items 2, 2, and 3, totaling 7 of 10 capacity, with unused space at the top. Bin 2: filled with one item, 5, totaling 5 of 10 capacity, with unused space at the top. Bin 3: filled with items 2 and 7, totaling 9 of 10 capacity, with a small unused gap at the top.

Figure 12.8: Diagram showing an optimal bin packing solution using three fully-filled bins, each with capacity 10, labeled “Capacity 10” above the set. Each bin is a vertical rectangle fully packed with gray segments (one per item, labeled with its size) separated by thin white lines, with no unused space in any bin. Bin 0: filled with items 2, 5, and 3 (stacked top to bottom), totaling exactly 10 of 10 capacity. Bin 1: filled with items 2, 2, 3, and 3, totaling exactly 10 of 10 capacity. Bin 2: filled with items 1, 2, and 7, totaling exactly 10 of 10 capacity.

Figure 12.9: Diagram showing an alternative optimal bin packing solution using three fully-filled bins, each with capacity 10, labeled “Capacity 10” above the set. Each bin is a vertical rectangle fully packed with gray segments (one per item, labeled with its size) separated by thin white lines, with no unused space in any bin — showing a different valid grouping of the same items that also achieves a perfectly optimized three-bin packing. Bin 0: filled with items 3 and 7 (stacked top to bottom), totaling exactly 10 of 10 capacity. Bin 1: filled with items 2, 3, and 5, totaling exactly 10 of 10 capacity. Bin 2: filled with items 1, 2, 2, 2, and 3, totaling exactly 10 of 10 capacity.

Figure 12.10: Diagram titled “checkIfHalts (program, input)” illustrating a conceptual halting-problem checker as a box. Two inputs, P and i, enter a rectangular box labeled “simulate.” Inside, a black box labeled “P” represents the simulated program running on input i. Two arrows exit this inner box: One labeled “P halts on i,” leading to an output arrow labeled “yes.” One labeled “P runs forever on i,” leading to an output arrow labeled “no.”

Figure 12.11: Diagram titled “loopIfHalts (program, input)” illustrating the paradoxical construction used in the halting problem proof. Two inputs, P and i, enter a rectangular box and both feed into a black inner box labeled “checkIfHalts.” Two arrows exit this inner box: One labeled “yes,” leading to an output arrow labeled “Run forever.” One labeled “no,” leading to an output arrow labeled “halts”

Figure 12.12: Diagram titled “M(program)” illustrating the final self-referential construction in the halting problem proof. A single input, P, enters a rectangular box and splits into two branches: One branch feeds directly into a black box labeled “loopIfHalts.” The other branch feeds into a black box labeled “Copier,” whose output also feeds into “loopIfHalts.” Two arrows exit “loopIfHalts”: one leading to an output labeled “Run forever,” and one leading to an output labeled “halts.”