Algorithms and Data Structures Review

Flashcards covering asymptotic notation, sorting algorithms (Selection, Bubble, Heapsort), BST traversals and construction, RPN, Graph theory, Hashing, Huffman coding, and algorithmic complexities based on the exam answer key.

Using the definition of asymptotic notation, what specific values of $c_1$, $c_2$, and $n_0$ prove that $n^2 - 2n = \Theta(n^2)$?

$c_1 = 1/3$, $c_2 = 1$, and $n_0 = 3$ (Note: $1/2, 1, 4$ is also valid)

Order the following functions from slowest-growing to fastest-growing: (1) $n \cdot \log(n)$, (2) $1$, (3) $n$, (4) $n^{0.9}$, (5) $n!$, (6) $\log^3(n)$

2, 6, 4, 3, 1, 5 ($1$; $\log^3(n)$; $n^{0.9}$; $n$; $n \cdot \log(n)$; $n!$)

What is the result of the first pass of ascending Selection Sort on the sequence: $3, 5, 4, 6, 1, 2, 0$?

$$0, 5, 4, 6, 1, 2, 3$$

What is the result of the first pass of Bubble Sort on the sequence: $6, 2, 5, 9, 8, 3, 6, 2$?

$$2, 5, 6, 8, 3, 6, 2, 9$$

In a Heapsort procedure using a MAX-heap, what is the state of the array $17, 14, 11, 5, 6, 2, 8, 9$ after 3 steps (the three largest elements placed at the end)?

$$9, 6, 8, 5, 2, 11, 14, 17$$

After applying the BUILD-MAX-HEAP algorithm to the array $7, 15, 4, 10, 3, 9, 13, 2, 1, 8$, what is the resulting sequence?

$$15, 10, 13, 7, 8, 9, 4, 2, 1, 3$$

Define the order of visits in a PREORDER Binary Search Tree (BST) traversal.

root, left subtree, right subtree

What is the POSTORDER traversal of a BST with root $10$, where $10 \rightarrow L:5$ ($5 \rightarrow L:3$ ($3 \rightarrow L:1$), $5 \rightarrow R:7$) and $10 \rightarrow R:15$ ($15 \rightarrow L:14$, $15 \rightarrow R:25$)?

$$1, 3, 7, 5, 14, 25, 15, 10$$

If keys $15, 8, 17, 18, 19, 10, 9, 4, 20, 14$ are inserted into an empty BST, how many nodes are in the subtree rooted at the RIGHT child of the LEFT child of the root?

3 nodes (The subtree rooted at node 10, containing {10, 9, 14})

What is the Reverse Polish Notation (postfix) for the expression: $((1+3)/2+(12-2) \times 3)/2$?

1 3 + 2 / 12 2 - 3 \times + 2 /

Given the graph vertices $V = \{1,2,3,4,5,6\}$ and edges $E = \{(1,2),(2,1),(1,4),(1,3),(3,5),(5,3),(4,5),(5,6)\}$, what is row 1 of the adjacency matrix?

0 1 1 1 0 0

What is the edit distance (Levenshtein) between the strings ARM and RAMA?

3

What is the phenomenon in linear probing hashing where long, merging runs of occupied cells are created?

Primary clustering

What is the worst-case time complexity for lookup and deletion in Cuckoo hashing?

$$O(1)$$

How many total bits are required to encode a symbol in a Hamming code with distance 3 and an alphabet size of 24?

9 bits (5 information bits + 4 check bits)

What are the primary properties of Huffman coding regarding its codewords and optimality?

It is an optimal prefix-free code with variable-length codewords that minimizes the average total encoded length.

What are the disadvantages of using an adjacency matrix to represent a graph?

It uses $O(n^2)$ memory regardless of the number of edges (wasteful for sparse graphs) and iterating over a vertex’s neighbors costs $O(n)$.

Why is the statement 'Insertion sort, bubble sort, and radix sort all have $O(n^2)$ worst-case complexity' false?

Radix sort does not have $O(n^2)$ complexity; it runs in $O(d \cdot (n+k))$ time.

Why is a binary heap NOT considered an efficient dictionary data structure?

Because searching for an arbitrary key in a binary heap takes $O(n)$ time.

What is the average-case complexity of interpolation search on uniformly distributed data?

$$O(\log \log(n))$$

In which data structure can the maximum element be found in $O(\log(n))$ expected time?

A treap (the maximum is the rightmost node)

Which sorting algorithm has the smallest worst-case complexity: heap sort, insertion sort, or quicksort?

Heap sort ($O(n \log(n))$)