Busy. Please wait.
Log in with Clever
or

show password
Forgot Password?

Don't have an account?  Sign up 
Sign up using Clever
or

Username is available taken
show password

Your email address is only used to allow you to reset your password. See our Privacy Policy and Terms of Service.


Already a StudyStack user? Log In

Reset Password
Enter the associated with your account, and we'll email you a link to reset your password.

MOD 1-4

Quiz yourself by thinking what should be in each of the black spaces below before clicking on it to display the answer.
        Help!  

Question
Answer
a sequence of unambiguous instructions for solving a problem   show
🗑
show 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   show
🗑
it is a sequence of computational steps that transform the input into the output   show
🗑
show Problem definition, Development of a model, Specification of an algorithm, Designing an algorithm, Checking the correctness of an algorithm, Analysis of an algorithm, Implementation of an algorithm, Program testing, Documentation (PDSDCAIPD)  
🗑
show Problem definition  
🗑
enumerate the 3 elements of problem statements   show
🗑
this element of problem statement is stated clearly and with enough contextual detail to establish its importance   show
🗑
show 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   show
🗑
show 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   show
🗑
where should subsequent modelling work may need to begin the search given that a previous original model has already been built?   show
🗑
show a common reason being that the model currently in service is poorly suited for reuse because it is poorly understood  
🗑
show Specification of an algorithm  
🗑
this criteria specifies that an algorithm has zero or more of it, taken from a specified set of objects   show
🗑
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   show
🗑
show Input, Output, Definiteness, Finiteness, Effectiveness (IODFE)  
🗑
this criteria specifies that an algorithm must have steps that are precisely defined; each instruction is clear and inambiguous   show
🗑
this criteria specifies that an algorithm must always terminate after a finite number of steps   show
🗑
this criteria specifies that an algorithm must have all of its operations sufficiently basic that they can be done exactly and in finite length   show
🗑
in this step, the algorithm will be examined if it is correct with respect to a specification   show
🗑
in theoretical computer science, ________ of an algorithm is asserted when it is said that the algorithm is correct with respect to a specification   show
🗑
this refers to the input-output behavior of the algorithm   show
🗑
show partial; total  
🗑
show termination proof  
🗑
show total correctness  
🗑
show the halting problem  
🗑
in this step, the amount of time and space resources required to execute an algorithm is determined   show
🗑
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 ____________   show
🗑
in this step, the efficiency and time/space complexity of an algorithm is determined   show
🗑
in this step, the degree of correctness and whether it terminates or not is determined   show
🗑
show 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   show
🗑
show implement  
🗑
this does not equal expressing code, that idea ignores and neglects the entire idea of writing code to solve a problem   show
🗑
enumerate the 5 steps in implementing an algorithm   show
🗑
in this step, a program is executed with the intent of finding errors   show
🗑
this is the process of executing a program with the intent of finding errors   show
🗑
show test  
🗑
show errors  
🗑
show no  
🗑
show Documentation  
🗑
show documentation  
🗑
show documentation  
🗑
show documentation  
🗑
enumerate the 4 main characteristics of algorithm   show
🗑
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   show
🗑
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   show
🗑
show algorithm  
🗑
generally, the word "________" can be used to describe any high level task in computer science   show
🗑
this is an informal and (often rudimentary) human readable description of an algorithm leaving many granular details of it   show
🗑
show pseudocode  
🗑
enumerate 5 issues related to algorithms   show
🗑
what is the theoretical importance of studying algorithms?   show
🗑
what is the practical importance of studying algorithms?   show
🗑
show Muhammad ibn Musa al-Khwarizmi  
🗑
show Euclid's algorithm  
🗑
show sieve of eratosthenes  
🗑
find the gcd of 60 and 24 using Euclid's algorithm   show
🗑
enumerate the 3 steps of Euclid's algorithm   show
🗑
what does the sieve of erastosthenes do?   show
🗑
a problem type that involves rearranging the items of a given list in ascending or descending order   show
🗑
show subroutine  
🗑
show sorting key  
🗑
evaluate sorting algorithm complexity: the number of __________   show
🗑
enumerate the 2 properties of a sorting algorithm   show
🗑
show stability  
🗑
a property of sorting algorithms which checks if it does not require extra memory except possibly for a few memory units   show
🗑
a problem type that involves finding a given value in a given set   show
🗑
show search key  
🗑
enumerate the 2 examples of searching algorithms   show
🗑
show sequential search  
🗑
a searching algorithm where at each stage you can divide data into two (bi) parts   show
🗑
a searching algorithm where you don't have to traverse through whole data   show
🗑
a searching algorithm that applies best for unsorted collections of data   show
🗑
in this, data is not sorted but it is stored in the memory in a tree-like way   show
🗑
a problem type where a sequence of characters from an alphabet, called a string, is processed or manipulated   show
🗑
this is a sequence of characters from an alphabet   show
🗑
this is a type of string consisting of letters, numbers, and special characters   show
🗑
this is the process of searching for a given word/pattern in a text   show
🗑
show graph problems  
🗑
show vertices; edges  
🗑
show graphs  
🗑
enumerate the 3 types of graph algorithms   show
🗑
show List, Stack, Queue, Priority Queue / Heap, Graph, Tree / Binary Tree, Set / Dictionary (LSQPGTS)  
🗑
enumerate the 3 types of list   show
🗑
show 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   show
🗑
show Singly (has next pointer only), Doubly (has next and previous pointers)  
🗑
a list that permits direct access   show
🗑
show linked list  
🗑
a(n) _______ has fixed length and needs preliminary reservation of memory while a(n) ______ has dynamic length and arbitrary memory locations   show
🗑
show stack  
🗑
this data structure's insertion is done from the back and deletion from the front   show
🗑
inserting in a queue is called _______ and removing from it is called _______   show
🗑
the ____ data structure is LIFO/FILO while ____ is FIFO/LILO   show
🗑
show 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   show
🗑
priority queues are implementing using ___   show
🗑
show priority queue  
🗑
show graph  
🗑
enumerate the 2 types of graph and their difference   show
🗑
a graph in which each pair of distinct vertices is connected by a unique edge   show
🗑
a graph in which the number of edges is close to the maximum possible for that graph   show
🗑
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   show
🗑
show undirected  
🗑
show adjacency linked lists  
🗑
enumerate the 2 ways you can represent a graph in code   show
🗑
show weighted graphs  
🗑
show path  
🗑
show simple paths  
🗑
this is the number of edges, or the number of vertices - 1   show
🗑
show connected  
🗑
this is the maximum connected subgraph of a given graph   show
🗑
this is a simple path of a positive length that starts and ends at the same vertex   show
🗑
this is what you call a graph without cycles   show
🗑
this is what you call a directed graph without cycles   show
🗑
this is what you call a connected acyclic graph   show
🗑
show forest  
🗑
show tree  
🗑
show rooted  
🗑
show ancestors  
🗑
all the vertices for which a vertex v is an ancestor are said to be _______ of v   show
🗑
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   show
🗑
show siblings  
🗑
show leaf  
🗑
a vertex v with all its descendants is called the ____ of T rooted at v   show
🗑
this is the length of the simple path from the root to the vertex   show
🗑
this is the length of the longest simple path from the root to a leaf   show
🗑
this is a rooted tree in which all the children of each vertex are ordered   show
🗑
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   show
🗑
show binary search tree  
🗑
show recursion  
🗑
a process which breaks a task into smaller subtasks   show
🗑
show recursion  
🗑
in recursion, this should be defined to avoid infinite loops   show
🗑
show recursion; iteration  
🗑
show recursion; iteration  
🗑
____ uses repetition structure, while ____ uses selection structure   show
🗑
show infinite loop  
🗑
show CPU  
🗑
an iteration terminates when the loop condition ____   show
🗑
show an iteration does not use the stack  
🗑
who consumes more memory? recursion or iteration?   show
🗑
show iteration  
🗑
show infinite recursion  
🗑
show crash it  
🗑
recursion terminates when a _______ is recognized   show
🗑
show maintaining the stack  
🗑
recursion makes the code length _______   show
🗑
show twice  
🗑
enumerate the 4 types of recursion   show
🗑
show direct  
🗑
a function is called _____ recursive if it calls another function and then that function calls the original function directly or indirectly   show
🗑
show tail  
🗑
show non-tail  
🗑
show time or space  
🗑
checking whether the algorithm is efficient or not, means ______ the algorithm   show
🗑
show analysis framework  
🗑
show efficiency  
🗑
show analysis of algorithm  
🗑
show Simplicity, Generality, Speed, Memory (SGSM)  
🗑
show 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   show
🗑
show 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   show
🗑
when time complexity is expressed using big O notation, it is said to be described _______, i.e., as the input size goes to infinity   show
🗑
the analysis of _______ and ________ is the major force that drives the design of solutions   show
🗑
if there are many solutions to a problem...?   show
🗑
show analyze algorithms  
🗑
show algorithm analysis  
🗑
cost, in terms of algorithm analysis, asks how much ____ does the algorithm require   show
🗑
the primary efficiency measure for an algorithm is ____   show
🗑
show space  
🗑
cost = ____ + ____   show
🗑
the running time of an algorithm increases with ____ size and depends on ________   show
🗑
show Correctness, Time efficiency, Space efficiency, Optimality (COST)  
🗑
show Theoretical analysis, Empirical analysis (TE)  
🗑
enumerate the 4 reasons to analyze algorithms   show
🗑
show to avoid performance bugs  
🗑
show poor  
🗑
show predicting performance and comparing algorithms  
🗑
show Observe the natural world, Hypothesize a model consistent with the observations, Predict events using the hypothesis, Verify these predictions by making more observations, Validate by repeating until hypothesis and observation agree (OHPVV)  
🗑
what are the 2 principles of scientific method applied to algorithm analysis   show
🗑
show charles babbage  
🗑
two ways of timing a program   show
🗑
show 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   show
🗑
show log-log plot  
🗑
show system independent (algorithm, input), system dependent (hardware, software, system)  
🗑
show system independent and dependent effects  
🗑
in power law, these effects determine constant b   show
🗑
a type of system effects that deals with the algorithm itself and the input data   show
🗑
a type of system effects that deals with the hardware (cpu, memory, cache), software (compiler, interpreter, GBC), system (OS, network, other apps)   show
🗑
this is the amount of memory required by an algorithm (including the input values) to run   show
🗑
this details how much memory, in the worst case, is needed at any point in the algorithm   show
🗑
show Variables (const/temp values), Program instruction, Execution (VPE)  
🗑
show auxiliary space  
🗑
space complexity = ______ space + ______ space   show
🗑
show Instruction space, Environmental stack, Data space (IED)  
🗑
this is the amount of memory used to save the compiled version of instructions   show
🗑
show 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   show
🗑
show data space  
🗑
show data space; instruction space and environmental stack  
🗑
show space complexity  
🗑
show 1 byte  
🗑
show 1 byte  
🗑
__int16 and (unsigned) short types have what size in bytes?   show
🗑
show 2 bytes  
🗑
show 4 bytes  
🗑
__int32 and (unsigned) int types have what size in bytes?   show
🗑
show 8 bytes  
🗑
show 8 bytes  
🗑
show constant and instance characteristic  
🗑
show 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   show
🗑
show 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)  
🗑
show 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?   show
🗑
if the space requirement increases linearly with input, it is called _________   show
🗑
we should always focus on writing algorithm code in such a way that we keep the space complexity _______   show
🗑
show time complexity  
🗑
show frequency count  
🗑
show multiuser  
🗑
enumerate the 4 elements to consider in analyzing time complexity   show
🗑
show model computer  
🗑
show Constant - O(1), Logarithmic - O(log n), Linear - O(n), Linearithmic/Quasilinear - O(n log n), Quadratic - O(n^2), Cubic - O(n^3), Polynomial - O(n^k) k >= 1, Exponential - O(a^n) a >= 1, Factorial - O(n!) --- (CLLLQCPEF)  
🗑
finding the median value in a sorted array of numbers has what time complexity class?   show
🗑
show logarithmic  
🗑
finding the smallest/largest item in an unsorted array has what time complexity class?   show
🗑
fast fourier transform has what time complexity class?   show
🗑
show quadratic  
🗑
naive multiplication of two nxn matrices has what time complexity class?   show
🗑
show polynomial  
🗑
show exponential  
🗑
solving the traveling salesman via brute-force search has what time complexity class?   show
🗑
show 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?   show
🗑
show O(n) - linear  
🗑
show O(log n) - logarithmic  
🗑
this is the sum of cost x frequency for all operations   show
🗑
show machine and compiler; algorithm and input data  
🗑
in principle, accurate ________ models are available   show
🗑
show integer add (2.1 ns), integer multiply (2.4 ns), floating-point multiply (4.2 ns), floating-point add (4.6 ns), integer divide (5.4 ns), floating-point divide (13.5 ns), sine (91.3 ns), arctan (129.0 ns)  
🗑
show number of repetitions  
🗑
this is the operation that contributes the most towards the running time of the algorithm   show
🗑
show T(n) = C_op * C(n) where C_op is the execution time of the basic operation (cost) and C(n) is how many times it is executed  
🗑
different basic operations may cost ________   show
🗑
searching for key in a list of n items will have what input size measure and basic operation?   show
🗑
multiplication of two matrices will have what input size measure and basic operation?   show
🗑
show input size: n of digits in binary representation of n', basic operation: division  
🗑
a typical graph problem will have what input size measure and basic operation?   show
🗑
show empirical  
🗑
enumerate all 3 cases in analyzing efficiency   show
🗑
show worst case - C_worst(n)  
🗑
this case is the minimum over inputs of size n   show
🗑
show average case - C_avg(n)  
🗑
this case is the number of times the basic operation will be executed on typical input   show
🗑
show no  
🗑
show average case  
🗑
show uniform  
🗑
what is the worst, best, and average cases of a sequential search?   show
🗑
enumerate the 3 types of formulas for basic operation's count   show
🗑
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   show
🗑
show 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   show
🗑
enumerate the 3 types of asymptotic order of growth   show
🗑
show asymptotic  
🗑
this notation is a class of functions that grow no faster than g(n)   show
🗑
this notation is a class of functions that grow at the same rate as g(n)   show
🗑
show Omega(g(n)) - Big Omega  
🗑
show asymptotic order of growth (theta, oh, omega)  
🗑
this notation encloses the function from above and below   show
🗑
show theta notation  
🗑
this notation is used for analyzing the average case complexity of an algorithm   show
🗑
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   show
🗑
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 __________   show
🗑
this notation represents the upper bound of the running time of an algorithm   show
🗑
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   show
🗑
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   show
🗑
show omega notation  
🗑
show omega notation  
🗑
show Omega(g(n))  
🗑
for any value of n, the _____ time required by the algorithm is given by Omega(g(n))   show
🗑
show brute force  
🗑
examples of this include computing a^n (a > 0, n is a nonnegative integer), computing n!, multiplying two matrices, and searching for a key of a given value in a list   show
🗑
show T  
🗑
(T/F) one strength of brute-force is its simplicity   show
🗑
(T/F) one strength of brute-force is that it yields reasonable algorithms for some important problems (e.g., matrix mult, sorting, searching, string matching)   show
🗑
(T/F) one weakness of brute-force is its wide applicability   show
🗑
show F  
🗑
(T/F) one weakness of brute-force is that it yields reasonable algorithms for some important problems (e.g., matrix mult, sorting, searching, string matching)   show
🗑
show F  
🗑
(T/F) one strength of brute-force is that some brute-force algorithms are unacceptably slow   show
🗑
(T/F) one strength of brute-force is that it is not as constructive as some other design techniques   show
🗑
(T/F) one weakness of brute-force is that it rarely yields efficient algorithms   show
🗑
show T  
🗑
show T  
🗑
(T/F) brute-force is as constructive as some other design techniques   show
🗑
show (1) Selection sort, (2) String matching, (3) Exhaustive search (e.g., traveling salesman, knapsack) (SSE)  
🗑
this algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning   show
🗑
show selection sort  
🗑
enumerate the 2 subarrays maintained by selection sort   show
🗑
in every iteration of this algorithm, the minimum element from the unsorted subarray is picked and moved to the sorted subarray   show
🗑
selection sort algorithm has how many steps?   show
🗑
selection sort has what best time complexity?   show
🗑
selection sort has what worst time complexity?   show
🗑
selection sort has what average time complexity?   show
🗑
selection sort has what space complexity?   show
🗑
show string matching  
🗑
show pattern  
🗑
this is a (longer) string of n characters to search in   show
🗑
this involves finding a substring in the text that matches the pattern   show
🗑
show string matching  
🗑
in string matching, those comparisons between substring and pattern proceed _____ by ______ unless a mismatch is found   show
🗑
whenever a ______ is found in string matching, the remaining character comparisons by that substring are dropped and the next substring can be selected immediately   show
🗑
show 3  
🗑
string matching has what worst time complexity in terms of m and n?   show
🗑
enumerate the 3 steps of brute-force string matching   show
🗑
this is a brute-force solution to a problem involving search for an element with a special property, usually among combinatorial objects such as permutations, combinations, or subsets of a set   show
🗑
show exhaustive search  
🗑
when this ends, it announces the solution(s) found   show
🗑
this is a problem where given n cities with known distances between each pair, find the shortest tour that passes through all the cities exactly once before returning to the starting city   show
🗑
this is a problem where we find the shortest Hamiltonian circuit in a weighted connected graph   show
🗑
show Hamiltonian circuit  
🗑
show 5  
🗑
show nearest neighbor algorithm  
🗑
this approach to TSP involves calculating the penalty of each 0 after reduction (the minimum element of a row + minimum element of a column)   show
🗑
show 7  
🗑
this is a problem where given n items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible   show
🗑
this is a problem where we find the most valuable subset of the items that can fit into the _____   show
🗑
what is the worst time complexity of the knapsack problem?   show
🗑
in knapsack, each subset can be represented by a _______   show
🗑
in this approach, the problem in hand is divided into smaller sub-problems and then each problem is solved independently   show
🗑
in this approach, when we keep on dividing the subproblems into even smaller sub-problems, we may eventually reach a stage where no more division is possible   show
🗑
in this approach, those "atomic" smallest possible sub-problem (fractions) are solved   show
🗑
in this approach, the solution of all sub-problems is finally merged in order to obtain the solution of an original problem   show
🗑
show (1) Divide/Break, (2) Conquer/Solve, (3) Merge/Combine (DCM/BSC)  
🗑
show Divide/Break  
🗑
this step in the divide and conquer approach takes a recursive approach to divide the problem until no sub-problem is further divisible   show
🗑
at this step in the divide and conquer approach, sub-problems become atomic in nature but still represent some part of the actual problem   show
🗑
at this step in the divide and conquer approach, sub-problems should represent a part of the original problem   show
🗑
show Conquer/Solve  
🗑
at this step in the divide and conquer approach, the problems are considered 'solved' on their own   show
🗑
at this step in the divide and conquer approach, when the smaller sub-problems are solved, this stage recursively combines them until they formulate a solution of the original problem   show
🗑
show Merge/Combine  
🗑
show (1) Merge Sort, (2) Quick Sort, (3) Binary Search, (4) Strassen's Matrix Multiplication, (5) Closest Pair of Points  
🗑
this algorithm is a sorting technique which first divides the array into equal halves and then combines them in a sorted manner   show
🗑
show O(n log n)  
🗑
show O(n log n)  
🗑
merge sort has what best-case time complexity?   show
🗑
show O(n)  
🗑
merge sort has how many steps?   show
🗑
show (1) if only one element, return, (2) divide recursively into 2 halves until atomic, (3) merge the smaller lists in sorted order  
🗑
merge sort usually utilizes two main functions, what are they?   show
🗑
this algorithm is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays   show
🗑
in this algorithm, a large array is partitioned into two arrays, one of which holds values smaller than the specified value, say pivot, based on which the partition is made, and another array holds values greater than the pivot value   show
🗑
show quick sort  
🗑
show quick sort  
🗑
in quicksort, this element is the basis of the partitioning algorithm, where every element to the left of it is less than it and every element to the right of it is greater than it   show
🗑
quick sort has what worst-case time complexity?   show
🗑
quick sort has what average-case time complexity?   show
🗑
quick sort has what best-case time complexity?   show
🗑
show O(log n)  
🗑
the quick sort pivot algorithm has how many steps?   show
🗑
the pivot algorithm normally used takes the ____ element as the pivot   show
🗑
show 4  
🗑
enumerate the 4 steps of quick sort   show
🗑
this algorithm is a fast search algorithm with run-time complexity of O(log n)   show
🗑
this searching algorithm works on the principle of divide and conquer   show
🗑
show binary search  
🗑
show binary search  
🗑
show index of the item  
🗑
in binary search, if the middle item is greater than the item, then the item is searched in the subarray to the ____ of the middle item   show
🗑
in binary search, if the middle item is less than the item, then the item is searched in the subarray to the ____ of the middle item   show
🗑
binary search continues until the size of the subarray reduces to ____   show
🗑
what is the formula for finding the mid index in binary search?   show
🗑
show -1  
🗑
show low = mid + 1  
🗑
show high = mid - 1  
🗑
this algorithm halves the searchable items and thus reduces the count of comparisons to be made   show
🗑
show strassen's matrix multiplication  
🗑
this algorithm is named after Volker Strassen, who discovered it in 1969   show
🗑
who discovered Strassen's matrix multiplication?   show
🗑
what year was Strassen's matrix multiplication discovered?   show
🗑
show strassen's matrix multiplication  
🗑
strassen's algorithm would be ____ than the fastest known algorithms for extremely large matrices   show
🗑
show strassen's matrix multiplication  
🗑
the naive matrix multiplication is so called __________ matrix multiplication   show
🗑
Volker Strassen proved that the general matrix multiplication algorithm wasn't optimal at time complexity of ____   show
🗑
show strassen's matrix multiplication  
🗑
show Coppersmith-Winograd  
🗑
show multiplications; additions  
🗑
show eight; four  
🗑
show seven; eighteen  
🗑
show ae + bg  
🗑
show af + bh  
🗑
say we multiply two 2x2 matrices A and B, where each cell is a submatrix of size n/2 X n/2, and each submatrix is labeled a-d for A and e-h for B, the resulting cell in the BOTTOM-LEFT of the resulting matrix C would be what?   show
🗑
say we multiply two 2x2 matrices A and B, where each cell is a submatrix of size n/2 X n/2, and each submatrix is labeled a-d for A and e-h for B, the resulting cell in the BOTTOM-RIGHT of the resulting matrix C would be what?   show
🗑
show O(n^2)  
🗑
the idea of this method is to reduce the number of recursive calls from 8 to 7   show
🗑
show p1 = a(f - h)  
🗑
show p2 = (a + b)h  
🗑
show p3 = (c + d)e  
🗑
say we multiply two 2x2 matrices A and B using strassen's method, where each cell is a submatrix of size n/2 X n/2, and each submatrix is labeled a-d for A and e-h for B, how will we get p4?   show
🗑
say we multiply two 2x2 matrices A and B using strassen's method, where each cell is a submatrix of size n/2 X n/2, and each submatrix is labeled a-d for A and e-h for B, how will we get p5?   show
🗑
show p6 = (b - d)(g + h)  
🗑
show p7 = (a - c)(e + f)  
🗑
show p5 + p4 - p2 + p6  
🗑
show p1 + p2  
🗑
say we multiply two 2x2 matrices A and B using strassen's method, where each cell is a submatrix of size n/2 X n/2, how will we get the BOTTOM-LEFT cell of the resulting matrix C after computing p1-p7?   show
🗑
say we multiply two 2x2 matrices A and B using strassen's method, where each cell is a submatrix of size n/2 X n/2, how will we get the BOTTOM-RIGHT cell of the resulting matrix C after computing p1-p7?   show
🗑
generally, this method is not preferred for practical applications because the constants used are high and the naive method works better for small matrices   show
🗑
show sparse  
🗑
in strassen's, the submatrices in recursion take extra _____   show
🗑
show larger  
🗑
show strassen's matrix multiplication  
🗑
using the master theorem with T(n) = _____________, we still get a runtime of O(n^3)   show
🗑
show O(n^2.8074)  
🗑
strassen's matrix multiplication has what best-case time complexity?   show
🗑
strassen's matrix multiplication has what space complexity?   show
🗑
this problem is a problem of computational geometry   show
🗑
show closest pair of points  
🗑
show closest pair of points  
🗑
a naive algorithm of finding distances between all pairs of points in a space of dimension d and selecting the minimum requires what time complexity?   show
🗑
show O(n log n)  
🗑
in the algebraic decision tree model of computation, the O(n log n) algorithm is optimal, by a reduction from the element __________ problem   show
🗑
show O(n log log n)  
🗑
in closest-pair, if we allow ________ to be used together with the floor function, the problem can be solved in O(n) time   show
🗑
in closest-pair, as a pre-processing step, the input array is sorted according to what?   show
🗑
in closest-pair, time complexity can be improved to O(n log n) by optimizing the _______ step   show
🗑
closest pair of points has what worst-case time complexity?   show
🗑
closest pair of points has how many steps?   show
🗑


   

Review the information in the table. When you are ready to quiz yourself you can hide individual columns or the entire table. Then you can click on the empty cells to reveal the answer. Try to recall what will be displayed before clicking the empty cell.
 
To hide a column, click on the column name.
 
To hide the entire table, click on the "Hide All" button.
 
You may also shuffle the rows of the table by clicking on the "Shuffle" button.
 
Or sort by any of the columns using the down arrow next to any column heading.
If you know all the data on any row, you can temporarily remove it by tapping the trash can to the right of the row.

 
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
Created by: user-1791948