cs320 final quiz study

What is a requirement for topological sort?

Graph must be a DAG (Directed Acyclic Graph)

What makes a valid topological order?

All edges must go from earlier to later in the order

Which is better for sparse graphs: adjacency list or matrix?

Adjacency list

Why not use adjacency matrix for sparse graphs?

It uses O(V²) space which is wasteful

What makes a graph non-bipartite?

It contains an odd-length cycle

What does Dijkstra’s algorithm do?

Finds shortest path in weighted graphs

What data structure does Dijkstra use?

Priority Queue (Min-Heap)

What does Prim’s algorithm do?

Builds Minimum Spanning Tree starting from one vertex

What does Kruskal’s algorithm use?

Sorted edge list and Union-Find

BFS vs DFS: which guarantees shortest path?

BFS (in unweighted graphs)

BFS vs DFS: which uses a queue?

BFS uses a queue, DFS uses a stack or recursion

What is Counting Sort’s time complexity?

O(n + k)

Why might Counting Sort fail?

Input contains negative integers

How many edges in a tree with n vertices?

n - 1

What is the approximate sum of the Harmonic series?

ln(n) + 0.577

Expected number of rolls to get a 3 on a fair die?

6

How to get count of 3 from cumulative array [2, 2, 4, 6, 7, 8]?

4 - 2 = 2 (3 appears 2 times)