need IT guy with maths knowledge and algo knowledge

6. (15 points) Suppose you are employed by a marine shipping company that routinely ships goods between San Francisco and Hong Kong. This is a very large company that needs to send multiple shipping vessels each week between these two locations. Each vessel has a fixed limit W on the maximum amount of weight that it is legally permitted to carry. Shipping containers arrive at the San Francisco dock one by one, and each of the i = 1, . . . , n containers is weighed (denoted as wi). Unfortunately, only one vessel can be docked and loaded at any point in time. In order to avoid customer complaints, the company policy is that containers are shipped in the order that they arrive at the dock. Currently, the company is using a simple strategy for loading the vessel: load containers in the order they arrive at the dock, and if a container doesn’t fit on the vessel, the vessel leaves the dock and the next vessel is loaded. Your company is curious whether they are using too many vessels and have thus hired you to provide an analysis on whether there is any room for improvement. Their thinking is that it may be possible to decrease the number of vessels needed by sometimes sending a vessel off to Hong Kong if it was less than full, which will allow the next vessels to be better packed. Prove that, for any set of containers with any weights, the current company strategy does minimize the number of needed vessels. Do not prove the complexity of the algorithm. HINTS: (1) use the “greedy stays ahead” approach shown in lecture, (2) proof by induction. 7. Consider the algorithm below, which operates on a given array A of n numbers. The algorithm assumes that arrays are indexed from item 0 (hence, n items are indexed from 0 to n − 1). 1: for i = 0 to n − 1 do 2: for j = 0 to n − 1 do 3: if A[j] > A[j + 1] then 4: x = A[j] 5: A[j] = A[j + 1] 6: A[j + 1] = x 7: end if 8: end for 9: end for (a) (3 points) What is the purpose of the algorithm? Show your work/reasoning. (b) (3 points) Using a loop invariant, prove that it correctly functions. (c) (3 points) Find a tight Θ-bound for its running time complexity. Clearly explain. 8. For each of the two situations below, pick a data structure (from those discussed in lecture) that is best suited for that use-case. If more than one data structure is best, discuss the trade-offs. For example, if you want to store the names of the calendar months and access them by month number then an array is best because the number of months is fixed and access by index is O(1). (a) (2 points) You want to store your company phone directory such that you can lookup a phone number by person’s name. You want to be able to add/remove people as well. (b) (2 points) You want to keep track of decisions made while trying to escape a maze such that if you make a wrong decision (get stuck at a dead end), you are able to easily backtrack and continue out of the maze.