Algorithms & complexity worksheet with answers

What is the time complexity of depth-first search on a graph stored as adjacency lists?

1. AO(V²)
2. BO(V × E)
3. CO(E log V)
4. DO(V + E)

What is a brute-force algorithm?

1. AOne that always uses recursion
2. BOne that guesses an answer at random
3. COne that tries all possible candidate solutions
4. DOne that runs on many processors

What is an algorithm?

1. AAny computer program that has a graphical interface
2. BA data structure that stores numbers
3. CA finite sequence of well-defined steps that solves a problem
4. DA programming language designed for writing mathematical formulas

What is the amortised time complexity of appending to a dynamic array that doubles its capacity when full?

1. AO(1)
2. BO(n²)
3. CO(log n)
4. DO(n)

How much stack space does a simple recursive factorial function fact(n) = n × fact(n − 1) use?

1. AO(n)
2. BO(n²)
3. CO(log n)
4. DO(1)

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

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

Why does binary search not give O(log n) time on a singly linked list?

1. AComparisons on linked list nodes are slower
2. BReaching the middle element takes O(n) steps, since there is no direct index access
3. CLinked lists cannot be sorted
4. DBinary search needs at least twice the memory

For which knapsack variant does the greedy rule "take items in order of value per weight" always give an optimal answer?

1. AThe fractional knapsack, where items may be split
2. BNeither variant
3. CThe 0/1 knapsack, where items must always be taken whole
4. DBoth variants