算法课业代做 CS 170代写 算法作业代写 高效算法作业代写

CS 170 Efficient Algorithms and Intractable Problems

Project

算法课业代做 Problem Statement Penguins are the last remaining species on Earth and they must figure out how to defend themselves against intergalactic attacks.

Problem Statement

Penguins are the last remaining species on Earth and they must figure out how to defend themselves against intergalactic attacks. Penguin Labs has recently released defense towers that can successfully shield cities within a 3 mile radius from all attacks. Each tower takes 170 kilowatts to power. If towers are placed too close together, the resonance of intergalactic radiation will cause the tower to consume more energy than necessary.

As one of the 170 chosen penguin agents, you are tasked with placing these towers throughout the penguin empire such that all cities are safe and you minimize the energy consumption (global warming is not good for penguins).

More formally: 算法课业代做

Input:

N: The number of cities for the problem instance.

D: The grid dimension (i.e. length of the sides of the square grid) for the problem instance.

R_s : The service radius for a tower.

R_p: The penalty radius for a tower.

N lines, each containing a coordinate (x_i , y_i) for the i’th city (0 ≤ x, y < D, 0 ≤ i < N).

Output:

M, the number of towers placed (M ≥ 0). M is unbounded; your solution can place as many towers as it wants to. M lines, each containing a coordinate (x_j , y_j) for the j’th tower (0 ≤ x, y < D, 0 ≤ j < M). Towers may be placed on cities.

Goal:

Output a set of towers that cover all cities, while minimizing the penalty P.

A city on the edge of a tower’s service radius is considered within the service radius; e.g. if R_s = 5, a city at (0,0) is covered by a tower at (0,5) or a tower at (3,4).

That is, w_j is the number of towers (exclusive of the j’th tower) within the penalty radius of tower j. Per the definition, a tower on the edge of the penalty radius is considered within the penalty radius; e.g. if R_p = 5, a tower at (0,0) is within the penalty radius of both a tower at (0,5) and a tower at (3,4).

1 Your Tasks 算法课业代做

1.1 Phase 1: Input Phase (Due 4/19, 11:59pm)

Overview

You will submit three inputs of different sizes. That is, the inputs you are submitting are instances of the problem that are to be solved by your peers in Phase 2.

We will collect everyone’s input files and release them after Phase 1 is due. Inputs are graded on completion and you will receive full points for your inputs as long as they follow the input format and submission guidelines. In Phase 2, you will be graded based on how well your solver performs compared your classmates’ solvers on these inputs, so it is in your favor to construct difficult/tricky inputs.

Submission Details

The three input files you submit should be named small.in, medium.in, and large.in. If your files do not satisfy these requirements, or if your input is invalid, you will not receive any credit for this portion of the project.

Only one member of your team should submit, and they should add the other members on Gradescope.

In order to get out a complete list of inputs to students in a timely fashion, there will be NO late submissions. As with the homework, our official policy is that if you can submit your inputs to Gradescope, then your submission is considered to be submitted on time. Anything that is submitted past the deadline will not be accepted.

1.2 Phase 2: Solver Phase (Due 5/2, 11:59pm) 算法课业代做

We strongly suggest you start working on Phase 2 early. In fact we recommend that students to begin working on working on solvers before the Phase 1 deadline.

Overview

You will be provided the pool of inputs generated by the class categorized by their size. Design and implement an algorithm and run it on the entire pool of input files. You will submit your output for every input provided in the format described below to the solutions assignment on gradescope. The autograder will check whether your solution is feasible and what the objective value is, and you’ll be given a score based on how well you did compared to the solution submitted with each input, on average. Your grade this phase will be determined in part by how your solver performs compared to those of other students. In addition to your outputs, you will write a reflection on the approaches you took and how they performed (more information is in the Grading section)

We have released starter code (see Piazza) to parse the provided input files and check outputs (you do not have to use the starter code). Teams are free to choose any programming language they wish, as long as the input and output files follow the specified format, since the Phase 2 autograder just requires the output files. Given the variety of possible programming languages and packages, we cannot guarantee that course staff will be able to provide support in office hours.

Note 1: 算法课业代做

Please choose a unique team name for the leaderboard (to keep the leaderboard anonymous). Please keep team names civil and PG-13 and no more than 30 characters long.

Note 2:

Any further details regarding the Phase 2 submission, autograder and leaderboard shall be released via Piazza when Phase 2 begins.

Services, Libraries, Tools

If you use non-standard libraries or computing resources beyond your personal computer, you may only use free services and tools. Services and tools which are normally paid are okay if used under free, easily available academic

licenses. This includes things like free AWS credits for students. If you use AWS or any other cloud computing service, you must cite how you used it, and how much, in your project report. If you use any non-standard libraries,

you need to explicitly cite which you used, and describe in your reflection document why you chose to use them. If you choose to use the instructional machines¹ , you may only use one at a time per team. We will be strict about

enforcing this; there will be a Google form for students to self-report anyone that they see using multiple instructional machines. Anybody caught using multiple instructional machines will receive a zero for this part of the project. The reason we have this rule is that in the past CS170 has overloaded instructional machines and we do not want to make these resources unavailable to other students.

