Algorithms & complexity worksheet with answers

What are the three steps of a divide-and-conquer algorithm?

1. ASort, search, return
2. BDivide, conquer, combine
3. CRead, compute, write
4. DGuess, check, repeat

A loop starts with i = 1 and doubles i each iteration until i > n. How many iterations does it run?

1. AAbout n²
2. BAbout log₂ n
3. CAbout n / 2
4. DAbout n

Which notation describes a lower bound on growth?

1. Ao (little o)
2. BΘ (Big Theta)
3. CΩ (Big Omega)
4. DO (Big O)

Why does dynamic programming give no real speed-up for merge sort?

1. AMerge sort is already O(n)
2. BDynamic programming only works on graph problems, not on arrays
3. CIts subproblems do not overlap, so there is nothing to reuse
4. DMerge sort has no recursive structure

Which algorithm finds the shortest paths from one source in a graph with non-negative edge weights?

1. AKruskal's algorithm
2. BDepth-first search
3. CBellman–Ford is required in all cases
4. DDijkstra's algorithm

How does Prim's algorithm build a minimum spanning tree?

1. AIt runs breadth-first search and keeps the BFS tree
2. BIt sorts all edges by weight and adds each one unless it would form a cycle in the forest
3. CIt grows one tree from a start vertex, adding the cheapest edge that leaves the tree
4. DIt removes the most expensive edge until no cycles remain

What would follow if someone found a polynomial-time algorithm for one NP-complete problem?

1. AThe halting problem would become decidable
2. BOnly that one problem would move into P
3. CEvery problem in NP could be solved in polynomial time, so P = NP
4. DAll exponential-time algorithms would immediately run in linear time

Shortest simple paths can be found in polynomial time. What is known about finding the longest simple path between two vertices in a general graph?

1. AIt is undecidable
2. BIt can be solved by Dijkstra's algorithm with negated weights
3. CIt is always solvable in O(V + E)
4. DIt is NP-hard