” 辅导COMP3121程序、 写作c++，Java编程语言Term 2, 2021 COMP3121/9101: Assignment 2You have five problems, marked out of a total of 100 marks; eachproblem is worth 20 marks. You should submit your solutions byMonday, July 12. Please do not wait till the last moment to submityour work – we WILL NOT accept emailed solutions regardless ofwhether you had network problems or not. Also follow closely theinstructions for how to submit your solutions. Your solutions toeach of the problems must be submitted in a separate file. Thereare 1000+ students in this class and thus NO EXCEPTIONS canbe granted except for special considerations or for ELS studentswho can get one Week extension. Your solutions must be typed,machine readable .pdf files. All submissions will be checked forplagiarism!1. You are given a sequence of n songs where the ith song is `i minuteslong. You want to place all of the songs on an ordered series of CDs(e.g. CD1, CD2, CD3, . . . CDk) where each CD can hold m minutes.Furthermore,(a) The songs must be recorded in the given order, song 1, song 2,. . ., song n.(b) All songs must be included.(c) No song may be split across CDs.Your goal is to determine how to place them on the CDs as to minimizethe number of CDs needed. Give the most efficient algorithm you canto find an optimal solution for this problem, prove the algorithm iscorrect and analyze its time complexity.2. At a trade school, there are N workers looking for jobs, each with askill level xi. There are P entry-level job openings, and the ith openingonly accepts workers with a skill level less than or equal to pi. Thereare also Q senior job openings, the i of which requires a skill level of atleast qi. Each worker can take at most one job, and each job openingonly accepts a single worker.Your task is to determine the largest number of workers you can assignto jobs in time O(N logN + P logP + Q logQ).3. A city is attacked by N Monsters and is defended by a single hero withinitial strength of S units. To kill a monster i the hero must dissipate1ai units of strength; if monster i is killed successfully the hero gains giunits of strength. Thus, if the hero had strength c ai before tacklingmonster i he can kill the monster and he will end up with c ? ai + giunits of strength. Note that for some monsters i you might have gi aibut for some other j you might have aj gj. You are given S and foreach i you are given ai and gi. Design an algorithm which determinesin which order the hero can fight the monsters if he is to kill them all(if there is such an ordering). In case there is no such ordering thealgorithm should output no such ordering. Assume all values arepositive integers.4. You are given n Stacks of blocks. The ith stack contains hi 0 identicalblocks. You are also able to move for any i n ? 1 any number ofblocks from stack i to stack i + 1. Design an algorithm to find outin O(n) time whether it is possible to make the sizes of stacks strictlyincreasing. (For example, 1,2,3,4 are strictly increasing but 1,2,2,3 arenot). The input for your algorithm is an array A of length n such thatA[i] = hi. Note that you are not asked to actually move the blocks,only to determine if such movements exists or not.5. You are given n jobs where each job takes one unit of time to finish.Job i will provide a profit of gi dollars (gi 0) if finished at or beforetime ti, where ti is an Arbitrary integer larger or equal to 1. Onlyone job can be done at any instant of time and jobs have to be donecontinuously from start to finish. (Note: If a job i is not finished byti then there is no benefit in scheduling it at all. All jobs can start asearly as time 0.) Give the Most efficient algorithm you can to find aschedule that maximizes the total profit.请加QQ：99515681 或邮箱：99515681@qq.com WX：codehelp
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
