Discrete Structures

Assignment 1 HIT 400 – Discrete Structures This assignment is worth 20 % of the assessment for this unit. Late submissions will not be accepted unless prior arrangements have been made. Show all working and explanations. Remember to write sentences. Successfully completion of tutorial exercises is worth 20% of your mark Question 1 ( 4 0 Marks) 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 A ny other excellent creative idea Question 2 (10 Marks) Explain how a DFS can be used to look for cycles in a graph. Explain why DFS trees cannot contain cross edges. (It may help to think about what it would mean if they did contain cross edges). Prove that any connected graph G with n vertices and 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 ( 10 Marks) Write the adjacency matrix for each graph in Figure 1. Figure 1 Question 4 (10 Marks ) For the graph in Figure 1(d), determine to find the number of paths of length 2 from node 2 to node 6. For the graph in Figure 1(a), count the number of paths of length 3 from vertex 5 to vertex 2. Check your answer by calculating . Question 5 ( 15 Marks) Prove that contains edges using mathematical induction. (5 marks) Hence prove that in a simple graph, for all possible graphs of order n. (2 marks) Consider the following statement. If and then . Either prove the statement or provide a counter example. ( 3 marks) Question 6 (15 Marks) What is the difference between