I am stuck on how to do this question. The code is in C and pseudo code PLEASE N
ID: 3881678 • Letter: I
Question
I am stuck on how to do this question. The code is in C and pseudo code
PLEASE NOTE: in questions 4-5, represent your answer in pseudocode form as discussed in class, be sure to clearly indicate your inputs, outputs, assertions, and comments. The highest marks will be awarded to the best running time Question 4: Resource Collection (6 marks) Background: Resource collection is a common optimization problem in the domain of Al. The input is a map with a description of the benefits (e.g., food/energy) or hazards (e.g., predators/obstacles) for each location, and the problem is to plan the best route, i.e., the one that maximizes the total energy collected 0389 In a resource-rich map, the best route might be to greedily visit everywhere; the other extreme in a completely hazardous environment is to just stay put. The Problem: The input will be an array A[n] of integers, representing a 1-dimensional map where positive numbers are beneficial, but negative numbers are harmful Devise an algorithm that finds the largest possible value of the expression Ak], the sum of a contiguous block of integers. (When jExplanation / Answer
1.) In this algorithm we find the non-negative element of the array and then find the sequence till the largest sum, if the sum goes down to zero or negative, the sum is reset to zero and we start finding the next new subsequence.
inputs= arr[i]
variables:
size(number of elements), l (lower index of subsequence)=0, u (upper index of subsequence)=0, x=0, sum=0(sum of current sequence), sum_max= INT_MIN(not using 0 as ithis provides ease in comparision, also protection from unwanted errors).
2) for(loop till i<size)
{
sum+= arr[i]
if(sum_max<sum)
{ sum_max=sum; l=x ;h=i;}
if(sum<0)
{ sum=0; s=i+1;}
}
The variable sum_max stores the maximum sum and l and u stores the starting and ending position of the array from where we get max sum.
The running time of the following algo will be O(n) as it runs n times only.(one for loop only.)
2.) Divide and conquer method:
In this method, we divide the array into two halves and then we make comparision between three parts, left of the middle of the array, right of the middle of the array and some sum from somewhere to the left to somewhere to the right of the middle element. But since the running time of this algorithm is O(nlogn) the previous method is more useful.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.