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
Algorithms MIDTERMS
| Question | Answer |
|---|---|
| What is the average-case time complexity of Merge sort? | O (n log n) |
| What is the space complexity of quick sort? | O (log n) |
| What is the time complexity of quick sort for worse case? | O (n^2) |
| The Strassen algorithm is named after? | Volker Strassen |
| What year did Strassen published his algorithm that proves the n^3 general matrix multiplication was not optimal? | 1969 |
| What is the worse time complexity of Strassen algorithm | O(n^2.8074) |
| What is the optimal time required for solving the closest pair problem using divide and conquer approach? (complexity) | O(n log n) |
| Using brute force algorithm in solving Strassen algorithm how many multiplication and addition are required? | 8 multiplication 4 addition |
| When computing for p1 what is the exact formula? (Strassen) | p1=a(f-h) |
| What is the time complexity of quick sort for best case? | O(n log n) |
| What do you call the step or stage in the divide and conquer method that recursively combines them until they formulate a solution of the original problem? | Combine |
| What do you call the step that receives a lot of smaller sub-problems to be solved. (Steps in Divide & Conquer) | Solve |
| What do you call the sorting technique that divides the array into equal halves and then combines them in a sorted manner? | Merge Sort |
| What is the time complexity of binary search? | O (n log) |
| What is the running time of Strassen’s algorithm for matrix multiplication? (big O notation) | O(n^2.8074) |
| What was the algorithm that Strassen algorithm was compared which resulted to a faster matrix multiplication? | Coppersmith-Winograd algorithm |
| When computing for p3 what is the exact formula is? (Strassen) | p3=(c+d)e |
| When computing for p4 what is the exact formula? | p4=d(g-e) |
| Strassen’s matrix multiplication algorithm follows ___________ technique. | Divide and Conquer |
| What is the worst-case time complexity of Merge sort? | O (n log n) |
| The Strassen algorithm is known as? | Matrix multiplication |
| In divide and conquer, the time is taken for merging the subproblems is? | O(n log n) |
| A method that compute its problem of computational geometry. | Closest Pair |
| What is the time complexity of closest pair | O(n log n) |
| It refers to the general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement. | Brute force/Exhaustive Search |
| There are how many steps in writing the brute force string matching algorithm | 3 |
| It refers to an algorithm that is an effective method that can be expressed within a finite amount of space and time and in a well-defined formal language for calculating a function. | Brute force |
| What is the time complexity of the brute force solution? | O(mn) |
| What is the time efficiency of the brute force string match? | O(mn) |
| What is the other term use to describe brute force? | Exhaustive Search |
| It derives its name from the problem faced by someone who is constrained by a fixed-size backpack and must fill it with the most valuable items. | Knapsack problem |
| It generates a list of all potential solutions to the problem in a systematic manner evaluate potential solutions one by one, disqualifying infeasible ones. | Brute force/Exhaustive Search |
| What is the efficiency of knapsack problem? | O(2^n) |
| This approach is used in real-world decision-making processes in a wide variety of fields, such as finding the least wasteful way to cut raw materials, selection of investments and portfolios | Knapsack problem |
| The Knapsack problem is an example of ____________ | Brute Force |
| There are how many steps in the selection sort algorithm | 5 |
| Which of the following methods can be used to solve the Knapsack problem? | Brute force, recursion |
| __________ A statement that repeatedly executes until the controlling condition becomes false. | iteration |
| __________ programming technique that terminates when a base case is recognized | recursion |
| Experiments must be reproducible. True or False? | True |
| Predict is events using the hypothesis. True or False? (Scientific Methods Applied to Analysis of Algorithms) | True |
| Hypothesize is a model that is consistent with the observation. True or False? (Scientific Methods Applied to Analysis of Algorithms) | True |
| A programming technique that makes the code smaller | recursion |
| Time efficiency or time complexity indicates how fast an algorithm runs. True or False? | True |
| There are how many scientific method use on performance and comparing algorithms? | 5 |
| Process that means must be falsifiable. (Scientific Methods Applied to Analysis of Algorithms) | Hypothesis |
| __________ A process in which a function calls itself directly or indirectly | recursion |
| This algorithmic check for the efficiency looking at the max input of n. Choices: best, worst average | worst |
| _int16, short, unsigned short consume 2 bytes. True or False. | True |
| What do you call the sum of cost x frequency for all operations. | Total running time |
| Instruction Space is the amount of memory used to save the compiled version of instructions. | True |
| n^2 is an example of that type of time complexity class | Quadratic |
| __________ uses repetition structure. Choices: A. Iteration B. Recursion | A. Iteration |
| __________ terminates when the loop condition fails. Choices: A. Iteration B. Recursion | A. Iteration |
| Space Efficiency or space complexity is the amount of memory units required by the algorithm including the memory needed for the i/p & o/p. True or False? | True |
| There are 5 scientific method use on performance and comparing algorithms. True or False? | True |
| __________ consumes less memory Choices: A. Iteration B. Recursion | A. Iteration |
| Bool, char, unsigned char data types consume size of 1 byte. True or False? | True |
| A powerful technique that can be used in place of iterations. | Recursion |
| n log n, log n! is an example of that type of time complexity class | quasilinear |
| n^3 is an example of that type of time complexity class | Cubic |
Created by:
RalphClarence