首页 >
> 详细

Term 2, 2021 COMP3121/9101: Assignment 2

You have five problems, marked out of a total of 100 marks; each

problem is worth 20 marks. You should submit your solutions by

Monday, July 12. Please do not wait till the last moment to submit

your work - we WILL NOT accept emailed solutions regardless of

whether you had network problems or not. Also follow closely the

instructions for how to submit your solutions. Your solutions to

each of the problems must be submitted in a separate file. There

are 1000+ students in this class and thus NO EXCEPTIONS can

be granted except for special considerations or for ELS students

who can get one week extension. Your solutions must be typed,

machine readable .pdf files. All submissions will be checked for

plagiarism!

1. You are given a sequence of n songs where the ith song is `i minutes

long. 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 minimize

the number of CDs needed. Give the most efficient algorithm you can

to find an optimal solution for this problem, prove the algorithm is

correct and analyze its time complexity.

2. At a trade school, there are N workers looking for jobs, each with a

skill level xi. There are P entry-level job openings, and the i

th opening

only accepts workers with a skill level less than or equal to pi. There

are also Q senior job openings, the i of which requires a skill level of at

least qi. Each worker can take at most one job, and each job opening

only accepts a single worker.

Your task is to determine the largest number of workers you can assign

to 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 with

initial strength of S units. To kill a monster i the hero must dissipate

1

ai units of strength; if monster i is killed successfully the hero gains gi

units of strength. Thus, if the hero had strength c ≥ ai before tackling

monster i he can kill the monster and he will end up with c ? ai + gi

units of strength. Note that for some monsters i you might have gi ≥ ai

but for some other j you might have aj > gj. You are given S and for

each i you are given ai and gi. Design an algorithm which determines

in 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 the

algorithm should output “no such ordering”. Assume all values are

positive integers.

4. You are given n stacks of blocks. The ith stack contains hi > 0 identical

blocks. You are also able to move for any i ≤ n ? 1 any number of

blocks from stack i to stack i + 1. Design an algorithm to find out

in O(n) time whether it is possible to make the sizes of stacks strictly

increasing. (For example, 1,2,3,4 are strictly increasing but 1,2,2,3 are

not). The input for your algorithm is an array A of length n such that

A[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 before

time ti, where ti is an arbitrary integer larger or equal to 1. Only

one job can be done at any instant of time and jobs have to be done

continuously from start to finish. (Note: If a job i is not finished by

ti then there is no benefit in scheduling it at all. All jobs can start as

early as time 0.) Give the most efficient algorithm you can to find a

schedule that maximizes the total profit.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-21:00
- 微信：codinghelp2

- 辅导comp30027帮做python编程 2021-08-02
- 辅导csse2002/7023-Assignment 1辅导留学... 2021-08-02
- 辅导rush2辅导c/C++ 2021-08-02
- 辅导r语言编程|辅导spss|辅导web开发|辅导... 2021-05-10
- Data留学生编程辅导、辅导analysis程序、Sql语言程序调试辅导r语 2021-05-10
- 辅导31748程序语言、辅导programming编程设计、Java，Pyt 2021-05-10
- 辅导cis 657编程、辅导c/C++程序、C++编程调试帮做haskell 2021-05-10
- Com1005程序辅导、辅导java编程语言、辅导java程序辅导留学生pr 2021-05-10
- 辅导sit283程序、辅导c/C++，Python编程设计、Cs，Java程 2021-05-09
- C++程序辅导、辅导c++程序、辅导program编程语言辅导r语言编程|辅 2021-05-09
- 辅导0ccs0cse编程、辅导r，Java，Python程序语言辅导web开 2021-05-09
- Comp124编程语言辅导、Java程序辅导、辅导program语言编程辅导 2021-05-09
- Comp122编程语言辅导、辅导java程序语言、Java程序调试帮做has 2021-05-09
- 辅导ele00041i 调试java Programming 2021-05-08
- 辅导econ 2014-Assignment 1 Managerial... 2021-05-08
- 辅导mast90044-Assignment 1 Thinking An... 2021-05-08
- 辅导cs310-Assignment 2 Hash Tables 2021-05-08
- 辅导5pm 调试java编程、Java编程辅导 2021-05-08
- 辅导cs544 Final Exam Preparation Guide... 2021-05-08
- 辅导infs7450 Social Media Analytics 2021-05-08