辅导COMP SCI编程、写作Algorithm

” 辅导COMP SCI编程、写作AlgorithmCOMP SCI 2201 7201 Algorithm and Data Structure Analysis Semester 1, 2021Minimum Spanning Trees, Euler Path, UndecidableProblems, and Turing MachinesExercise 1 Kruskals AlgorithmCompute a minimum Spanning for the following graph using Kruskals algorithm. Showthe status of your partial minimum spanning tree after each edge insertion and indicatefor each edge whether it is included in the minimum spanning tree.Tutorial 5: Hashtables and Topological SortingGeneral InstructionsYou do not need to submit your solution. We will discuss the questions during theworkshop sessions in week 10.Exercise 1 Hash Tables1. Insert the key sequence 7, 18, 2, 3, 14, 25, 1, 11, 12, 1332 with hashing by chainingin a hash table with size 11. Please show the final table by using the hash functionh(k) = k mod 11.2. Please show the final table if we use linear probing instead.3. Investigate by yourself what is quadratic probing and double hashing. Bothcan be considered improved versions of linear probing. Please find out where theyimprove upon linear probing.Exercise 2 Single-source-shortest path problem in acyclic graphsWe consider the single-source-shortest path problem of a given directed graph G = (V,E)with non-negative edge weights and a source node s. Furthermore, we assume that thegiven graph G is acyclic, i. e. it does not contain a cycle.? Give an algorithm (in pseudo-code) that solves the single-source-shortest path prob-lem for a given acyclic graph in time O(m + n).? Prove the correctness of your algorithm.? Explain why your algorithm runs in time O(m + n).End of QuestionsExercise 2 Euler tours of directed graphsA 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 cyclethat 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 equalsthe out degree of v.? Describe an O(m) (where m is the number of edges in G) algorithm to find an Eulertour of G if such a tour exists (Hint: Merge edge-disjoint cycles).1COMP SCI 2201 7201 Algorithm and Data Structure Analysis Semester 1, 2021Exercise 3 We define the following program: Does program Q, given input y, print eitherHello world or Goodbye world as its first output?Use reduction to prove that the above program is undecidable.Exercise 4 On httpss://turingmachine.io/, implement the Turing machine that testswhether the input is a UoA ID. That is, whether the input starts with a, and is thenfollowed by 7 digits.Tutorial 5: Hashtables and Topological SortingGeneral InstructionsYou do not need to submit your solution. We will discuss the questions during theworkshop sessions in week 10.Exercise 1 Hash Tables1. Insert the key Sequence 7, 18, 2, 3, 14, 25, 1, 11, 12, 1332 with hashing by chainingin a hash table with size 11. Please show the final table by using the hash functionh(k) = k mod 11.2. Please show the final table if we use linear probing instead.3. Investigate by yourself what is quadratic probing and double hashing. Bothcan be considered improved versions of linear probing. Please find out where theyimprove upon linear probing.Exercise 2 Single-source-shortest path problem in acyclic graphsWe consider the single-source-shortest path problem of a given directed graph G = (V,E)with non-negative edge weights and a source node s. Furthermore, we assume that thegiven graph G is acyclic, i. e. it does not contain a cycle.? Give an algorithm (in pseudo-code) that solves the single-source-shortest path prob-lem for a given acyclic graph in time O(m + n).? Prove the correctness of your algorithm.? Explain why your Algorithm runs in time O(m + n).End of Questions请加QQ：99515681 或邮箱：99515681@qq.com WX：codehelp

“