Final Exam Review: Data Structures and Algorithms

These flashcards cover critical concepts related to Red-Black Trees, graphs, traversal algorithms, spanning trees, and dynamic programming as per the provided lecture notes.

What are the properties of a Red-Black Tree?

1. Every node is either red or black. 2. The root node and leaves (NIL) are black. 3. If a node is red, then both its children are black. 4. All paths from any node to its descendant leaves contain the same number of black nodes.

Why do we use Red-Black Trees instead of regular binary search trees?

Red-Black Trees maintain their height at O(log n), which guarantees O(log n) time complexity for operations such as search, insert, and delete, preventing the O(n) worst-case scenario of skewed trees.

What defines a Directed Acyclic Graph (DAG)?

A Directed Acyclic Graph (DAG) is a graph with directed edges that does not contain any cycles.

What are the two ways to represent graphs?

Graphs can be represented as an Adjacency Matrix or an Adjacency List.

What is an advantage of using an Adjacency List?

An Adjacency List uses O(V + E) space, which is more efficient than O(V^2) when the graph has fewer edges.

What is the traversal order in Breadth-First Search (BFS)?

BFS explores level by level, visiting all immediate neighbors before moving to the next level.

What is a Minimum Spanning Tree (MST)?

A Minimum Spanning Tree is a spanning tree that has the smallest total edge weight among all possible spanning trees.

What is the main difference between Dijkstra's Algorithm and Bellman-Ford Algorithm?

Dijkstra's Algorithm works with graphs having non-negative edge weights, while Bellman-Ford can handle negative edge weights and detect negative cycles.

What is the relax operation in shortest path algorithms?

The relax operation updates the distance to a vertex if a shorter path is found via another vertex.

What are the components of Dynamic Programming?

1. Optimal Substructure. 2. Overlapping Subproblems.

What is the key idea of the Bottom-Up approach in Dynamic Programming?

To solve all smaller problems first and build up to the final solution iteratively.

How is Dynamic Programming used in the Fibonacci sequence calculation?

By storing previously computed Fibonacci numbers to avoid redundant calculations, achieving a time complexity of O(n) with a Bottom-Up approach.

Prims Algorithm Compelxity

Array:O(V^2) with an adjacency matrix; O(E log V) with adjacency list and priority queue.

Binary heaps: O(E log V)

Kruksals Algorithm Complexity

O(E log V) or O(E log V), depending on the data structure used for the disjoint set operations and the graph representation.

overall complexity is O(E log E + E log V)

Dijkstra’s algorithm complexity

Array or linked list is O(|V|² + |E|)

sparse graph and min-Priority Queue with binary minheap is is O((|E| + |V|) log|V|)

Bellman Ford Complexity

overall complexity is O(|V| * |E|)

sparse graph is O(|V|²

complete graph is O(|V|³)

Red Black tree complexity

The average and worst-case time complexity for search, insertion, and deletion operations in a Red-Black Tree is O(log n), maintaining balanced structure.

AVL tree

AVL Tree is a Binary Search Tree where the difference in height between the left and right subtrees of any node is at most 1

Pros/Cons Adjacency List

Pros: Space-efficient for sparse graphs (few edges).

Faster iteration over a node’s neighbors.

Dynamic — easy to add/remove edges.

Cons: Slower to check if a specific edge exists (O(n) in worst case).

Slightly more complex to implement than a matrix.

Pros/Cons Adjacency matrix

Pros: Fast edge lookup: check if edge exists in O(1) time.

Simple and easy to implement.

Good for dense graphs (many edges).

Cons: Uses more space: O(n²), even if the graph is sparse.

Iterating over neighbors takes O(n) time per node.

Less efficient for dynamic graph changes (like inserting/removing edges).