PART 1 : Analyze the following algorithms. Write worst-case, average-case, base-case analysis if significant. Express your results using most proper asymptotic notation.
Explain your solutions. For the 1st to the 4th algorithms use table method and show table.
| somefunction(rows, cols){ for(i = 1; i <= rows; i++){ for( j = 1; j <= cols; j++) print(*) print(newline)}} |
| somefunction(a, b){ if (b == 0) return 1 answer = a increment = afor(i = 1; i < b; i++){ for(j = 1; j < a; j++){ answer += increment} increment = answer} return answer} |
| somefunction(arr[], arr_len){val = 0for (i = 0; i < arr_len / 2; i++) val = val + arr[i]for (i = n / 2; i < arr_len; i++) val = val arr[i]if (val >= 0) return 1 elsereturn 1} |
somefunction(n)
{
c = 0 for (i = 1 to n*n) for (j = 1 to n) for (k = 1 to 2*j) c = c+1
return c
}
| otherfunction(xp, yp){ temp = xp xp = yp yp = temp} somefunction(arr[], arr_len){ for (i = 0; i < arr_len 1; i++){ min_idx = ifor (j = i+1; j < arr_len; j++) if (arr[j] < arr[min_idx]) min_idx = jotherfunction(arr[min_idx], arr[i])}} |
| otherfunction(a, b){if b == 0: return 1 answer = aincrement = a for i = 1 to b:{ for j = 1 to a:answer += increment increment = answer}return answer} somefunction(arr, arr_len){for i = 0 to arr_len): for j = i to arr_len): if otherfunction(arr[i], 2) == arr[j]:print(arr[i], arr[j]) elif otherfunction(arr[j], 2) == arr[i]:print(arr[j], arr[i])} |
| otherfunction(X, i){ s = 0 for(j = 0; j <= i; j=j*2) s = s + X[j] return s} somefunction(arr[], arr_len){for(i = 0; i <= arr_len-1; i++)A[i] = otherfunction(arr, i) / (i + 1) return A} |
| somefunction(n){res = 0j = 1 if(n < 10)return n + 10 for(i = 9; i >= 1; i) while (n % i == 0) n = n / i res = res + j * i j *= 10 if(n > 10) return -1 return res} |
PART 2 : Design an algorithm for each of the problems. Write your algorithms in pseudo code. Obtain the complexities of the algorithms. Write worst-case, average-case, base-case analysis if significant. Express your results using most proper asymptotic notation. Explain your solutions.
- Assume you have an array of points in 2d space. Find the closest point in the array to a given point.
- The ith element of an array A is a local minimum if, A[i] <= A[i+1] and A[i] <= A[I-1].
- Find a local minimum in a given array A.
- Find all local minimums in a given array A.
- Find if a given array of integers contains two numbers whose sum is a given number b.
- A sequence of positive integers in increasing order, a1, a2,,an is called a Sum Chain of Length n if for all k (1 < k n), there exist i, j (1 i j k) such that ak=ai+aj
Example: {1, 2, 3, 5, 10, 13, 15} : (2=1+1, 3=2+1, 5=3+2, 10=5+5, 13=10+3, 15=10+5)
Find if a given sequence of n numbers is a Sum Chain of Length n. Use the algorithm you design for the third question in this part.
Reviews
There are no reviews yet.