F26 1332 Exam 2

TOPICS: SkipLists, AVLs, 2-4 Trees, Iterative Sorts, MergeSort, Quicksort, QuickSelect, RadixSort, Intro to Graphs, DFS, BFS, Dijkstra's

What is an AVL?

A data structure that is essentially a self-balancing Binary Search Tree.

• every node must maintain a balance factor of -1, 0, or 1.

How do you find the balance factor of a node?

Balance Factor = Height(left subtree) - Height(right subtree)

• Calculating Height: count the # of edges on the longest downward path from that node to a leaf node

What if a node’s balance factor is +2?

The AVL is left-heavy and needs to be rebalanced using a rotation.

• Perform a Single Right Rotation: if the left child’s BF is +1 or 0

• Perform a Left-Right Rotation: if the left child’s BF is -1 (rotate left child first, then rotate the unbalanced node right)

What if a node’s balance factor is -2?

The AVL is right-heavy and needs to be rebalanced using a rotation.

• Perform a Single Left Rotation: if the right child’s BF is -1 or 0

• Perform a Right-Left Rotation: if the right child’s BF is +1

What does it mean for an algorithm to be “in-place”?

The algorithm does not require extra memory (additional space) for storing a copy of the input dataset.

What does it mean for an algorithm to be “stable”?

The algorithm preserves the relative order of items with equal values. Items of the same value stay in same relative position.

What would be some examples of an Unstable Algorithm?

QuickSort, Heapsort, Selection Sort—they perform long-distance swaps across the array.

What does it mean for an algorithm to be “adaptive”?

An algorithm that is adaptive runs significantly faster if the input data is pre or completely sorted.

How does Selection Sort work? (hint: “what gets selected”)

• Divides the array into [ “sorted part” | “unsorted part” ]

• Picks out the smallest item from the unsorted section (scans from L → R)

• Repeatedly moves the smallest item to the front updating the sorted section as you go

How does Bubble Sort work? (hint: “what gets bubbled”)

• Compares neighbors starting at the front of the array

• Swaps if out of order and moves to the next element to repeat the comparison

• Once it hits the end of the array, the algorithm resets back to the beginning and repeats the entire process

• Bubble: largest unsorted item gets bubbled up to the end of the list every pass

How does Cocktail Shaker Sort work?

• First Pass L → R: bubble sort—bubbles the largest unsorted item to the right

• Second Pass R → L: reverse bubble sort—bubbles the smallest unsorted item to the left

• Repeats.

How does Insertion Sort work?

• Assumes the 1st item is sorted

• Picks the next unsorted item

• Scans through the sorted section from right to left

• Drops it into the correct slot and picks the next unsorted element