Problem 1

What is wrong with the following argument?

Let T  : ℕ  →  ℕ. The following equations have the solution T(n)=Θ(n):

• T(0)=0
• T(n)=n + T(n − 1), if n > 0.

Proof by induction on n:

• Base case: T(0)=0 = Θ(0).

• Step case (n > 0):

  T(n)
    =
  n + T(n − 1)
    = { Inductive hypothesis. }
  n + Θ(n − 1)
    =
  Θ(n).

Solution.

Problem 2

Consider the following procedure:

multi-pop(n,s)
   Pops the first n elements from the stack s (n ∈ ℕ).
   Precondition: n ≤ the size of s.

   if n > size of s then
     raise error

   while n > 0 do
     pop s
     n ← n - 1

What is the worst-case time complexity of multi-pop? What is the best possible amortised time complexity of multi-pop?

When analysing the time complexity, assume that the stack is implemented as a singly linked list.

Solution.

Problem 3

Implement (preferably using pseudo code) a program which checks if a text file contains both some word w and its mirror image reverse(w) (e.g. both ropa and apor). Use a hash table. Analyse the program's time complexity under two assumptions:

• A perfect hash function.

• A hash function which is as bad as possible.

Do not blindly assume that hash functions compute in constant time.

Solution.

Problem 4

Directed unweighted graphs can be represented textually as follows:

node1 node2 apa
node2
apa node2 apa

Every line starts with a node identifier, followed by the node identifiers of all direct successors of the node.

Implement (preferably using pseudo code) a program which parses such a file and constructs a representation of the graph in memory. Be explicit about how you represent the graphs. Make sure that finding a direct successor of a node does not involve looking up a string in a map.

You can assume that the files do not contain errors (such as syntax errors or undeclared node identifiers), and that the graphs are well-formed (no duplicated edges).

Solution.

Problem 5

Assume that there is an algorithm which, in linear time, can decide whether a graph contains a Hamiltonian cycle. Design an algorithm which decides whether a graph contains a Hamiltonian path, prove that it is correct, and analyse its time complexity.

Solution.

Problem 6

The edge set E of a graph G = (V, E) can be seen as a relation R between nodes, by defining that u R v holds iff (u, v) ∈ E.

Design an algorithm which decides if the edge set of a directed, unweighted graph represents an equivalence relation. Explain why the algorithm is correct and analyse its time complexity.

Solution.

Problem 7

Assume that V₁ and V₂ partition the vertex set V of some connected, undirected, weighted graph G = (V, E). Let us define the spacing of this partition as

  min {c_v₁,v₂ | v₁  ∈  V₁, v₂  ∈  V₂, (v₁,v₂)  ∈  E},

where c_v₁,v₂ is the cost of the edge (v₁,v₂). (In other words, the spacing is the cost of any of the cheapest edges connecting the two partitions.)

Design an algorithm which, given a connected, undirected, weighted graph G = (V, E) with |V|  ≥  2, calculates

  max {spacing of (V₁,V₂) | V₁, V₂ partition V}.

In other words, the algorithm should find the largest possible spacing. Explain why the algorithm is correct and analyse its time complexity.

Hint: Consider using a minimum spanning tree.

Solution.

Problem 8

Think of a real-world problem which can be solved using some graph algorithm (possibly in combination with other algorithms). Solve the problem, explain why your solution is correct, and analyse the time complexity of your solution.

Problem 9

Implement an operation which reverses a binary search tree. Explain why it is correct. Analyse its time complexity.

Modify the binary tree data structure so that reversal can be implemented in constant time. The asymptotic worst-case time complexities of other operations should not change.

Solution.

Problem 10

Implement a procedure which checks if a binary tree is an AVL tree (i.e. a search tree satisfying the AVL tree balancing invariant). The procedure's worst-case big-O time complexity should be as low as possible (assuming that tree elements can be compared in constant time).

Solution.

Problem 11

Prove that the height of an AVL tree with n nodes is O(log n).

Hint: Establish a lower bound on the number of nodes in an AVL tree of a given height, using the fact that 1+ϕ = ϕ², where ϕ is the golden ratio.

Solution.

Problem 12

Implement one quadratic and one efficient sorting algorithm. Compare the run-times of these implementations and an optimised implementation from a standard library. Document your results.

Can you think of a good way to test your implementations?

Solution.

Problem 13

Out of the sorting algorithms you know, which would sort one million 32-bit integers in the least amount of time? Back up your answer/guess with a coherent argument.

Solution.

Problem 14

Why is the following partitioning strategy for quicksort bad?

• Use a median-of-three strategy to find the pivot p.

• Partition the remaining elements R into S₁ = {x | x ∈ R, x ≤ p} and S₂ = {x | x ∈ R, x > p}.

Solution.