Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
FA 4 - Algorithms
| Question | Answer |
|---|---|
| Which of the following is true about merge sort? Merge Sort works better than quick sort if data is accessed from slow sequential memory. All of the above Merge sort outperforms heap sort Merge Sort is stable sort by nature | All of the above |
| Describe an advantage of a binary search algorithm Performs well over large ordered lists. Slow with large data sets. Data does not need to be in order. Can only work on an ordered list. If unordered must use a linear search. | Performs well over large ordered lists. |
| What is the average-case time complexity of Merge sort? Group of answer choices Exponential O (1) O (n log n) O (n2) | O (n log n) |
| What is the auxiliary space complexity of merge sort? Group of answer choices Exponential O(n log n) O(n) O(1) | O(n) |
| What do you call the sorting technique that divides the array into equal halves and then combines them in a sorted manner? Group of answer choices Insertion Sort Quick Sort Merge Sort Bubble Sort | Merge Sort |
| What is the formula use in the binary search if a new mid value needs to be set. low = mid + 2 mid = low + (high - low) / 2 low = mid + 1 mid = low + (high + low) / 2 low = mid = low + (high - low) / 2 low = mid + 1 mid = low + (high - low) / 2 | low = mid + 1 mid = low + (high - low) / 2 |
| What is the time complexity of quick sort for worse case? Group of answer choices O (n^2) O (n log n) Exponential O (1) | O (n^2) |
| What do you call the step that receives a lot of smaller sub-problems to be solved. Group of answer choices Answer Solve Crack Rejoin | Solve |
| What do you call the step in the divide and conquer that generally takes a recursive approach to divide the problem until no sub-problem is further divisible? Group of answer choices Breakdown Halt Break Collapse | Break |
| What is the worst-case time complexity of Merge sort? Group of answer choices O (1) Exponential O (n log n) O (n2) | O (n log n) |
| What is the optimal time required for solving the closest pair problem using divide and conquer approach? Group of answer choices Exponential O(n!) O(n log n) O(1) | O(n log n) |
| What is the running time of Strassen’s algorithm for matrix multiplication? Group of answer choices O(n^3.8074) O(n^2.8974) O(n^2.8074) O(n^3.8974) | O(n^2.8074) |
| What is the worse time complexity of Strassen algorithm Group of answer choices O(n^3.8974) O(n^2.8074) O(n^3.8074) O(n^2.8974) | O(n^2.8074) |
| A method that easily modified to find the points with the smallest distance Group of answer choices Strassen Algo Binary Search Closest Pair Merge sort | Closest Pair |
| What is the running time of naïve matrix multiplication algorithm? Group of answer choices O(n^3) O(n) O(n^4) O(n^2.8074) | O(n^3) |
| Strassen’s algorithm is a/an_____________ algorithm. Group of answer choices Non-recursive Recursive Accurate Approximation | Recursive |
| When computing for p3 what the exact formula is? Group of answer choices p3=(cd)e p3=(c-d)+e p3=(c/d)e p3=(c+d)e | p3=(c+d)e |
| Is the first geometric problems that were treated at the origins of the systematic study of the computational complexity of geometric algorithms. Group of answer choices Closest Pair Merge sort Binary Search Strassen Algo | Closest Pair |
| In divide and conquer, the time is taken for merging the subproblems is? Group of answer choices Exponential O(1) O(n log n) O(n!) | O(n log n) |
| There are a total of _______ sub-matrices in solving for the Strassen algorithm Group of answer choices 6 8 9 7 | 8 |
| Problem solving approach where the problem in hand, is divided into smaller sub-problems and then each problem is solved independently. Group of answer choices Divide and Conquer Greedy Algorithm Dynamic Programming Decrease and Conquer | Divide and Conquer |
| Which of the following sorting algorithms has the lowest worst-case complexity? Group of answer choices Merge Sort Insertion Sort Quick Sort Bubble Sort | Merge Sort |
| Merge Sort can be categorized into which of the following? Group of answer choices Dynamic Programming Greedy Algorithm Decrease and Conquer Divide and Conquer | Divide and Conquer |
| A binary search is to be performed on the list: 1 5 10 13 48 68 100 101 How many comparisons would it take to find number 101? Group of answer choices 4-5 3-4 0-1 C 1-2 | 3-4 |
| In this searching algorithm, it is mandatory for the target array to be sorted Group of answer choices Binary Bubble Merge Quick | Binary |
| What is the correct formula use in binary search Group of answer choices mid = low * (high - low) / 2 mid = low - (high - low) / 2 mid = low + (high - low) / 2 mid = low + (high + low) / 2 | mid = low + (high - low) / 2 |
| What year did Strassen published his algorithm that proves the n3 general matrix multiplication was not optimal? Group of answer choices 1968 1970 1967 1969 | 1969 |
| Strassen’s Matrix Algorithm was proposed by _____________ Group of answer choices Andrew Strassen Volker Strassen Virginia Williams Victor Jan | Volker Strassen |
| Strassen’s matrix multiplication algorithm follows ___________ technique. Group of answer choices Divide and Conquer Dynamic Backtracking Dynamic | Divide and Conquer |
| What is the best time complexity of Strassen algorithm Group of answer choices O(n^2) O(n^2.8074) O (1) Exponential | O (1) |
| Which of the following areas do closest pair problem arise? Group of answer choices string matching numerical problems graph colouring problems computational geometry | computational geometry |
| The Strassen algorithm is known as a? Group of answer choices Matrix Division Matrix subtraction Matrix multiplication Matrix Addition | Matrix multiplication |
| Binary search is similar to that methodology? Group of answer choices Dynamic Programming Divide and Conquer Greedy Algorithm Decrease and Conquer | Divide and Conquer |
| Which of the following method is used for sorting in merge sort? Group of answer choices partitioning selection D exchanging merging | merging |
| A binary search is to be performed on the list: 3 5 9 10 123 How many comparisons would it take to find number 9? Group of answer choices 6-7 2-3 4-5 0-1 | 0-1 |
| What is the space complexity of quick sort? Group of answer choices O (1) O (n^2) O (n log n) Exponential | O (n log n) |
| A method that compute its problem of computational geometry. Group of answer choices Closest Pair Merge sort Strassen Algo Binary Search | Closest Pair |
| What is the time complexity of closest pair Group of answer choices Exponential O(1) O(n log n) O(n!) | O(n log n) |
| When computing for p7 what the exact formula? Group of answer choices p7=(a-c)+(e+f) p7=(a-c)(e+f) p7=(a-c)+(e-f) p7=(a*c)(e+f) | p7=(a-c)(e+f) |
Created by:
jekong