CMSC 401 Exam 2

Binary Search Tree (BST)

A binary tree where for every node: all values in the left subtree are smaller and all values in the right subtree are larger. This ordering property allows efficient searching.

Heap

A complete binary tree that satisfies the heap property: in a max heap every parent is greater than or equal to its children, and in a min heap every parent is less than or equal to its children.

Difference between BST and Heap

A BST maintains global ordering (left < node < right) enabling efficient searching. A heap only enforces parent-child ordering and is optimized for quickly accessing the minimum or maximum element.

Breadth-First Search (BFS)

A graph traversal algorithm that visits nodes level by level, exploring all neighbors of a node before moving deeper. It uses a queue.

Depth-First Search (DFS)

A graph traversal algorithm that explores as far as possible down one branch before backtracking. It typically uses recursion or a stack.

Difference between BFS and DFS

BFS explores nodes level by level using a queue and finds shortest paths in unweighted graphs. DFS explores deeply along branches using a stack or recursion.

Dijkstra’s Algorithm

A shortest path algorithm that finds the minimum distance from a source vertex to all other vertices in a weighted graph with non-negative edge weights.

Steps of Dijkstra’s Algorithm

Initialize source distance to 0 and others to infinity, repeatedly select the unvisited vertex with the smallest distance, update its neighbors’ distances, and mark the vertex as visited.

Data structure used in Dijkstra’s Algorithm

A priority queue (usually implemented with a min heap) is used to efficiently select the vertex with the smallest temporary distance.

Limitation of Dijkstra’s Algorithm

It does not work correctly with negative edge weights because it assumes once a node's shortest distance is finalized it cannot decrease.

Binary Search Tree search complexity

O(log n) in a balanced BST but O(n) in the worst case if the tree becomes skewed.

Heap main use

Heaps are commonly used to implement priority queues and efficiently retrieve the minimum or maximum element.

Heap property

The rule that in a max heap every parent node is greater than or equal to its children, and in a min heap every parent node is less than or equal to its children.

Complete binary tree

A tree where every level is full except possibly the last, and nodes in the last level are filled from left to right.

BFS data structure

BFS uses a queue to keep track of the next nodes to visit.

DFS data structure

DFS uses a stack or recursion to explore deeper paths first.

Time complexity of BFS

O(V + E), where V is the number of vertices and E is the number of edges.

Time complexity of DFS

O(V + E), where V is the number of vertices and E is the number of edges.

Time complexity of Dijkstra (priority queue)

O((V + E) log V)

Heap build complexity

Building a heap from an unsorted array takes O(n) time.

Heapsort worst-case complexity

O(n log n)

Preemptive split in B-trees

A technique where a full node is split before inserting a new key during traversal to maintain B-tree properties.

Minimum keys in a B-tree node

For a B-tree with minimum degree t, each node (except the root) must have at least t−1 keys.

Maximum keys in a B-tree node

For a B-tree with minimum degree t, each node can have at most 2t−1 keys.

Maximum children in a B-tree node

A node in a B-tree can have at most 2t children.

How to check if a B-tree is valid

Verify that each node has a valid number of keys, the number of children equals keys + 1, and all leaves are at the same depth.

Effect of adding a constant to all edge weights

Adding the same constant to every edge weight can change shortest paths because paths with more edges increase in total weight more.

Why adjacency lists are used with Dijkstra’s algorithm

Adjacency lists store only existing edges, making traversal efficient for sparse graphs.

Connected component in a graph

A connected component is a set of vertices where each vertex is reachable from every other vertex in that set.

How DFS finds connected components

Run DFS from an unvisited node and mark all reachable nodes as part of the same component, then repeat for other unvisited nodes.

Property of preorder traversal in BSTs

Given the preorder traversal of a BST, the structure of the tree is uniquely determined.

Space complexity of Heapsort

Heapsort sorts in place and requires only O(1) additional memory.

Why building a heap is O(n) instead of O(n log n)

Most heapify operations occur near the bottom of the tree where subtrees are small, reducing the total work required.

Difference between shortest paths in weighted vs unweighted graphs

BFS finds shortest paths in unweighted graphs, while Dijkstra’s algorithm is used for weighted graphs.

In sparse graphs the best implementation for a graph (relating to search time complexity) is…

...adjacency List

In dense graphs the best implementation for a graph (relating to search time complexity) is…

…adjacency matrix

How MaxHeapify works

Restores the max-heap property for a node. It compares the node with its left and right children, swaps it with the largest child if necessary, and recursively continues this process down the tree until the heap property is satisfied.

How Heapsort works

Sorts an array by first building a max heap from the elements.

Repeatedly swaps the root (largest element) with the last element in the heap, reduces the heap size by one, and calls MaxHeapify to restore the heap property.

This continues until the array is sorted.