COMP SCI 2201 & 7201 Algorithm and Data Structure Analysis Semester 1, 2021 Tutorial 5: Hashtables and Topological Sorting General Instructions You do not need to submit your solution. We will discuss the questions during the workshop sessions in week 10. Exercise 1 Hash Tables 1. Insert the key sequence 7, 18, 2, 3, 14, 25, 1, 11, 12, 1332 with hashing by chaining in a hash table with size 11. Please show the final table by using the hash function h(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”. Both can be considered improved versions of linear probing. Please find out where they improve upon linear probing. Exercise 2 Single-source-shortest path problem in acyclic graphs We 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 the given 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 1
欢迎咨询51作业君