Question 1)

Choose one of the exercised from the award winning book Computer Science Unplugged. Record a creative presentation of this material. This may consist of:

• A video of a session with children where you demonstrate the exercise.
• A creative dance - See Erik Stern and Karl Schaffer's TEDx Video
• Props and materials
• Any other excellent creative idea

Question 2)

a) Explain how a DFS can be used to look for cycles in a graph.

b) Explain why DFS trees cannot contain cross edges. (It may help to think about what it would mean if they did contain cross edges).

c) Prove that any connected graph G with n vertices and n-1 edges must be a tree.

(Hint: Use a proof by contradiction. Show that the assumption that G is not a tree, ie that G contains a cycle, will lead to the contradiction that G is not connected).

Question 3)

(a) What is the difference between a polynomial time algorithm and an exponential time algorithm?

(b) Give three examples of problems for which only inefficient algorithmic solutions exist.

(c) Given an example of a problem for which an algorithm of complexity O(log₂n) exists. Explain why the algorithm is so efficient.