首页 >
> 详细

COMP3023 Programming Assignment

Shooting Competition

Philoctetes is a sharp shooter. One day he is invited by a shooting competition.

In the competition, each shooter is given an array of n targets. Every target

has a value, a positive integer. If one target t is shot, the shooter’s scores will

be increased by

v1 × v2 × v3

where v1 is the value on the target t, v2 is the value on t’s left neighbor, and v3

is the value on t’s right neighbor.

You need to design a greed algorithm and a dynamic programming algorithm

to find an shooting order to maximize the score earned by Philoctetes under the

following assumptions.

1. Philoctetes never misses any target.

2. Shooters know the value on every target before shooting.

3. Each target has only two neighbors, left and right.

4. If one target is shot, its left and right neighbors will be neighbors afterwards.

5. Pretend that the first target has an artificial left neighbor - target 0.

Philoctetes cannot shoot target 0, but the target has value 1 and will be

counted in the score calculation.

6. Similarly, the right nieghbor of the last target is also an artificial target

n + 1 of value 1, which cannot be shot.

Requirements

1. Algorithms

(a) The greedy algorithm runs in O(n log n) time and uses O(1) space.

The greedy algorithm is not required to always find the maximum

score.

(b) The dynamic programming runs in O(n

2

) time and uses O(n

2

) space.

It always gives the maximum score.

1

2. Program

(a) You need to implement your algorithms in C.

(b) Your program reads a test case from “input.txt”.

(c) “input.txt” only contains the values for each target, one value on

each line.

(d) Your program outputs the resulting score on the screen and the corresponding

shooting sequence to “output.txt”, one index of a target

on each line.

3. Report

(a) Your report should contain all the notations that you have used to

model the problem,

(b) the recurrent relation for the dynamic programming,

(c) step-by-step pseudo codes for the two algorithms with clearly described

inputs and outputs,

(d) an instance such that your greedy algorithm cannot find the maximum

solution,

(e) space and time complexity anlysis of your algorithms.

(f) Your report should be 2 to 3 pages long, depends how you write.

4. Submission includs your code and your report. Name the package as

“COMP3023 20F PA #########.zip”, where #########

is your student ID.

Example

Suppose Philoctetes is given 4 targes of values 2, 1, 4, 3 (see “input example.txt”),

the maximum score is 41 because

Iteration Target index Score Values of the remaining targets

1 Target 2 (valued 1) 0 + 2 × 1 × 4 2, 4, 3

2 Target 3 (valued 4) 8 + 2 × 4 × 3 2, 3

3 Target 1 (valued 2) 32 + 1 × 2 × 3 3

4 Target 4 (valued 3) 38 + 1 × 3 × 1 Empty

The shooting sequence 2, 3, 1, 4 is in “output example.txt”.

联系我们

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

- Csse1001 Assignment 3 2021-01-10
- Comp3506/7505 Homework 4 – Graph Algo 2021-01-10
- Unix & C Programming (Comp1000) Assign... 2021-01-10
- Ece 209 Program 3: Market 2021-01-10
- Informatics 1 — Functional Programming 2021-01-10
- Cisc/Cmpe 452/Cogs400 Assignment 2 2021-01-10
- Fit2100 Operating Systems Assignment #... 2021-01-10
- Csci 1100 — Homework 5 2021-01-10
- Comp9444 Neural Networks And Deep Lea... 2021-01-10
- Assignment Case: German Credit 2021-01-10
- 48024 Applications Programming Assign... 2021-01-10
- Cs 405/805-001: Computer Graphics Ass... 2021-01-10
- Cse 434, Sln 70608 — Computer Networks 2021-01-10
- Corpfin 2503 - Business Data Analytics 2021-01-10
- Cis 455 / 555: Internet And Web System... 2021-01-10
- Cs110留学生编程代写、代做c++程序实验、Program程序语言调试帮做 2021-01-10
- Csc8021程序代做、代写networks编程语言、代做c/C++，Jav 2021-01-10
- 代写program编程语言、代做python，C++，Java程序设计帮做j 2021-01-10
- R编程课程代写、代做program程序语言、R程序实验代做代写databas 2021-01-09
- Data编程设计代做、代写java程序语言、Java程序实验调试代写r语言程 2021-01-09