本次代写是一个C++算法相关的assignment
IMPORTANT NOTES (PLEASE READ BEFORE WORKING ON THE SOLUTION):
- Please read the entire of this question sheet before starting to work on the solution.
- Your assignment should consist of a single .pdf, named A3-[studentID].pdf and a single .cpp/.java fifile, named
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.
- We provide 13 hours grace period. This means, there will be no penalty if you submit before the grace period ends. However, we will NOT accept assignment submission beyond this time (i.e., late penalty after the grace period ends is 100%).
– You can update your assignment until the grace period ends.
- Assignment marking:
– 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%.
- Discussion with your colleagues are allowed and encouraged. However, you need to work on the assignment on your own AND write the names you discussed this assignment with.
[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 = hs1, s2, . . . , smi where s1 = city-1 and sm = city-n (denoted as P(1, n) TPs(1, n)), can be computed as P(1, n) TPs(1, n) = P |s| i=1 P(si, si+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.
