본문 바로가기
REC_CMPL3 What is the worst case time complexity of the following code:int memo[101][101]; int findMinPath(vector& V, int r, int c) { int R = V.size(); int C = V[0].size(); if (r >= R || c >= C) return 100000000; // Infinity if (r == R - 1 && c == C - 1) return 0; if (memo[r][c] != -1) return memo[r][c]; memo[r][c] = V[r][c] + min(findMinPath(V, r + 1, c), findMinPath(V, r, c + 1)); return memo[r][c]; } C.. 더보기
CHOOSE2 Which of the given options provides the increasing order of complexity of functions f1, f2, f3 and f4:f1(n) = 2^n f2(n) = n^(3/2) f3(n) = nLogn f4(n) = n^(Logn) f3, f2, f4, f1 f3, f2, f1, f4 f2, f3, f1, f4 f2, f3, f4, f1Good solution:n < nlog(n)n^x < n^y if x < yn^x < c^n where c is a constant (polynomials will eventually grow slower than exponentials)log(n) < nc^n < n! < n^n where c is a constant 더보기
REC_CMPL2 What is the worst case time complexity of the following code:int findMinPath(vector &V, int r, int c) { int R = V.size(); int C = V[0].size(); if (r >= R || c >= C) return 100000000; // Infinity if (r == R - 1 && c == C - 1) return 0; return V[r][c] + min(findMinPath(V, r + 1, c), findMinPath(V, r, c + 1)); } Assume R = V.size() and C = V[0].size(). O(2^(R + C)) O(R*C) O(R + C) O(R*R + C*C) O(R*.. 더보기
GCD_CMPL In the following C++ function, let n >= m. int gcd(int n, int m) { if (n%m ==0) return m; if (n 0) { n = n%m; swap(n, m); } return n; } What is the time complexity of the above function assuming n > m? Θ(logn) Ω(n) Θ(loglogn) Θ(sqrt(n))Good solution:https://www.youtube.com/watch?v=pqivnzmSbq4Euclidean algorithm 더보기
CHOOSE1 CHOOSE1BookmarkSuggest EditWhich of the following is not bounded by O(n^2)? (15^10) * n + 12099 n^1.98 n^3 / (sqrt(n)) (2^20) * nGood solution:The big O gives an upper bound. It doesn’t have to be tight - just means the function won’t exceed it for n > some constant. In this case O(n^2) serves as an upper bound for a, b and d. Functions a and d are linear - more to the order of O(n). Function b .. 더보기
LOOP_CMPL2 What is the time complexity of the following code : int i, j, k = 0; for (i = n/2; i 더보기
NESTED_CMPL3 What is time complexity of following code : int count = 0; for (int i = N; i > 0; i /= 2) { for (int j = 0; j 더보기
Sorting: Bubble Sort Consider the following version of Bubble Sort:for (int i = 0; i a[j+1]){ int tmp = a[j+1]; a[j+1] = a[j]; a[j] = tmp; count++; } } } System.out.println("Array is sorted in " + count + " swaps."); System.out.println("First Element: " + a[0]); System.out.println("Last Element: " + a[a.length-1]); } } 더보기
Heaps: Find the Running Median The median of a dataset of integers is the midpoint value of the dataset for which an equal number of integers are less than and greater than the value. To find the median, you must first sort your dataset of integers in non-decreasing order, then:If your dataset contains an odd number of elements, the median is the middle element of the sorted sample. In the sorted dataset , is the median.If yo.. 더보기
Level 4- 땅따먹기 게임 영희는 땅따먹기 게임에 푹 빠졌습니다. 땅따먹기 게임의 땅은 총 N행 4열로 나누어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 땅을 밟으면서 한 행씩 내려올 때, 영희는 각 행의 4칸 중 1칸만 밟으면서 내려올 수 있습니다. 땅따먹기 게임에는 같은 열을 연속해서 밟을 수가 없는 특수 규칙이 있습니다. 즉, 1행에서 (5)를 밟았다면, 2행의 (8)은 밟을 수가 없게 됩니다. 마지막 행까지 모두 내려왔을 때, 점수가 가장 높은 사람이 게임의 승자가 됩니다. 여러분이 hopscotch 함수를 제작하여 영희가 최대 몇 점을 얻을 수 있는지 알려주세요. 예를 들어 1 2 3 5 5 6 7 8 4 3 2 1 의 땅이 있다면, 영희는 각 줄에서 (5), (7), (4) 땅을 밟아 16점을 최고점으로 받을 수 있으.. 더보기

티스토리툴바