本次代写是一个C++算法相关的assignment

IMPORTANT NOTES (PLEASE READ BEFORE WORKING ON THE SOLUTION):

A3-[studentID].cpp or A3-[studentID].java. You should zip these two fifiles together into a single fifile, named the .zip fifile A3-[studentID].zip and submit via Wattle before the due date.

**– **You can update your assignment until the grace period ends.

**– **The total mark you can get in this assignment is 100 points.

**– **This assignment will contribute 20% to your overall mark.

**– **In each question, you need to provide a convincing argument (including mathematical derivation) that supports your answer. The argument is worth 80% of the marks, while the solution alone is 20%.

**[30 pts] Part A **

- [15 pt] Mr Sort were provided with the source code that performs simple uniform hashing with chaining. He would like to modify the chaining component, such that each list is kept in a sorted order
**array**using merge sort. What will the effect of this modifification be to:

(a) [5pt] The time complexity of searching for a key

(b) [5pt] The time complexity of insertion

(c) [5pt] The time complexity of deletion

- [8 pt] Mr B has created a complete binary tree, denoted as
*T*and coloured all nodes to be black. He claimed that*T*is a Red-Black tree. Is he correct? Please justify your answer.

- [7 pt] In an AVL tree, where is the node with the minimum key located? And where is the node with the maxi mum key located?

**[40 pts] Part B **

- [20 pt] Due to travel restrictions, the global travel cost has sky-rocketed. However, Ms Niche found that if a passenger is willing to change flflight multiple times, they can generally get to their destination with a much cheaper flflight ticket. Due to her extensive network with airline executives, Ms Niche can purchase any airline tickets free of commission. Therefore, she can charge a flflat fee –that is, the fee remains the same regardless of the number of hops to go from one city to a destination city. This flflat fee means the total price for travelling from city-1 to city-
*n*via sequence*s*= h*s*1,*s*2, . . . ,*s**m*i where*s*1 = city-1 and*s**m*= city-*n*(denoted as*P*(1,*n*)**TP***s*(1,*n*)), can be computed as*P*(1,*n*)**TP***s*(1,*n*) = P |*s*|*i*=1*P*(*s**i*,*s**i*+1)+*C*, where*C*is the flflat fee. Ms Niche knows that the prices of all direct flflights (i.e.,*P*(*i*,*j*) for*i*,*j*,*i*,*j*∈ [1,*n n*1]) changes quarterly, and so she would like to develop a program such that she can answer customers’ queries on fifinding the cheapest sequence of cities to travel from city-*i*to city-*n*. Please help Ms Niche by answering the following questions:(a) [5 pt] Can Ms Niche use Dynamic Programming to solve the above problem? If she can, please show that the two requirements for a problem to be solvable by Dynamic Programming is satisfified. Otherwise, please explain which requirements are being violated.(b) [10 pt] Please provide an algorithm that Ms Niche can use to solve her problem.

(c) [5 pt] Please provide the time complexity of the algorithm you proposed in 4b.