Prove that your algorithm is correct or not

Assignment Help Computer Engineering

Reference no: EM132101042

Question :

Please do not write an answer form the internet,You want very clear algorithm with mathematical prove of correction if that can be possible.

You are going on a trip from Halifax to San Francisco. You know that, along the route, there are gas stations at kilometers k 1, k 2, . . . , k n.

You also know that your car can go m kilometers on a tank full of gas. Develop an algorithm that determines at which gas stations to stop so that

a. The distance between two consecutive stops is at most m (that is, you can always get from one stop to the next on a tank full of gas) and

b. You make as few stops as possible while respecting the previous condition. The running time of your algorithm should be linear. You do not have to prove that it is.

Prove that your algorithm is correct, that is, that it indeed produces a sequence of stops that satisfies the above conditions.

Reference no: EM132101042

Questions Cloud

Write a program that reads the values of c and prints value : Present Value (PV) is a formula used in finance that calculates the present day value of an amount received at a future date.

Improve the efficiency of its radiology department : Heavenly Mercy Hospital wants to improve the efficiency of its radiology department and its responsiveness to doctors’ needs.

What is organizational decline : What is organizational decline? List its five stages. Provide an “original” example that depicts each of the 5 stages.

Kitty statement that she had no personal liability : Which of the following is true regarding Kitty's statement that she had no personal liability?

Prove that your algorithm is correct or not : You are going on a trip from Halifax to San Francisco. You know that, along the route, there are gas stations at kilometers k 1, k 2, . . . , k n.

Essay on the topic - Communication-Problematising Identity : Question - Write an essay on the topic "Communication - Problematising Identity". Ensure APA guidelines are followed

How many joules of energy does the battery lose in a minute : A 12-V battery causes a current of 0.80A through a resistor. How many joules of energy does the battery lose in a minute?

Business consists of preparation and delivery of hot meal : Family Meals, Inc. is a thriving business in a large metropolitan area of over 500,000 people. The business consists of the preparation and delivery of hot meal

Create a primary function that returns the number of trials : Create a primary function that returns the number of trials that give each of the distinct simulated sums of two dice rolls.

User Account

All Pages