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
Alg-Mt
Alg-SA-Two
| Question | Answer |
|---|---|
| ______ is an algorithm compares the pattern to the text, one character at a time, until un-matching characters are found: Group of answer choices Divide and conquer Dynamic programming Transform and conquer Brute force | Brute force |
| It’s a sorting algorithm that sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning Group of answer choices Selection Merge Bubble Quick | Selection Sort |
| What is the time efficiency of the brute force string match? Group of answer choices O(mn) O(1) exponential (nm2) | O(mn) |
| In the given code snippet below, pseudocode of brute force string, what does m represents? for i ← to n-m do j ← 0 while j<m and P[j} = T[i+j] do _________ if j=m return i __________ | characters representing a pattern |
| Given the text pattern, Find the first index in the pattern Text: A A B A A C A A D A A B A A B A Pattern: A A B A 15 12 9 0 | 0 |
| Given input string = “THIS IS A TEST TEXT” and pattern string = “TEXT”. Find the first index of the pattern match using quick search algorithm Group of answer choices 14 16 17 15 | 15 |
| Given input string = “ABCDABCATRYCARCABCSRT” and pattern string = “CAT”. Find the first index of the pattern match using quick search algorithm Group of answer choices 11 2 14 6 | 6 |
| An algorithm that calculate the total distance for every possible route and then select the shortest one. Group of answer choices Greedy Dynamic Programming Exhaustive Search Divide and Conquer | Exhaustive Search |
| There are how many steps in writing the brute force string matching algorithm 5 6 3 4 | 3 |
| It finds the location of a specific text pattern within a larger body of text? seeking Brute force pattern matching string search | string search |
| A process there it involves searching for an element with a special property, usually among combinatorial objects such as permutations, combinations, or subsets of a set. Dynamic programming Brute force Divide and Conquer Traveling Salesman | Brute force |
| You are given a knapsack that can carry a maximum weight of 60. There are 4 items with weights {20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of the items you can carry using the knapsack? 90 160 170 200 | 160 |
| What is the time complexity of the brute force algorithm used to solve the Knapsack problem? Group of answer choices O(2^n) Exponential O(n) O(1) | O(2^n) |
| 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. Traveling Salesman Knapsack problem Dynamic programming Brute force | Knapsack problem |
| According to the Stony Brook University Algorithm Repository, what is the ranked of the knapsack problem? 19th 20th 17th 18th | 19th |
| The Knapsack problem is an example of ____________ Divide and Conquer Greedy Brute Force Transform and conquer | Brute force |
| Given the text pattern, how many match can you derived from it? Text: A A B A A C A A D A A B A A B A Pattern: A A B A 2 3 4 0 | 3 |
| Which is an advantage of using a brute force from the following list? It yields ѕtаndаrd аlgоrіthmѕ fоr simple соmрutаtіоnаl tasks, It rаrеlу уіеldѕ еffісіеnt аlgоrіthmѕ | It yields ѕtаndаrd аlgоrіthmѕ fоr simple соmрutаtіоnаl tasks, |
| There are how many steps in the selection sort algorithm 5 6 7 4 | 5 |
| Refers to a string of M characters to search for text string matching pattern string | Pattern |
| It finds the location of a specific text pattern within a larger body of text? Group of answer choices Brute force seeking string search pattern matching | string search |
| Compares a given pattern with all substrings of a given text. Brute force Brute force string matching selection sort None of the above | Brute force string matching |
| How many sub-arrays does selection sort maintains? 5 4 2 3 | 2 |
| An algorithm that calculate the total distance for every possible route and then select the shortest one. Dynamic Programming Greedy Exhaustive Search Divide and Conquer | Exhaustive Search |
| Given the text pattern, What is the index of the second pattern Text: A A B A A C A A D A A B A A B A Pattern: A A B A 9 10 12 13 | 9 |
| What is the time complexity of the brute force algorithm used to solve the Knapsack problem? Group of answer choices O(n) Exponential O(2^n) O(1) | O(2^n) |
| The 0-1 Knapsack problem can be solved using Greedy algorithm True False | True (dapat false to) |
| This approach is an example of combinatorial optimization. Dynamic programming Traveling Salesman Brute force Knapsack problem | Knapsack problem |
| In the travelling salesman problem, what do you call the stating point? Starting point Top Vertex Edge | Vertex |
| The main challenge of the traveling salesman is? maximize the cost minimize travel None tour cities | minimize travel |
| What is the auxiliary space complexity of merge sort? O(n log n) O(1) O(n) Exponential | O(n) |
| Which of the following method is used for sorting in merge sort? D exchanging merging selection partitioning | merging |
| What is the time complexity of quick sort for worse case? O (n^2) O (1) Exponential O (n log n) | O (n^2) |
| 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? 2-3 6-7 4-5 0-1 | 0-1 |
| What do you call a sorting algorithm that partitions an array and then calls itself recursively twice to sort the two resulting subarrays. Group of answer choices Insertion Sort Bubble Sort Quick Sort Merge Sort | Quick sort |
| Select the best description to explain what a binary search algorithm is Put the elements in order, compare with the middle value, split the list in order and repeat Elements do not need to be in order, check each item in turn. | Put the elements in order, compare with the middle value, split the list in order and repeat |
| Merge Sort can be categorized into which of the following? Decrease and Conquer Divide and Conquer Dynamic Programming Greedy Algorithm | Divide and Conquer |
| What do you call the step in the Divide and conquer approach that involves breaking the problem into smaller sub-problems? Group of answer choices Collapse Halt Breakdown | Break |
| Describe an advantage of a binary search algorithm Can only work on an ordered list. If unordered must use a linear search. Data does not need to be in order. Performs well over large ordered lists. Slow with large data sets. | Performs well over large ordered lists. |
| What is the time complexity of closest pair O(n!) O(1) O(n log n) Exponential | O(n log n) |
| What is the running time of naïve matrix multiplication algorithm? O(n^2.8074) O(n^4) O(n) O(n^3) | O(n^3) |
| What is the worse time complexity of Strassen algorithm O(n^3.8974) O(n^2.8074) O(n^3.8074) O(n^2.8974) | O(n^2.8074) |
| There are a total of _______ sub-matrices in solving for the Strassen algorithm 8 6 9 7 | 8 |
| A method that compute its problem of computational geometry. Strassen Algo Merge sort Closest Pair Binary Search | Closest Pair |
| There are how many steps in the closest pair algorithm? 6 7 8 9 | 7 |
| What was the algorithm that Strassen algorithm was compared which resulted to a faster matrix multiplication? Coppersmith algorithm Copper Winograd algorithm Coppersmith-Winograd algorithm Smith-Winograd algorithm | Coppersmith-Winograd algorithm |
| The Strassen algorithm is known as a? Matrix multiplication Matrix subtraction Matrix Addition Matrix Division | Matrix multiplication |
| Strassen’s algorithm is a/an_____________ algorithm. Approximation Accurate Non-recursive Recursive | Recursive |
| What is the optimal time required for solving the closest pair problem using divide and conquer approach? O(1) O(n log n) O(n!) Exponential | O(n log n) |
| The searching phase in quick search algorithm has good practical behaviour. Group of answer choices No answer text provided. No answer text provided. False True | True |
| It refers to the general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the solution Greedy Divide and Conquer Brute force Dynamic Programming | Brute force |
| It’s a sorting algorithm that sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning Group of answer choices Selection Merge Quick Bubble | Selection |
| Complete the code snippet below, pseudocode of brute force string for i ← to n-m do j ← 0 while j<m and P[j} = T[i+j] do _________ if j=m return i return -1 Group of answer choices J <- j +1 J <- j / 1 J <- j * 1 J<- j - 1 | J <- j +1 |
| Given input string = “THIS IS A TEST TEXT” and pattern string = “TEST”. Find the first index of the pattern match using quick search algorithm Group of answer choices 11 9 12 10 | 10 |
| ______ is an algorithm compares the pattern to the text, one character at a time, until un-matching characters are found: Group of answer choices Dynamic programming Divide and conquer Brute force Transform and conquer | Brute force |
| There are how many steps in writing the brute force string matching algorithm Group of answer choices 4 5 3 6 | 3 |
| How many sub-arrays does selection sort maintains? Group of answer choices 4 5 2 3 | 2 |
| It refers to the general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the solution Exhaustive Search Greedy Dynamic Programming Divide and Conquer | Exhaustive Search |
| Who was the mathematician who have done works on the knapsack problem Group of answer choices Tobby Dantzig Tobias Datzig Tobias Dantzig Tom Dantzig | Tobias Dantzig |
| 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 Dynamic programming Brute force Traveling Salesman Knapsack problem | Knapsack problem |
| This approach is an example of combinatorial optimization. Group of answer choices Traveling Salesman Dynamic programming Brute force Knapsack problem | Knapsack problem |
| The Knapsack problem is an example of ____________ Group of answer choices Greedy Brute Force Transform and conquer Divide and Conquer | Knapsack problem |
| The Knapsack problem is an example of ____________ Group of answer choices Greedy Brute Force Transform and conquer Divide and Conquer | Brute Force |
| The main challenge of the traveling salesman is? Group of answer choices tour cities maximize the cost minimize travel None | minimize travel |
| 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. Group of answer choices Knapsack problem Brute force Traveling Salesman Dynamic programming | Knapsack problem |
| Which is an advantage of using brute force from the following list? Sоmе brute-fоrсе algorithms are unacceptably slow It is neither as соnѕtruсtіvе nоr as сrеаtіvе It hаѕ wide applicability аnd is known for іtѕ ѕіmрlісіtу | It hаѕ wide applicability аnd is known for іtѕ ѕіmрlісіtу |
| Given input string = “ABCDABCATRYCARCABCSRT” and pattern string = “CAT”. Find the first index of the pattern match using quick search algorithm Group of answer choices 11 6 14 2 | 6 |
| Which is an advantage of using a brute force: Sоmе brute-fоrсе algorithms are slow It yields ѕtаndаrd аlgоrіthmѕ fоr simple соmрutаtіоnаl tasks, such аѕ sum аnd рrоduсt оf n numbеrѕ, It is neither as соnѕtruсtіvе nоr as сrеаtіvе | It yields ѕtаndаrd аlgоrіthmѕ fоr simple соmрutаtіоnаl tasks, such аѕ sum аnd рrоduсt оf n numbеrѕ, аnd finding the mаxіmum оr mіnіmum іn a lіѕt |
| Complete the code snippet below, pseudocode of brute force string for i ← to n-m do j ← 0 while j<m and P[j} = T[i+j] do _________ if j=m return i __________ Group of answer choices return i return -n return m return -1 | return -1 |
| An algorithm that calculate the total distance for every possible route and then select the shortest one. Group of answer choices Divide and Conquer Greedy Exhaustive Search Dynamic Programming | Exhaustive Search |
| What is the time efficiency of the brute force string match? Group of answer choices O(1) (nm2) O(mn) exponential | O(mn) |
| In the given code snippet below, what does m represents? for i ← to n-m do j ← 0 while j<m and P[j} = T[i+j] do _________ if j=m return i __________ characters representing a pattern value of character first search value none of the above | characters representing a pattern |
| According to the Stony Brook University Algorithm Repository, what is the ranked of the knapsack problem? Group of answer choices 17th 20th 19th 18th | 19th |
| You are given a knapsack that can carry a maximum weight of 60. There are 4 items with weights {20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of the items you can carry 90 160 170 200 | 160 |
| Given input string = “TWO ROADS DIVERGED IN A YELLOW WOOD” and pattern string = “ROADS”. Find the first index of the pattern match using quick search algorithm Group of answer choices 5 4 6 3 | 4 |
| It finds the location of a specific text pattern within a larger body of text? Group of answer choices string search seeking pattern matching Brute force | string search |
| 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. Divide and Conquer Dynamic Programming Brute force Greedy | Brute force |
| What is the time complexity of the brute force solution? Group of answer choices O(n) O(mn) Exponential O(1) | O(mn) |
| A process there it involves searching for an element with a special property, usually among combinatorial objects such as permutations, combinations, or subsets of a set. Brute force Divide and Conquer Dynamic programming Traveling Salesman | Brute force |
| Which of the following methods can be used to solve the Knapsack problem? Group of answer choices brute force, recursion divide and conquer recursion dynamic programming | brute force, recursion |
| In the travelling salesman problem, what do you call the stating point? Group of answer choices Starting point Top Edge Vertex | Vertex |
| It generates a list of all potential solutions to the problem in a systematic manner evaluate potential solutions one by one, disqualifying infeasible ones Divide and Conquer Dynamic programming Exhaustive search Traveling Salesman | Exhaustive search |
| Compares a given pattern with all substrings of a given text. Brute force string matching selection sort Brute force None of the above | Brute force string matching |
| The 0-1 Knapsack problem can be solved using Greedy algorithm Group of answer choices False True | False |
| Refers to a string of M characters to search for | pattern |
| A brute force problem that has to visit each one of the cities starting from a certain one (e.g. the hometown) and returning to the same city. | traveling salesman |
| What is the efficiency of knapsack problem? | O(2^n) |
| 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 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 |
| 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) |
| a sequence of unmbiguous instructions for solving a problem | algorithm |
| this is the process of obtaining a required output for any legitimate input in a finite amount of time | algorithm |
| this is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output | algorithm |
| it is a sequence of computational steps that transform the input into the output | algorithm |
| in this step, the programmer must be able to understand fully the problem statement before starting to work on the solution | Problem definition |
| this element of problem statement is stated clearly and with enough contextual detail to establish its importance | the PROBLEM itself |
| this element of problem statement is often stated as a claim or a working thesis | the METHOD of solving the problem |
| this element of problem statement is a statement of objective and scope of the document the writer is preparing | the PURPOSE |
| in this step, the definition of model objectives, conceptualization of the problem, translation into a computational model, and model testing, revision, and application is performed | Development of a model (Model Development) |
| model development is an ________ process, in which many models are derived, tested and built upon until a model fitting the desired criteria is built | iterative |
| where should subsequent modelling work may need to begin the search given that a previous original model has already been built? | at the same place as the original model building began |
| in this step, all algorithms must satisfy a criteria involving input, output, definiteness, finiteness, and effectiveness | Specification of an algorithm |
| this criteria specifies that an algorithm has zero or more of it, taken from a specified set of objects | input |
| this criteria specifies that an algorithm has one or more of it, which have a specified relation to another criteria involving a subset of objects | output |
| this criteria specifies that an algorithm must have steps that are precisely defined; each instruction is clear and inambiguous | definiteness |
| this criteria specifies that an algorithm must always terminate after a finite number of steps | finiteness |
| this criteria specifies that an algorithm must have all of its operations sufficiently basic that they can be done exactly and in finite length | effectiveness |
| in this step, the algorithm will be examined if it is correct with respect to a specification | Checking the correctness of an algorithm |
| in theoretical computer science, ________ of an algorithm is asserted when it is said that the algorithm is correct with respect to a specification | correctness |
| this refers to the input-output behavior of the algorithm | functional correctness |
| _____ correctness requires that if an answer is returned it will be correct, and ______ correctness additionally requires that the algorithm terminates | partial; total |
| this is a type of mathematical proof that plays a critical role in formal verification because total correctness of an algorithm depends on termination | termination proof |
| since there is no general solution to the halting problem, a ___________ assertion may lie much deeper | total correctness |
| this is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever | the halting problem |
| in this step, the amount of time and space resources required to execute an algorithm is determined | Analysis of an algorithm |
| the _______ or running time of an algorithm is stated as a function relating the input length to the number of steps, known as ___________, or volume of memory, known as ____________ | efficiency; time complexity; space complexity |
| in this step, the efficiency and time/space complexity of an algorithm is determined | Analysis of an algorithm |
| in this step, the degree of correctness and whether it terminates or not is determined | Checking the correctness of an algorithm |
| a series of steps that you expect will arrive at a specific solution | algorithm |
| in this step, we establish the rules of a problem, explore the problem space, write the test and verify solution, specify a plan that should sovle the problem & elaborate it into steps, and translate each step into code | Implementation of an algorithm |
| in order to understand how to _______ an Algorithm, we first need to conceptually understand what an Algorithm is | implement |
| this does not equal expressing code, that idea ignores and neglects the entire idea of writing code to solve a problem | writing a program |
| in this step, a program is executed with the intent of finding errors | Program testing |
| this is the process of executing a program with the intent of finding errors | program testing |
| a good ____ is one that has a high probability of finding an error | test |
| program testing cannot show the absence of _____; it can only show if they are present | errors |
| is it impossible to write the tests before the program? | no |
| in this step, the team keeps track of all aspects of an application and it improves on the quality of a software product | Documentation |
| its main focuses are development, maintenance and knowledge transfer to other developers | documentation |
| this will make information easily accessible, provide a limited number of user entry points, help new users learn quickly, simplify the product and help cut support costs | documentation |
| this is usually focused on the following components that make up an application: server environments, business rules, databases/files, troubleshooting, application installation and code deployment | documentation |
| this gives a high-level description of an algorithm without the ambiguity associated with plain text but also without the need to know the syntax of a particular programming language | pseudocode |
| the running time can be estimated in a more general manner by using ________ to represent the algorithm as a set of fundamental operations which can then be counted | pseudocode |
| this is a formal definition with some specific characteristics that describes a process, which could be executed by a Turing-complete computer machine to perform a specific task | algorithm |
| generally, the word "________" can be used to describe any high level task in computer science | algorithm |
| this is an informal and (often rudimentary) human readable description of an algorithm leaving many granular details of it | pseudocode |
| writing a _________ has no restriction of styles and its only objective is to describe the high level steps of algorithm in a much realistic manner in natural language | pseudocode |
| what is the theoretical importance of studying algorithms? | the core of computer science |
| he is the 9th century mathematician | Muhammad ibn Musa al-Khwarizmi |
| whose algorithm is known for finding the GCD? | Euclid's algorithm |
| this is an ancient algorithm for finding all prime numbers up to any given limit | sieve of eratosthenes |
| find the gcd of 60 and 24 using Euclid's algorithm | gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12 |
| enumerate the 3 steps of Euclid's algorithm | say we're solving for gcd(m, n) and remainder is r, STEP 1: if n = 0, return m else continue, STEP 2: divide m by n and put the remainder to r, STEP 3: assign n as the new m and r as the new n and return to step 1 |
| a problem type that involves rearranging the items of a given list in ascending or descending order | sorting |
| algorithms often use sorting as a key _______ | subroutine |
| this is a specially chosen piece of information used to guide sorting (e.g., sort student records by names) | sorting key |
| evaluate sorting algorithm complexity: the number of __________ | key comparisons |
| enumerate the 2 properties of a sorting algorithm | Stability, In place (SI) |
| a property of sorting algorithms which checks if it preserves the relative order of any two equal elements in its input | stability |
| a property of sorting algorithms which checks if it does not require extra memory except possibly for a few memory units | in place |
| a problem type that involves finding a given value in a given set | searching |
| searching is finding a given value, called a ________, in a given set | search key |
| enumerate the 2 examples of searching algorithms | Sequential search, Binary search (SB) |
| a searching algorithm where you go through whole data sequentially until you find the match | sequential search |
| a searching algorithm where at each stage you can divide data into two (bi) parts | binary search |
| a searching algorithm where you don't have to traverse through whole data | binary search |
| a searching algorithm that applies best for unsorted collections of data | sequential search |
| in this, data is not sorted but it is stored in the memory in a tree-like way | binary search tree |
| a problem type where a sequence of characters from an alphabet, called a string, is processed or manipulated | string processing |
| this is a sequence of characters from an alphabet | string |
| this is a type of string consisting of letters, numbers, and special characters | text string |
| this is the process of searching for a given word/pattern in a text | string matching |
| a problem type where we deal with a collection of points called vertices, some of which are connected by line segments called edges | graph problems |
| a graph is a collection of points called _____, some of which are connected by line segments called _____ | vertices; edges |
| modeling WWW, communication networks, and project scheduling use this | graphs |
| this is a sequence of n items of the same data type that are stored contiguously in computer memory and made accessible by specifying a value of its index | array |
| this is a sequence of zero or more nodes each containing two kinds of information: some data and one or more links called pointers to other nodes | linked list |
| a list that permits direct access | array |
| a list that permits access by following links | linked list |
| a(n) _______ has fixed length and needs preliminary reservation of memory while a(n) ______ has dynamic length and arbitrary memory locations | array; linked list |
| this data structure's insertion/deletion can be done only at the top | stack |
| this data structure's insertion is done from the back and deletion from the front | queue |
| inserting in a queue is called _______ and removing from it is called _______ | enqueue; dequeue |
| the ____ data structure is LIFO/FILO while ____ is FIFO/LILO | stack; queue |
| inserting in a stack is called _______ and removing from it is called _______ | push; pop |
| this is a data structure for maintaining a set of elements, each associated with a key/priority, with the following operations: finding/deleting the element with the highest priority and inserting a new element | priority queue |
| priority queues are implementing using ___ | heaps |
| scheduling jobs on a shared computer uses what data structure | priority queue |
| a _______ G = <V, E> is defined by a pair of two sets: a finite set V of items called vertices and a set E of vertex pairs called edges | graph |
| enumerate the 2 types of graph and their difference | Undirected (two-way arrows), Directed (digraphs, one-way) |
| a graph in which each pair of distinct vertices is connected by a unique edge | complete graph |
| a graph in which the number of edges is close to the maximum possible for that graph | dense graph |
| dense graph this is a n x n boolean matrix if |V| is n, and the element on the ith row and jth column is 1 if there?s an edge from ith vertex to the jth vertex; otherwise 0 | adjacency matrix |
| the adjacency matrix of an _______ graph is symmetric | undirected |
| these are graphs or digraphs with numbers assigned to the edges | weighted graphs |
| a ____ from vertex u to v of a graph G is defined as a sequence of adjacent (connected by an edge) vertices that starts with u and ends with v | path |
| a path where all edges are distinct | simple paths |
| this is the number of edges, or the number of vertices - 1 | path length |
| a graph is said to be ______ if for every pair of its vertices u and v there is a path from u to v | connected |
| this is the maximum connected subgraph of a given graph | connected component |
| this is a simple path of a positive length that starts and ends at the same vertex | cycle |
| this is what you call a graph without cycles | acyclic graph |
| this is what you call a directed graph without cycles | directed acyclic graph (DAG) |
| this is what you call a connected acyclic graph | tree (free tree) |
| tree (free tree) a graph that has no cycles but is not necessarily connected | forest |
| tree (free tree) for every two vertices in a ____ there always exists exactly one simple path from one of these vertices to the other | tree |
| tree (free tree) the unique property of trees makes it possible to select an arbitrary vertex in a free tree and consider it as the root of the so called ____ tree | rooted |
| for any vertex v in a tree T, all the vertices on the simple path from the root to that vertex are called ________ | ancestors |
| all the vertices for which a vertex v is an ancestor are said to be _______ of v | descendants |
| if (u, v) is the last edge of the simple path from the root to vertex v, u is said to be the ___ of v and v is called a ___ of u | parent; child |
| vertices that have the same parent are called ____ | siblings |
| a vertex without children is called a ____ | leaf |
| a vertex v with all its descendants is called the ____ of T rooted at v | subtree |
| this is the length of the simple path from the root to the vertex | depth of a vertex |
| this is the length of the longest simple path from the root to a leaf | height of a tree |
| this is a rooted tree in which all the children of each vertex are ordered | ordered tree |
| this is an ordered tree in which every vertex has no more than two children and each children is designated as either a left child or a right child of its parent | binary tree |
| this is a binary tree where each vertex is assigned a number; a number assigned to each parental vertex is larger than all the numbers in its left subtree and smaller than all the numbers in its right subtree | binary search tree |
| a process in which a function calls itself directly or indirectly | recursion |
| a process which breaks a task into smaller subtasks | recursion |
| a powerful technique that can be used in place of iterations | recursion |
| in recursion, this should be defined to avoid infinite loops | base case |
| ________ is when a statement in a function calls itself repeatedly, while ________ is when a loop repeatedly executes until the controlling condition becomes false | recursion; iteration |
| the primary difference between iteration and recursion is that ______ is a process, always applied to a function and ______ is applied to the set of instructions which we want to get repeatedly executed | recursion; iteration |
| ____ uses repetition structure, while ____ uses selection structure | iteration; recursion |
| this occurs with iteration if the loop condition test never becomes false | infinite loop |
| infinite looping uses ___ cycles repeatedly | CPU |
| an iteration terminates when the loop condition ____ | fails |
| why is iteration faster than recursion? | an iteration does not use the stack |
| who consumes more memory? recursion or iteration? | recursion (too much will cause stack overflow) |
| who makes the code longer? recursion or iteration? | iteration |
| this occurs with recursion if the recursion step does not reduce the problem in a manner that converges on some condition (base case) | infinite recursion |
| what can infinite recursion do to the system? | crash it |
| recursion terminates when a _______ is recognized | base case |
| recursion is usually slower than iteration due to the overhead of _______ | maintaining the stack |
| recursion makes the code length _______ | smaller |
| if we compare recursion implementation against recursion it is at least _____ slower | twice |
| a function is called _____ recursive if it calls the same function again | direct |
| a function is called _____ recursive if it calls another function and then that function calls the original function directly or indirectly | indirect |
| a function is called _____ recursive if the recursive call is the last thing done by the function (there is no need to keep record of the previous state) | tail |
| a function is called _____ recursive if the recursive call is not the last thing done by the function (after returning back, there is something left to evaluate/do) | non-tail |
| the efficiency of an algorithm can be in terms of ___ or ___ | time or space |
| checking whether the algorithm is efficient or not, means ______ the algorithm | analyzing |
| there is a systematic approach that has to be applied for analyzing any given algorithm; and this approach is modelled by a framework called _____________ | analysis framework |
| the _______ of an algorithm can be decided by measuring the performance of an algorithm | efficiency |
| this is the process of investigation of an algorithm's efficiency respect to two resources: running time and memory space | analysis of algorithm |
| in algorithm analysis, this indicates how fast an algorithm runs | time efficiency / time complexity |
| in algorithm analysis, this is the amount of memory units required by the algorithm including the memory needed for the i/p & o/p | space efficiency / space complexity |
| this describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions | big O notation |
| the __________ of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem | time complexity |
| when time complexity is expressed using big O notation, it is said to be described _______, i.e., as the input size goes to infinity | asymptotically |
| the analysis of _______ and ________ is the major force that drives the design of solutions | algorithms and data structure |
| if there are many solutions to a problem...? | pick the most efficient one |
| how to compare various algorithms? | analyze algorithms |
| this is the process of analyzing the cost of the algorithm | algorithm analysis |
| cost, in terms of algorithm analysis, asks how much ____ does the algorithm require | time & space (memory) |
| the primary efficiency measure for an algorithm is ____ | time |
| all concepts discussed for time analysis also apply to ____ analysis | space |
| cost = ____ + ____ | space + time |
| the running time of an algorithm increases with ____ size and depends on ________ | input; hardware |
| enumerate the 4 issues in the analysis of algorithms | Correctness, Time efficiency, Space efficiency, Optimality (COST) |
| enumerate the 2 approaches in the analysis of algorithms | Theoretical analysis, Empirical analysis (TE) |
| enumerate the 4 reasons to analyze algorithms | Predict performance, Compare algorithms, Provide guarantees, Understand theoretical basis (PCPU) |
| client gets ____ performance because programmer did not understand performance characteristics | poor |
| the scientific method applied to algorithm analysis is a framework for __________ and __________ | predicting performance and comparing algorithms |
| what are the 2 principles of scientific method applied to algorithm analysis | experiments must be REPRODUCIBLE, hypothesis must be FALSIFIABLE |
| who created the analytical engine, the first programmable device? | charles babbage |
| two ways of timing a program | manual and automatic |
| an ________ analysis of an algorithm involves running the program for various input sizes and measuring the running time (often in ms) | empirical |
| in data analysis, this is a plot that has the running time T(N) as y-axis and the input size N as x-axis | standard plot |
| in data analysis, this is a plot of the log of the running time log(T(N)) vs. log of the input size log(N) | log-log plot |
| experimental algorithmics analyzes two types of system effects, what are they? | system independent (algorithm, input), system dependent (hardware, software, system) |
| this is the amount of memory required by an algorithm (including the input values) to run | space complexity |
| this is tenumerate the 3 things for any algorithm memory may be used for | Variables (const/temp values), Program instruction, Execution (VPE) |
| this details how much memory, in the worst case, is needed at any point in the algorithm | space complexity |
| this is the extra space or the temporary space used by the algorithm during its execution | auxiliary space |
| space complexity = ______ space + ______ space | auxiliary space + input space |
| enumerate the 3 reasons algorithms use memory space while executing | Instruction space, Environmental stack, Data space (IED) |
| this is the amount of memory used to save the compiled version of instructions | instruction space |
| this memory is used in situations where sometimes an algorithm (function) may be called inside another algorithm (function) | environmental stack |
| this is used when the current variables in a function is pushed onto the system stack because an inner function is called inside it | environmental stack |
| this is the amount of space used by the variables and constants | data space |
| while calculating the space complexity, we only consider the ______ and we neglect the ______ and ______ | data space; instruction space and environmental stack |
| for calculating the ____________, we need to know the value of memory used by different type of datatype variables, which generally varies for different operating systems, but the method for calculating it remains the same | space complexity |
| char and unsigned/signed char types have what size in bytes? | 1 byte |
| bool and __int8 types have what size in bytes? | 1 byte |
| __int16 and (unsigned) short types have what size in bytes? | 2 bytes |
| wchar_t and __wchar_t types have what size in bytes? | 2 bytes |
| float and (unsigned) long types have what size in bytes? | 4 bytes |
| __int32 and (unsigned) int types have what size in bytes? | 4 bytes |
| (long) double and long long types have what size in bytes? | 8 bytes |
| __int64 types have what size in bytes? | 8 bytes |
| to compute the space complexity, we use two factors: ______ and ______ | constant and instance characteristic |
| S(p) = C + Sp, where C (constant) is the space taken by _____ and Sp is the space dependent upon _____ | instruction, variable and identifiers; instance characteristic |
| this is a (typically numeric) measure of the properties of the input data that has a bearing on performance | instance characteristic |
| in the code { int z = a + b + c; return z; }, how many bytes is the total memory requirement? | variables a, b, c, and z are all integer types, hence they will take 4 bytes each, with an addition of 4 more bytes for the returned value totaling to 20 bytes (4 * 4 + 4 = 20) |
| if the space requirement is fixed and is a constant, it is called __________ | constant space complexity |
| in the code { int x = 0; for (int i = 0; i < n; i++) { x = x + a[i]; } return x; }, how many bytes is the total memory requirement? | 4 * n bytes is required for the input array (a[n]), 4 bytes each for each variable (x, n, i, return value), hence the total memory is 4n + 16 which increases linearly as n increases |
| if the space requirement increases linearly with input, it is called _________ | linear space complexity |
| we should always focus on writing algorithm code in such a way that we keep the space complexity _______ | minimum |
| this is the amount of time required by an algorithm to run for completion | time complexity |
| this is a count denoting number of times of execution of a statement | frequency count |
| in _______ system, executing time depends on many factors such as system load, number of other programs running, instruction set used, and speed of hardware | multiuser |
| a __________ has a single processor, 32 bit, sequential, 1 unit time for arithmetic/logical operations, and 1 unit time for assignment/return operations | model computer |
| finding the median value in a sorted array of numbers has what time complexity class? | constant |
| binary search has what time complexity class? | logarithmic |
| finding the smallest/largest item in an unsorted array has what time complexity class? | linear |
| fast fourier transform has what time complexity class? | linearithmic/quasilinear |
| bubble sort has what time complexity class? | quadratic |
| naive multiplication of two nxn matrices has what time complexity class? | cubic |
| AKS primality test has what time complexity class? | polynomial |
| solving matrix chain multiplication via brute-force search has what time complexity class? | exponential |
| solving the traveling salesman via brute-force search has what time complexity class? | factorial |
| an algorithm's time complexity is defined as T = 4n^3 + 3n^2 + n + 14, what is it in big O notation and its TC class? | O(n^3) - cubic |
| an algorithm's time complexity is defined as T = 16n + n log(n^3) + 2, what is it in big O notation and its TC class? | O(n log n) - linearithmic/quasilinear |
| an algorithm's time complexity is defined as T = log(n + 5) + 3n + 90, what is it in big O notation and its TC class? | O(n) - linear |
| this is the sum of cost x frequency for all operations | total running time |
| cost depends on ______ and _______ while frequency depends on _______ and ______ | machine and compiler; algorithm and input data |
| in principle, accurate ________ models are available | mathematical |
| time efficiency is analyzed by determining the ________ of the basic operation as a function of input size | number of repetitions |
| this is the operation that contributes the most towards the running time of the algorithm | basic operation |
| different basic operations may cost ________ | differently |
| in _________ analysis of time efficiency, we select a specific/typical sample of inputs and use a physical unit of time (ms) then analyze the data | empirical |
| enumerate all 3 cases in analyzing efficiency | Worst case, Best case, Average case (WBA) |
| this case is the maximum over inputs of size n | worst case - C_worst(n) |
| this case is the minimum over inputs of size n | best case - C_best(n) |
| this case is the "average" over inputs of size n | average case - C_avg(n) |
| this case is the number of times the basic operation will be executed on typical input | average case |
| is average case the average of the worse and best cases? | no |
| this case is the expected number of basic operations considered as a random variable under some assumption about the probability distribution of all inputs | average case |
| this is a way of saying/predicting how execution time of a program and the space/memory occupied by it changes with the input size | order of growth |
| this notation gives the worst case possibility for an algorithm | big O notation |
| the part of the program which takes the most amount of time is generally assumed to be the _________ in case of the Big-Oh notation | order of growth |
| enumerate the 3 types of asymptotic order of growth | Big Theta, Big Oh, Big Omega (TOO) |
| we use three types of ______ notations to represent the growth of any algorithm, as input increases | asymptotic |
| this notation is a class of functions that grow no faster than g(n) | O(g(n)) - Big Oh |
| this notation is a class of functions that grow at the same rate as g(n) | Theta(g(n)) - Big Theta |
| this notation is a class of functions that grow at least as fast as g(n) | Omega(g(n)) - Big Omega |
| this notation encloses the function from above and below | theta notation |
| this notation represents the upper and the lower bound of the running time of an algorithm | theta notation |
| this notation is used for analyzing the average case complexity of an algorithm | theta notation |
| a function f(n) belongs to the set _____ if there exist positive constants c1 and c2 such that it can be sandwiched between c1g(n) and c2g(n) for sufficiently large n | Theta(g(n)) |
| if a function f(n) lies anywhere in between c1g(n) and c2g(n) for all n >= n0, then f(n) is said to be __________ | asymptotically tight bound |
| this notation represents the upper bound of the running time of an algorithm | big-o notation |
| a function f(n) belongs to the set _____ if there exists a positive constant c such that it lies between 0 and cg(n) for sufficiently large n | O(g(n)) |
| since it gives the worst case running time of an algorithm, it is widely used to analyze an algorithm as we are always interested in the worst case scenario | big-o notation |
| this notation represents the lower bound of the running time of an algorithm | omega notation |
| this notation provides the best case complexity of an algorithm | omega notation |
| a function f(n) belongs to the set _____ if there exists a positive constant c such that it lies above cg(n) for sufficiently large n | Omega(g(n)) |
| for any value of n, the _____ time required by the algorithm is given by Omega(g(n)) | minimum |
| Muhammad ibn Musa al-Khwarizmi – 9th century mathematicia | TRUE |
| _________ is a sequence of unambiguous instructions for solving a problem. | algorithm |
| _________ thus a sequence of computational steps that transform the input into the output. | algorithm |
| ______ refers to an algorithm is asserted when it is said that the algorithm is correct with respect to a specification. | correctness |
| A criterion where all operations to be performed must be sufficiently basic that they can be done exactly and in finite length. | effectiveness |
| " A sequence of computational steps that transform the input into the output." | algorithm |
| TRUE | |
| "Adjacent Linked list is collection of linked lists, one for each vertex, that contain all the vertices adjacent to the list’s vertex." | TRUE |
| Linked list is sequence of zero or more nodes each containing two kinds of information: some data and one or more links called pointers to other nodes. | TRUE |
| " __________ searching for a given word/pattern in a text" | string matching |
| " Sorting ______ is a special piece of information used to guide sorting." | key |
| " A sorting property that if it preserves the relative order of any two equal elements in its input" | stability |
| " Finding a given value, called a search key, in a given set." | sorting |
| " Edges set E of vertex pairs." | TRUE |
| __________ is a collection of points called vertices, some of which are connected by line segments called edges. | graph |
| Model development is an __________ process. | iterative |
| Program testing is the process of executing a program with the intent of finding errors. | TRUE |
| " There are how many steps involved in solving computational problems" | 9 |
| Pseudocode gives a high-level description of an algorithm without the ambiguity associated with plain text but also without the need to know the syntax of a particular programming language. | TRUE |
| " It is a sequence of characters from an alphabet" | TRUE |
| " Connected components is the maximum connected subgraph of a given graph." | string |
| " Cycle simple path of a positive length that starts and ends a the same vertex." | TRUE |
| Queue uses FIFO / LILO approach. | TRUE |
| " __________ A sequence of n items of the same data type that are stored contiguously in computer memory and made accessible by specifying a value of the array’s index." | array |
| IT refers to an algorithm is asserted when it is said that the algorithm is correct with respect to a specification | correctness |
| There are how many elements of a problem statement | 3 |
| " A criterion where all operations to be performed must be sufficiently basic that they can be done exactly and in finite length" | effectiveness |
| __________ is finding a given value, called a search key, in a given set. | searching |
| " is a sorting property that does not require extra memory, except, possibly for a few memory units" | in place |
| " It refers to the correctness refers to the input-output behavior of the algorithm" | Functional |
| The presence of documentation helps keep track of all aspects of an application and it improves on the quality of a software product. | TRUE |
| " It refers to the process that a program must end finite number of steps." | Finiteness |
| _________ is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. | algorithm |
| " Ordered Tree is a rooted tree in which all the children of each vertex are ordered" | TRUE |
| "It refers to a sequence of unambiguous instructions for solving a problem " | Algorithm |
| "__________ is a sorting property that if it preserves the relative order of any two equal elements in its input. " | stability |
| "Cycle A simple path of a positive length that starts and ends a the same vertex. " | TRUE |
| "Arrays is sequence of n items of the same data type that are stored contiguously in computer memory " | TRUE |
| Vertices sets: a finite set V of items. | TRUE |
| Time efficiency or Time complexity indicates how fast a program runs | TRUE |
| Predict is events using Hypothesis | Predict ata |
| A statement that repeatedly executes until the controlling condition becomes false. | Iteration |
| __________ A statement that repeatedly executes until the controlling condition becomes false. | Iteration |
| Hypothesis must be falsifiable | TRUE |
| __________ uses repetition structure | Iteration |
| __________ A powerful technique that can be used in place of iterations. | recursion |
| A programming technique that makes the code smaller | recursion |
| __________ statement in a function calls itself repeatedly | recursion |
| Observe show features of the natural world | TRUE |
| A process where repeating until the hypothesis and observation agree | Validate |
| float, _int32 and unsigned long data type consume 4 bytes | TRUE |
| n2 is an example of that type of time complexity class | Quadratic |
| Space Complexity = Auxiliary Space + Input space | FALSE |
| When the input size measures the matrix dimension or total number of elements what is the basic operation | multiplication of two numbers |
| n log n, log n! is an example of that type of time complexity class | quasilinear |
| n log n, log n! is an example of that type of time complexity class Adding floating point numbers takes about how many nanoseconds to compute | 4.6 |
| 1.1n, 10n is an example of that type of time complexity class | exponential |
| A process in which a function calls itself directly or indirectly | Recursion |
| Validate means repeating until the hypothesis and observation agree | TRUE |
| __________ A process which breaks a task into smaller subtasks | recursion |
| Process that means must be falsifiable | Hypothesis |
| n! is an example of that type of time complexity class | factorial |
| Binary Search belongs in what class. | Logarithmic |
Created by:
rusean