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(log2n) exists. Explain why the algorithm is so efficient.