A word ladder is a sequence of English words, where two adjacent words differ by only one letter. For example: COLD CORD CARD WARD WARM -> You are given the two words "PHYSICS" and "GEOLOGY", and you must design an algorithm that computes a word ladder between the two words, with the shortest possible sequence of words. Input: The two words "PHYSICS" and "GEOLOGY", and an unsorted list of 7-letter English words. Assume that there are n such words in the list, and that all words consist of only the 26 English alphabet letters. Output: A word ladder sequence from "PHYSICS" to "GEOLOGY" that contains the smallest possible number of words. If such a word ladder is impossible, return NIL. Requirement: The average-case runtime of the algorithm must be in O(n). Part (a) [4 MARKS] How do you model this problem using a graph? Describe what each vertex represents and what each edge represents. Indicate whether it is a directed or undirected graph. Part (b) [2 MARKS] In order to be able to construct your graph from Part (a) in O(n) average-case runtime, you need to use a data structure to store the list of 7-letter English words. What data structure should you use? Question 8. (CONTINUED) Part (c) [4 MARKS] Give a clear description of the construction process of your graph from Part (a) and justify that it takes average-case runtime O(n). Part (d) [5 MARKS] Using the graph you constructed in Part (c), describe in clear English how to find a word ladder with the shortest sequence of words. Justify briefly that your algorithm is correct and has the desired runtime.