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 🗑
|
||||
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.
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