Data Structures and Algorithms Lecture Flashcards

A set of practice flashcards covering core concepts from data structures and algorithms, including sorting complexities, tree properties, and complexity analysis.

How is the abstract class Stack structure defined in the lecture notes?

abstract class Stack { abstract void push(T item); abstract T pop(); }

According to the transcript, what is the distinction between Generics and an ADT in terms of guarantees?

Generics guarantee each operation runs in $O(1)$ time, whereas an ADT guarantees only correctness, not speed.

What is the expected running time for Quick Sort on average over random pivot choices, and what is its potential worst-case?

The expected time is $O(n ext{ log }(n))$, but a specific input may take $O(n^2)$.

When is it appropriate to use a sorting strategy for data with many duplicates but an unknown range?

When the data contains many duplicates but the range is unknown.

Why might Radix Sort be implemented as unstable according to the notes?

To avoid the overhead of maintaining insertion order within buckets.

What is one reason provided for why a recurrence might not be solved using the Master Theorem?

The Master Theorem does not apply in certain cases, such as when $n / ext{ log }(n)$ is not asymptotic.

What is a mandatory property for NIL leaves in a Red-Black Tree?

Every NIL leaf is black.

What is the result of an in-order traversal of a Binary Search Tree?

It lists all keys in sorted order.

Which specific algorithm is identified for graph operations in the transcript?

Kruskal’s algorithm.

In a tree with $n$ vertices, how many edges are present?

$$n - 1$$

What is the stated running time for Fibonacci when memoization is not considered helpful in the given context?

Still $ext{Θ}(2^n)$

If an algorithm is mentioned as having a best-case running time of $O(n ext{ log }(n))$, what does that imply about the best-case bound?

The best-case running time must also be $O(n ext{ log }(n))$.

How is the $ext{Θ}$ bound determined in a general case?

The average case determines the $ext{Θ}$ bound.

What complexity is associated with scanning the adjacency list of each vertex in a graph?

Scanning the adjacency list of each vertex is represented as a fundamental operation, often linked to complexity bounds like $ext{Θ}(n)$ or $O(n^2)$ depending on the graph density.