¹ Note on accessing instructional machines: to use the instructional machines, first access EECS Acropolis and get your account credentials (e.g. cs170-abc). Once you have your account, SSH into one of the instructional machines listed on Hivemind (e.g. ssh cs170-abc@asbhy.cs.berkeley.edu). You should now have terminal access to your instructional account.

Input Format 算法课业代做

Each input should be formatted as follows:

• The first line should specify N, the number of cities.

• The second line should specify D, the dimensions of the grid. Coordinates of cities and towers cannot lie outside this grid.

• The third line should specify R_s , the service radius for each tower. (For all input sizes, this R_s = 3.)

• The fourth line should specify R_p, which is the distance where all towers within R_p of each other draw more power than necessary.

• Following those, there should be N lines. Each line should be formatted as a space-separated list of two integers “x y” representing the coordinates of each city.

Note: For each input size, D, N, R_s , and R_p must be restricted as follows:

– Small:

D = 30, 15 ≤ N ≤ 25, R_s = 3, R_p = 8

– Medium:

D = 50, 45 ≤ N ≤ 55, R_s = 3, R_p = 10

– Large:

D = 100, 195 ≤ N ≤ 205, R_s = 3, R_p = 14

Lines whose first character is a # will be ignored, so you can use them as comments.

Sample input:

# Small instance.
22
30
3
8
1 2
23 5
34 20
...

Output Format 算法课业代做

The output file corresponding to an input file must have the same name, except with the extension .in replaced by .out. For example, the output file for small.in must be named small.out.

Each output should be formatted as follows:

• The first line should specify M, the number of towers.

• Following that, there should be M lines. Each line should be formatted as a space-separated list of two integers “x y” representing the coordinates of each tower.

Lines whose first character is a # will be ignored, so you can use them as comments.

Sample Output:

# Penalty: 12345 
5 
23 12 
10 11 
0 3 
21 5 
10 20 

Reflection 算法课业代做

You will also submit a project reflection in addition to your code Phase 2. Your reflection should address the following questions:

• Describe the algorithm you used to generate your outputs. Why do you think it is a good approach?

• What other approaches did you try? How did they perform?

• What computational resources did you use? (e.g. AWS, instructional machines, etc.)

Your reflection should be no more than 1000 words long, although it may be shorter as long as you respond to the questions above. You will also submit the code for your solver, along with a README containing precise instructions

on how to run it. If we cannot parse your instructions then you run the risk of receiving a penalty to your overall grade.

We should be able to replicate all your results using the code you submit as well as your project report. More details on how to submit your code and project report will be released closer to the Phase 2 deadline.

Grading 算法课业代做

Overall, this project is worth 5% of your final grade. You will earn these points as follows:

• 1% will come from your inputs.² 

• 1% will come from your reflection.

• 3% will come from the the quality of your outputs.

We will release specific details about how outputs are scored closer to the release of Phase 2.

We encourage students to create the best solver they possibly can, and as staff we love to see a healthy competitive spirit in project groups. However, we’d like to emphasize that the point of this project is not to be purely an evaluation of your abilities against those of your peers. We really want to encourage students to view this as an opportunity to apply what they’ve learned over the semester to an open-ended project in an exploratory way. Do your best, try approaches that sound interesting to you, and have fun!

We will not accept late submissions. Submissions made after the deadline will not be considered.

² Inputs will be graded for validity and completion.

Academic Honesty 算法课业代做

Here are some rules and guidelines to keep in mind while doing the project:

1. No sharing of any files (input files or output files), in any form.

2. No sharing of code, in any form.

3. Informing others about available libraries is encouraged in the spirit of the project. You are encouraged to do this openly, on Piazza.

4. Informing others about available research papers that are potentially relevant is encouraged in the spirit of the project. You are encouraged to do this openly, on Piazza.

5. Informing others about possible reductions is fine, but treat it like a homework question – you are not to give any substantial guidance on how to actually think about formulating the reduction to anyone not in your team.

6. 算法课业代做

As a general rule of thumb: don’t discuss things in such detail that after the discussion, the other teams write code that produces effectively the same outputs as you. This should be a general guideline about how deep your

discussions should be.

7. If in doubt, ask us. Ignorance is not an excuse for over-collaborating.

If you observe a team cheating, or have any reason to suspect someone is not playing by the rules, please report it here.

As a final note from the staff, we generally trust that students will make the right decisions when it comes to academic honesty, and can distinguish collaboration from cheating. However, we’d like to point out that what has made this project so interesting in the past is the diversity of student approaches to a single problem. We could have elected to give you yet another problem set, but we believe that the open-ended nature of this project is a valuable experience to have. Do not deprive yourselves (or us) of this by over-collaborating or simply taking the same approaches you find your peers using. Again, try your best and have fun!

更多代写：Cs MBA网课代修代上  gre代考一亩三分地  英国exam代考价格  Essay写作综述代写  Paraphrase代写  能源经济代考

合作平台：essay代写 论文代写 写手招聘 英国留学生代写