Elon Musk is building a prototype Hyperloop line that travels through cities X =
ID: 3703286 • Letter: E
Question
Elon Musk is building a prototype Hyperloop line that travels through cities X = x1, x2,..., xn in that order. The Hyperloop may travel through the same city multiple times. He wishes to construct a public transit service using the Hyperloop, by constructing stops at a subset of the cities on the route. In order to be useful, the transit service must stop in a list of cities in order, and then go back through those same cities in the reverse order. To maximize the usage of the transit service, it should have as many stops as possible. For instance, consider the route X = { London (L), Kitchener (K), Hamilton (H), Burlington (B), Toronto (T), Ottawa (O), Montreal (M), Pickering (P), Toronto (T), Burlington (B), Kitchener (K) }. Two valid transit paths would be KTTK and KBTMTBK, the latter of which is optimal. Note that Montreal is only stopped at once, but the route is valid as long as it reads the same backwards and forwards. Given a Hyperloop route X, devise a dynamic programming algorithm to find the length of the optimal (longest) transit path of X. Write the pseudocode, recurrence relation, and analyze the run time complexity of your algorithm.
Explanation / Answer
//recurrence relation, and analyze the run time complexity of your algorithm
public static int c=0
public static int transitPaths(String X,int start,int end) //it takes a string and its starting index and end index
{
int a;
for(int i=start;i<end;i++)
{
a=search(X,X[i]); //search x[i] in x it return the largest index which contain same character as x[i] if not found then return -1
if(a!<0 && start<end && s[start]==s[end]) //if element found and start < end (not equal to also) and if s[start]==s[end] for palindrom
{
c++; // increment the counter for return the largest length of substring
transitPaths(X,i+1,a-1); // recursively call the function to execute in substrings
}
}
return c; //return the largest length of the substring
}
public static search(String s,char q) // linear search function of order n and for the condition of largest we return the largest index that matches with the char
{
int c=0;
for(int i=s.length();i>0;i--)
{
if(s[i]==q)
return i;
}
return -1;
}
public static void main()
{
scan("%s",city_name); //scanf the city_name
transitPaths(city_name,0,city_name.length()-1); // proceed with start =0;and end =length()-1
}
Recurrence Relation:-
T(n) = 1 n = 0
T(n-2) + c n > 1;
where c be a constant.
Applying Telescopic Sum, We have
T(n) = T(n-2) + c
T(n-2) = T(n-4) + c
.
.
.
.
.
T(2) = T(0) + c
___________________
T(n) = nc + 1 = O(n)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.