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!
|
|
||||
|---|---|---|---|---|---|
| a sequence of unambiguous instructions for solving a problem | show 🗑
|
||||
| this is the process of obtaining a required output for any legitimate input in a finite amount of time | show 🗑
|
||||
| show | algorithm
🗑
|
||||
| it is a sequence of computational steps that transform the input into the output | show 🗑
|
||||
| enumerate the 9 steps involved in solving computational problems | show 🗑
|
||||
| in this step, the programmer must be able to understand fully the problem statement before starting to work on the solution | show 🗑
|
||||
| show | the PROBLEM itself, the METHOD of solving, the PURPOSE (PMP)
🗑
|
||||
| show | the PROBLEM itself
🗑
|
||||
| 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 🗑
|
||||
| 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 | show 🗑
|
||||
| show | iterative
🗑
|
||||
| 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
🗑
|
||||
| in this step, all algorithms must satisfy a criteria involving input, output, definiteness, finiteness, and effectiveness | show 🗑
|
||||
| this criteria specifies that an algorithm has zero or more of it, taken from a specified set of objects | show 🗑
|
||||
| show | output
🗑
|
||||
| enumerate the 5 criteria that all algorithms must satisfy during the specifications stage | show 🗑
|
||||
| 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 🗑
|
||||
| show | Checking the correctness of an algorithm
🗑
|
||||
| show | correctness
🗑
|
||||
| show | functional correctness
🗑
|
||||
| _____ correctness requires that if an answer is returned it will be correct, and ______ correctness additionally requires that the algorithm terminates | show 🗑
|
||||
| this is a type of mathematical proof that plays a critical role in formal verification because total correctness of an algorithm depends on termination | show 🗑
|
||||
| since there is no general solution to the halting problem, a ___________ assertion may lie much deeper | show 🗑
|
||||
| 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 | show 🗑
|
||||
| show | Analysis of an algorithm
🗑
|
||||
| show | efficiency; time complexity; space complexity
🗑
|
||||
| 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 🗑
|
||||
| in order to understand how to _______ an Algorithm, we first need to conceptually understand what an Algorithm is | show 🗑
|
||||
| this does not equal expressing code, that idea ignores and neglects the entire idea of writing code to solve a problem | show 🗑
|
||||
| show | Establish the rules of a problem, Explore the problem space, Write the test and verify the solution, Specify a plan that should solve the problem and elaborate the plan into steps, Translate each step into a line of code (EEWST)
🗑
|
||||
| show | Program testing
🗑
|
||||
| show | program testing
🗑
|
||||
| a good ____ is one that has a high probability of finding an error | show 🗑
|
||||
| show | errors
🗑
|
||||
| show | no
🗑
|
||||
| in this step, the team keeps track of all aspects of an application and it improves on the quality of a software product | show 🗑
|
||||
| its main focuses are development, maintenance and knowledge transfer to other developers | show 🗑
|
||||
| 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 | show 🗑
|
||||
| show | documentation
🗑
|
||||
| show | Unique name, Defined inputs/outputs, Definiteness (well-ordered with unambiguous operations), Finiteness (halts in a finite amount of time)
🗑
|
||||
| show | 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 | show 🗑
|
||||
| show | algorithm
🗑
|
||||
| show | algorithm
🗑
|
||||
| this is an informal and (often rudimentary) human readable description of an algorithm leaving many granular details of it | show 🗑
|
||||
| show | pseudocode
🗑
|
||||
| show | Designing algorithms, Expressing algorithms, Proving correctness, Efficiency/complexity analysis (Theoretical & Empirical analyses), Optimality (DEPEO)
🗑
|
||||
| show | the core of computer science
🗑
|
||||
| what is the practical importance of studying algorithms? | show 🗑
|
||||
| he is the 9th century mathematician | show 🗑
|
||||
| whose algorithm is known for finding the GCD? | show 🗑
|
||||
| this is an ancient algorithm for finding all prime numbers up to any given limit | show 🗑
|
||||
| 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 🗑
|
||||
| a searching algorithm where you go through whole data sequentially until you find the match | show 🗑
|
||||
| show | binary search
🗑
|
||||
| show | binary search
🗑
|
||||
| show | sequential search
🗑
|
||||
| show | binary search tree
🗑
|
||||
| show | string processing
🗑
|
||||
| this is a sequence of characters from an alphabet | show 🗑
|
||||
| this is a type of string consisting of letters, numbers, and special characters | show 🗑
|
||||
| show | 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 | show 🗑
|
||||
| a graph is a collection of points called _____, some of which are connected by line segments called _____ | show 🗑
|
||||
| show | graphs
🗑
|
||||
| enumerate the 3 types of graph algorithms | show 🗑
|
||||
| show | List, Stack, Queue, Priority Queue / Heap, Graph, Tree / Binary Tree, Set / Dictionary (LSQPGTS)
🗑
|
||||
| show | Array, Linked List, String (ALS)
🗑
|
||||
| show | array
🗑
|
||||
| show | linked list
🗑
|
||||
| enumerate the 2 types of linked list and their difference | show 🗑
|
||||
| show | array
🗑
|
||||
| a list that permits access by following links | show 🗑
|
||||
| a(n) _______ has fixed length and needs preliminary reservation of memory while a(n) ______ has dynamic length and arbitrary memory locations | show 🗑
|
||||
| this data structure's insertion/deletion can be done only at the top | show 🗑
|
||||
| this data structure's insertion is done from the back and deletion from the front | show 🗑
|
||||
| show | enqueue; dequeue
🗑
|
||||
| the ____ data structure is LIFO/FILO while ____ is FIFO/LILO | show 🗑
|
||||
| inserting in a stack is called _______ and removing from it is called _______ | show 🗑
|
||||
| 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 🗑
|
||||
| show | complete graph
🗑
|
||||
| show | 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 | show 🗑
|
||||
| show | undirected
🗑
|
||||
| show | adjacency linked lists
🗑
|
||||
| show | Adjacency Matrix, Adjacency Linked Lists (AM-ALL)
🗑
|
||||
| show | 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 | show 🗑
|
||||
| a path where all edges are distinct | show 🗑
|
||||
| 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 🗑
|
||||
| show | cycle
🗑
|
||||
| show | acyclic graph
🗑
|
||||
| show | directed acyclic graph (DAG)
🗑
|
||||
| this is what you call a connected acyclic graph | show 🗑
|
||||
| show | forest
🗑
|
||||
| for every two vertices in a ____ there always exists exactly one simple path from one of these vertices to the other | show 🗑
|
||||
| show | rooted
🗑
|
||||
| for any vertex v in a tree T, all the vertices on the simple path from the root to that vertex are called ________ | show 🗑
|
||||
| all the vertices for which a vertex v is an ancestor are said to be _______ of v | show 🗑
|
||||
| show | parent; child
🗑
|
||||
| show | siblings
🗑
|
||||
| a vertex without children is called a ____ | show 🗑
|
||||
| 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 🗑
|
||||
| show | height of a tree
🗑
|
||||
| show | ordered tree
🗑
|
||||
| show | 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 | show 🗑
|
||||
| a process in which a function calls itself directly or indirectly | show 🗑
|
||||
| show | recursion
🗑
|
||||
| show | recursion
🗑
|
||||
| in recursion, this should be defined to avoid infinite loops | show 🗑
|
||||
| show | 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 | show 🗑
|
||||
| ____ 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
🗑
|
||||
| show | recursion (too much will cause stack overflow)
🗑
|
||||
| show | iteration
🗑
|
||||
| show | infinite recursion
🗑
|
||||
| show | crash it
🗑
|
||||
| show | base case
🗑
|
||||
| show | maintaining the stack
🗑
|
||||
| show | smaller
🗑
|
||||
| if we compare recursion implementation against recursion it is at least _____ slower | show 🗑
|
||||
| enumerate the 4 types of recursion | show 🗑
|
||||
| show | direct
🗑
|
||||
| show | indirect
🗑
|
||||
| show | 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) | show 🗑
|
||||
| the efficiency of an algorithm can be in terms of ___ or ___ | show 🗑
|
||||
| checking whether the algorithm is efficient or not, means ______ the algorithm | show 🗑
|
||||
| show | analysis framework
🗑
|
||||
| the _______ of an algorithm can be decided by measuring the performance of an algorithm | show 🗑
|
||||
| this is the process of investigation of an algorithm's efficiency respect to two resources: running time and memory space | show 🗑
|
||||
| enumerate the 4 reasons for selecting the criteria of running time and memory space in algorithm analysis | show 🗑
|
||||
| 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
🗑
|
||||
| show | 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 | show 🗑
|
||||
| the analysis of _______ and ________ is the major force that drives the design of solutions | show 🗑
|
||||
| show | pick the most efficient one
🗑
|
||||
| show | analyze algorithms
🗑
|
||||
| this is the process of analyzing the cost of the algorithm | show 🗑
|
||||
| show | time & space (memory)
🗑
|
||||
| show | time
🗑
|
||||
| show | space
🗑
|
||||
| show | space + time
🗑
|
||||
| show | input; hardware
🗑
|
||||
| enumerate the 4 issues in the analysis of algorithms | show 🗑
|
||||
| enumerate the 2 approaches in the analysis of algorithms | show 🗑
|
||||
| enumerate the 4 reasons to analyze algorithms | show 🗑
|
||||
| show | to avoid performance bugs
🗑
|
||||
| client gets ____ performance because programmer did not understand performance characteristics | show 🗑
|
||||
| the scientific method applied to algorithm analysis is a framework for __________ and __________ | show 🗑
|
||||
| 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 🗑
|
||||
| who created the analytical engine, the first programmable device? | show 🗑
|
||||
| two ways of timing a program | show 🗑
|
||||
| show | empirical
🗑
|
||||
| show | 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) | show 🗑
|
||||
| show | system independent (algorithm, input), system dependent (hardware, software, system)
🗑
|
||||
| show | system independent and dependent effects
🗑
|
||||
| show | system independent effects
🗑
|
||||
| show | system independent effects
🗑
|
||||
| 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 🗑
|
||||
| show | space complexity
🗑
|
||||
| enumerate the 3 things for any algorithm memory may be used for | show 🗑
|
||||
| show | auxiliary space
🗑
|
||||
| space complexity = ______ space + ______ space | show 🗑
|
||||
| enumerate the 3 reasons algorithms use memory space while executing | show 🗑
|
||||
| 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
🗑
|
||||
| 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 | show 🗑
|
||||
| show | 1 byte
🗑
|
||||
| show | 1 byte
🗑
|
||||
| show | 2 bytes
🗑
|
||||
| show | 2 bytes
🗑
|
||||
| show | 4 bytes
🗑
|
||||
| __int32 and (unsigned) int types have what size in bytes? | show 🗑
|
||||
| show | 8 bytes
🗑
|
||||
| show | 8 bytes
🗑
|
||||
| to compute the space complexity, we use two factors: ______ and ______ | show 🗑
|
||||
| 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)
🗑
|
||||
| if the space requirement is fixed and is a constant, it is called __________ | show 🗑
|
||||
| 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 🗑
|
||||
| show | minimum
🗑
|
||||
| this is the amount of time required by an algorithm to run for completion | show 🗑
|
||||
| show | frequency count
🗑
|
||||
| show | multiuser
🗑
|
||||
| enumerate the 4 elements to consider in analyzing time complexity | show 🗑
|
||||
| show | model computer
🗑
|
||||
| enumerate the 9 time complexity classes and their big O notations | show 🗑
|
||||
| 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 🗑
|
||||
| show | linearithmic/quasilinear
🗑
|
||||
| show | quadratic
🗑
|
||||
| naive multiplication of two nxn matrices has what time complexity class? | show 🗑
|
||||
| show | polynomial
🗑
|
||||
| show | exponential
🗑
|
||||
| show | factorial
🗑
|
||||
| show | O(n^3) - cubic
🗑
|
||||
| show | 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? | show 🗑
|
||||
| an algorithm's time complexity is defined as T = 3 log_8 (n) + log_2 (log_2 (log_2 (n))), what is it in big O notation and its TC class? | show 🗑
|
||||
| this is the sum of cost x frequency for all operations | show 🗑
|
||||
| cost depends on ______ and _______ while frequency depends on _______ and ______ | show 🗑
|
||||
| in principle, accurate ________ models are available | show 🗑
|
||||
| enumerate all 8 basic operations and their costs in ns (assuming it is running OS X on Macbook Pro 2.2 Ghz with 2GB RAM) | show 🗑
|
||||
| time efficiency is analyzed by determining the ________ of the basic operation as a function of input size | show 🗑
|
||||
| this is the operation that contributes the most towards the running time of the algorithm | show 🗑
|
||||
| what is the formula for theoretical analysis of time efficiency | show 🗑
|
||||
| different basic operations may cost ________ | show 🗑
|
||||
| show | input size: number of list's items (n), basic operation: key comparison
🗑
|
||||
| show | input size: matrix dimensions or total n of elements, basic operation: multiplication of two numbers
🗑
|
||||
| checking the primality of a given integer n will have what input size measure and basic operation? | show 🗑
|
||||
| a typical graph problem will have what input size measure and basic operation? | show 🗑
|
||||
| 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 | show 🗑
|
||||
| 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 🗑
|
||||
| this case is the "average" over inputs of size n | show 🗑
|
||||
| this case is the number of times the basic operation will be executed on typical input | show 🗑
|
||||
| is average case the average of the worse and best cases? | show 🗑
|
||||
| this case is the expected number of basic operations considered as a random variable under some assumption about the probability distribution of all inputs | show 🗑
|
||||
| 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
🗑
|
||||
| show | order of growth
🗑
|
||||
| show | Big Theta, Big Oh, Big Omega (TOO)
🗑
|
||||
| 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 🗑
|
||||
| this notation is a class of functions that grow at least as fast as g(n) | show 🗑
|
||||
| these are ways of comparing functions that ignores constant factors and small input sizes | show 🗑
|
||||
| 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 🗑
|
||||
| show | 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 __________ | 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 🗑
|
||||
| show | big-o notation
🗑
|
||||
| this notation represents the lower bound of the running time of an algorithm | show 🗑
|
||||
| this notation provides the best case complexity of an algorithm | show 🗑
|
||||
| show | Omega(g(n))
🗑
|
||||
| for any value of n, the _____ time required by the algorithm is given by Omega(g(n)) | show 🗑
|
||||
| this is a straightforward approach, usually based directly on the problem's statement and definitions of the concepts involved | show 🗑
|
||||
| show | brute force
🗑
|
||||
| (T/F) one strength of brute-force is its wide applicability | show 🗑
|
||||
| show | T
🗑
|
||||
| show | T
🗑
|
||||
| show | F
🗑
|
||||
| show | F
🗑
|
||||
| show | F
🗑
|
||||
| (T/F) one strength of brute-force is that it rarely yields efficient algorithms | show 🗑
|
||||
| show | F
🗑
|
||||
| (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
🗑
|
||||
| (T/F) one weakness of brute-force is that it is not as constructive as some other design techniques | show 🗑
|
||||
| (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 🗑
|
||||
| show | selection sort
🗑
|
||||
| show | 5
🗑
|
||||
| show | O(n^2)
🗑
|
||||
| show | O(n^2)
🗑
|
||||
| selection sort has what average time complexity? | show 🗑
|
||||
| show | O(1)
🗑
|
||||
| this algorithm involves finding a pattern within a text | show 🗑
|
||||
| show | pattern
🗑
|
||||
| this is a (longer) string of n characters to search in | show 🗑
|
||||
| show | string matching
🗑
|
||||
| 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 🗑
|
||||
| string matching has how many steps? | show 🗑
|
||||
| string matching has what worst time complexity in terms of m and n? | show 🗑
|
||||
| enumerate the 3 steps of brute-force string matching | show 🗑
|
||||
| show | exhaustive search
🗑
|
||||
| show | exhaustive search
🗑
|
||||
| show | exhaustive search
🗑
|
||||
| show | traveling salesman problem
🗑
|
||||
| show | traveling salesman problem
🗑
|
||||
| this is a cycle that visits every vertex exactly once and returns to the starting vertex | show 🗑
|
||||
| how many steps does the nearest neighbor algorithm for TSP have? | show 🗑
|
||||
| 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 🗑
|
||||
| how many steps does the branch and bound (penalty) method for TSP have? | show 🗑
|
||||
| show | knapsack problem
🗑
|
||||
| show | knapsack problem
🗑
|
||||
| what is the worst time complexity of the knapsack problem? | show 🗑
|
||||
| in knapsack, each subset can be represented by a _______ | show 🗑
|
||||
| show | divide and conquer
🗑
|
||||
| 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 🗑
|
||||
| show | divide and conquer
🗑
|
||||
| in this approach, the solution of all sub-problems is finally merged in order to obtain the solution of an original problem | show 🗑
|
||||
| enumerate the 3 steps of the divide and conquer approach | show 🗑
|
||||
| show | Divide/Break
🗑
|
||||
| show | Divide/Break
🗑
|
||||
| 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 🗑
|
||||
| show | Divide/Break
🗑
|
||||
| show | Conquer/Solve
🗑
|
||||
| at this step in the divide and conquer approach, the problems are considered 'solved' on their own | show 🗑
|
||||
| show | Merge/Combine
🗑
|
||||
| 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)
🗑
|
||||
| show | O(n log n)
🗑
|
||||
| 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
🗑
|
||||
| show | divide (which divides the array recursively into two halves) and merge (which merges the two halves in a sorted manner)
🗑
|
||||
| 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
🗑
|
||||
| show | pivot
🗑
|
||||
| show | O(n^2)
🗑
|
||||
| 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 🗑
|
||||
| show | last (highest index)
🗑
|
||||
| the quick sort algorithm itself has how many steps? | show 🗑
|
||||
| enumerate the 4 steps of quick sort | show 🗑
|
||||
| show | binary search
🗑
|
||||
| show | binary search
🗑
|
||||
| show | binary search
🗑
|
||||
| show | binary search
🗑
|
||||
| in binary search, if a match occurs, the ______ is returned | show 🗑
|
||||
| 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 🗑
|
||||
| show | right
🗑
|
||||
| show | zero
🗑
|
||||
| what is the formula for finding the mid index in binary search? | show 🗑
|
||||
| show | -1
🗑
|
||||
| show | low = mid + 1
🗑
|
||||
| show | high = mid - 1
🗑
|
||||
| show | binary search
🗑
|
||||
| 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 🗑
|
||||
| show | O(n^3)
🗑
|
||||
| show | strassen's matrix multiplication
🗑
|
||||
| a faster approach to matrix multiplication than both naive and strassen's is called the _______ algorithm | show 🗑
|
||||
| show | multiplications; additions
🗑
|
||||
| show | eight; four
🗑
|
||||
| in strassen's algorithm of matrix multiplication, there are ____ multiplications and ____ additions | 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 TOP-LEFT of the resulting matrix C would be what? | show 🗑
|
||||
| show | af + bh
🗑
|
||||
| show | ce + dg
🗑
|
||||
| show | cf + dh
🗑
|
||||
| show | O(n^2)
🗑
|
||||
| show | strassen's matrix multiplication
🗑
|
||||
| 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 p1? | show 🗑
|
||||
| show | p2 = (a + b)h
🗑
|
||||
| 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 p3? | show 🗑
|
||||
| show | p4 = d(g - 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 p5? | 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 p6? | show 🗑
|
||||
| show | p7 = (a - c)(e + f)
🗑
|
||||
| show | p5 + p4 - p2 + p6
🗑
|
||||
| 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 TOP-RIGHT cell of the resulting matrix C after computing p1-p7? | show 🗑
|
||||
| show | p3 + p4
🗑
|
||||
| show | p1 + p5 - p3 - p7
🗑
|
||||
| show | strassen's matrix multiplication
🗑
|
||||
| generally, strassen's method is not preferred because for ______ matrices, there are better methods especially designed for them | show 🗑
|
||||
| show | space
🗑
|
||||
| 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 🗑
|
||||
| show | O(log n)
🗑
|
||||
| this problem is a problem of computational geometry | show 🗑
|
||||
| this is a problem where given n points in metric space, find a pair of points with the smallest distance between them | show 🗑
|
||||
| this problem was among the first geometric problems that were treated at the origins of the systematic study of the computational complexity of geometric algorithms | show 🗑
|
||||
| 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)
🗑
|
||||
| show | uniqueness
🗑
|
||||
| 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 🗑
|
||||
| show | sorting of strips (step 5)
🗑
|
||||
| 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.
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
Normal Size Small Size show me how
Created by:
user-1791948