Suppose you are given an array A of n sorted numbers that has been circularly shifted k positions to the right. For example, {35, 42, 5, 15, 27, 29} is a sorted array that has been circularly shifted k = 2 positions, while {27, 29, 35, 42, 5, 15} has been shifted k = 4 positions.

(a) Suppose you know what k is. Give an algorithm to find the largest number in A.

(b) Suppose you do not know what k is. Give an algorithm to find the largest number in A.

(a) Suppose you know what k is. Give an algorithm to find the largest number in A.

Since the array was sorted to start with then we know that if it was not shifted then the last element in the list is the largest element. However, since it is circular shifted the last element has been moved. If the array was shifted by 1 element then the largest element would have moved to the front of the list. If the array was shifted by 2 elements then the largest would be at the second location. So we know that if the array is ...

Solution Summary

This solutions explains two algorithms for manipulating values in a list and explains the algorithmic complexity of each algorithm.

You should post the "best possible" responses to the question. Remember that the main purpose of algorithm questions is to come up with the best possible algorithms through discussion. It is ok to write your responses using pseudocode, and there is no need to code & test using C++.
1. Design an algorithm for finding two clos

Trace the algorithm below and track the number of times that the addition operation (+) is executed over the course of the program's run time. Answer the question by giving a formula in terms of n:
for i := 1 to n do
for j := 1 to i do x := x + f(x) od;
x := x + g(x)
od

Describe the error in the following fallacious "proof" that P NP. Consider an algorithm for SAT: "On input , try all possible assignments to the variables. Accept if any satisfy ." This algorithm clearly requires exponential time. Thus SAT has exponential time complexity. Therefore SAT is not in P.

Please help with these 2 problems in algorithm efficiency. View attached file.
1. Rank the terms of the following function according to their order of growth. Give explanation.
2. Consider the following algorithm where n is a positive integer.
What is the efficiency class of this algorithm? Show your reasoning.

Suppose you are given a set P of integers and another integer x. We wish to use a O(n*lg n) algorithm to decide whether there are 2 integers in P whose sum equals to x. Show your algorithm. You can use pseudo code or verbose description to explain your algorithm.
If you need to use any well known standard algorithm in your so

How much time does an algorithm take to solve a problem of size n if this algorithm uses 2n^2 + 2^n bit operations, each requiring 10^-9 second, with these values of n?
i) 10
ii) 20
iii) 50
iv) 100
I need help with a question, the attachment contains the question as well as what I think is the answer. Could someone ple

Use big-O notation to classify the traditional grade school algorithms for addition and multiplication. That is, if asked to add two numbers each having N digits, how many individual additions must be performed? If asked to multiply two N-digit numbers, how many individual multiplications are required?

Describe the worst case scenario for quick sort algorithm. Any ideas to improve the worst case? Comment on the improvement in running time vs. increase in code complexity.