COMP SCI 2201 & 7201 Algorithm and Data Structure Analysis Semester 1, 2021 Minimum Spanning Trees, Euler Path, Undecidable Problems, and Turing Machines Exercise 1 Kruskal’s Algorithm Compute a minimum spanning for the following graph using Kruskal’s algorithm. Show the status of your partial minimum spanning tree after each edge insertion and indicate for each edge whether it is included in the minimum spanning tree. 4 5 4 3 1 5 6 2 8 8 v1 v2 v3 v4 v5 v6 v7 v8 Exercise 2 Euler tours of directed graphs A Hamiltonian tour is a tour that visits every node of a strongly directed graph just once. Determining if a Hamiltonian tour exists is an NP-Complete problem. In contrast an Euler tour of a strongly connected directed graph G = (V,E) is a cycle that traverses each edge of G exactly once, although it may visit a node more than once. Answer the following questions: • Show that G has an Euler tour if and only if the in-degree of every node v equals the out degree of v. • Describe an O(m) (where m is the number of edges in G) algorithm to find an Euler tour of G if such a tour exists (Hint: Merge edge-disjoint cycles). 1 COMP SCI 2201 & 7201 Algorithm and Data Structure Analysis Semester 1, 2021 Exercise 3 We define the following program: Does program Q, given input y, print either ”Hello world” or ”Goodbye world” as its first output? Use reduction to prove that the above program is undecidable. Exercise 4 On https://turingmachine.io/, implement the Turing machine that tests whether the input is a UoA ID. That is, whether the input starts with a, and is then followed by 7 digits. 2
欢迎咨询51作业君