Help
Options
Question
a sequence of unambiguous instructions for solving a problem
click to flip
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't know
Question
this is the process of obtaining a required output for any legitimate input in a finite amount of time
Remaining cards (434)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
ALGO MIDTERMS
MOD 1-4
| Question | Answer |
|---|---|
| a sequence of unambiguous instructions for solving a problem | algorithm |
| this is the process of obtaining a required output for any legitimate input in a finite amount of time | algorithm |
| this is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output | algorithm |
| it is a sequence of computational steps that transform the input into the output | algorithm |
| enumerate the 9 steps involved in solving computational problems | 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) |
| in this step, the programmer must be able to understand fully the problem statement before starting to work on the solution | Problem definition |
| enumerate the 3 elements of problem statements | the PROBLEM itself, the METHOD of solving, the PURPOSE (PMP) |
| this element of problem statement is stated clearly and with enough contextual detail to establish its importance | the PROBLEM itself |
| this element of problem statement is often stated as a claim or a working thesis | the METHOD of solving the problem |
| this element of problem statement is a statement of objective and scope of the document the writer is preparing | the PURPOSE |
| in this step, the definition of model objectives, conceptualization of the problem, translation into a computational model, and model testing, revision, and application is performed | Development of a model (Model Development) |
| model development is an ________ process, in which many models are derived, tested and built upon until a model fitting the desired criteria is built | iterative |
| where should subsequent modelling work may need to begin the search given that a previous original model has already been built? | at the same place as the original model building began |
| subsequent modelling work may need to begin the search at the same place as the original model building began, rather than where it finished. Why is that? | 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 | Specification of an algorithm |
| this criteria specifies that an algorithm has zero or more of it, taken from a specified set of objects | input |
| this criteria specifies that an algorithm has one or more of it, which have a specified relation to another criteria involving a subset of objects | output |
| enumerate the 5 criteria that all algorithms must satisfy during the specifications stage | 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 | definiteness |
| this criteria specifies that an algorithm must always terminate after a finite number of steps | finiteness |
| this criteria specifies that an algorithm must have all of its operations sufficiently basic that they can be done exactly and in finite length | effectiveness |
| in this step, the algorithm will be examined if it is correct with respect to a specification | Checking the correctness of an algorithm |
| in theoretical computer science, ________ of an algorithm is asserted when it is said that the algorithm is correct with respect to a specification | correctness |
| this refers to the input-output behavior of the algorithm | functional correctness |
| _____ correctness requires that if an answer is returned it will be correct, and ______ correctness additionally requires that the algorithm terminates | partial; total |
| this is a type of mathematical proof that plays a critical role in formal verification because total correctness of an algorithm depends on termination | termination proof |
| since there is no general solution to the halting problem, a ___________ assertion may lie much deeper | total correctness |
| this is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever | the halting problem |
| in this step, the amount of time and space resources required to execute an algorithm is determined | Analysis of an algorithm |
| the _______ or running time of an algorithm is stated as a function relating the input length to the number of steps, known as ___________, or volume of memory, known as ____________ | efficiency; time complexity; space complexity |
| in this step, the efficiency and time/space complexity of an algorithm is determined | Analysis of an algorithm |
| in this step, the degree of correctness and whether it terminates or not is determined | Checking the correctness of an algorithm |
| a series of steps that you expect will arrive at a specific solution | algorithm |
| in this step, we establish the rules of a problem, explore the problem space, write the test and verify solution, specify a plan that should sovle the problem & elaborate it into steps, and translate each step into code | Implementation of an algorithm |
| in order to understand how to _______ an Algorithm, we first need to conceptually understand what an Algorithm is | implement |
| this does not equal expressing code, that idea ignores and neglects the entire idea of writing code to solve a problem | writing a program |
| enumerate the 5 steps in implementing an algorithm | 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) |
| in this step, a program is executed with the intent of finding errors | Program testing |
| this is the process of executing a program with the intent of finding errors | program testing |
| a good ____ is one that has a high probability of finding an error | test |
| program testing cannot show the absence of _____; it can only show if they are present | errors |
| is it impossible to write the tests before the program? | no |
| in this step, the team keeps track of all aspects of an application and it improves on the quality of a software product | Documentation |
| its main focuses are development, maintenance and knowledge transfer to other developers | documentation |
| this will make information easily accessible, provide a limited number of user entry points, help new users learn quickly, simplify the product and help cut support costs | documentation |
| this is usually focused on the following components that make up an application: server environments, business rules, databases/files, troubleshooting, application installation and code deployment | documentation |
| enumerate the 4 main characteristics of algorithm | Unique name, Defined inputs/outputs, Definiteness (well-ordered with unambiguous operations), Finiteness (halts in a finite amount of time) |
| this gives a high-level description of an algorithm without the ambiguity associated with plain text but also without the need to know the syntax of a particular programming language | pseudocode |
| the running time can be estimated in a more general manner by using ________ to represent the algorithm as a set of fundamental operations which can then be counted | pseudocode |
| this is a formal definition with some specific characteristics that describes a process, which could be executed by a Turing-complete computer machine to perform a specific task | algorithm |
| generally, the word "________" can be used to describe any high level task in computer science | algorithm |
| this is an informal and (often rudimentary) human readable description of an algorithm leaving many granular details of it | pseudocode |
| writing a _________ has no restriction of styles and its only objective is to describe the high level steps of algorithm in a much realistic manner in natural language | pseudocode |
| enumerate 5 issues related to algorithms | Designing algorithms, Expressing algorithms, Proving correctness, Efficiency/complexity analysis (Theoretical & Empirical analyses), Optimality (DEPEO) |
| what is the theoretical importance of studying algorithms? | the core of computer science |
| what is the practical importance of studying algorithms? | a practitioner?s toolkit of known algorithms & framework for designing and analyzing algorithms for new problems |
| he is the 9th century mathematician | Muhammad ibn Musa al-Khwarizmi |
| whose algorithm is known for finding the GCD? | Euclid's algorithm |
| this is an ancient algorithm for finding all prime numbers up to any given limit | sieve of eratosthenes |
| find the gcd of 60 and 24 using Euclid's algorithm | gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12 |
| enumerate the 3 steps of Euclid's algorithm | say we're solving for gcd(m, n) and remainder is r, STEP 1: if n = 0, return m else continue, STEP 2: divide m by n and put the remainder to r, STEP 3: assign n as the new m and r as the new n and return to step 1 |
| what does the sieve of erastosthenes do? | it sieves all multiples of noneliminated integers less than n, leaving only a list of prime numbers below n |
| a problem type that involves rearranging the items of a given list in ascending or descending order | sorting |
| algorithms often use sorting as a key _______ | subroutine |
| this is a specially chosen piece of information used to guide sorting (e.g., sort student records by names) | sorting key |
| evaluate sorting algorithm complexity: the number of __________ | key comparisons |
| enumerate the 2 properties of a sorting algorithm | Stability, In place (SI) |
| a property of sorting algorithms which checks if it preserves the relative order of any two equal elements in its input | stability |
| a property of sorting algorithms which checks if it does not require extra memory except possibly for a few memory units | in place |
| a problem type that involves finding a given value in a given set | searching |
| searching is finding a given value, called a ________, in a given set | search key |
| enumerate the 2 examples of searching algorithms | Sequential search, Binary search (SB) |
| a searching algorithm where you go through whole data sequentially until you find the match | sequential search |
| a searching algorithm where at each stage you can divide data into two (bi) parts | binary search |
| a searching algorithm where you don't have to traverse through whole data | binary search |
| a searching algorithm that applies best for unsorted collections of data | sequential search |
| in this, data is not sorted but it is stored in the memory in a tree-like way | binary search tree |
| a problem type where a sequence of characters from an alphabet, called a string, is processed or manipulated | string processing |
| this is a sequence of characters from an alphabet | string |
| this is a type of string consisting of letters, numbers, and special characters | text string |
| this is the process of searching for a given word/pattern in a text | string matching |
| a problem type where we deal with a collection of points called vertices, some of which are connected by line segments called edges | graph problems |
| a graph is a collection of points called _____, some of which are connected by line segments called _____ | vertices; edges |
| modeling WWW, communication networks, and project scheduling use this | graphs |
| enumerate the 3 types of graph algorithms | Graph traversal algorithms (e.g. BFS/DFS), Shortest-path algorithms (e.g. A*, dijkstra), Topological sorting (GST) |
| enumerate the 7 fundamental data structures | List, Stack, Queue, Priority Queue / Heap, Graph, Tree / Binary Tree, Set / Dictionary (LSQPGTS) |
| enumerate the 3 types of list | Array, Linked List, String (ALS) |
| this is a sequence of n items of the same data type that are stored contiguously in computer memory and made accessible by specifying a value of its index | array |
| this is a sequence of zero or more nodes each containing two kinds of information: some data and one or more links called pointers to other nodes | linked list |
| enumerate the 2 types of linked list and their difference | Singly (has next pointer only), Doubly (has next and previous pointers) |
| a list that permits direct access | array |
| a list that permits access by following links | linked list |
| a(n) _______ has fixed length and needs preliminary reservation of memory while a(n) ______ has dynamic length and arbitrary memory locations | array; linked list |
| this data structure's insertion/deletion can be done only at the top | stack |
| this data structure's insertion is done from the back and deletion from the front | queue |
| inserting in a queue is called _______ and removing from it is called _______ | enqueue; dequeue |
| the ____ data structure is LIFO/FILO while ____ is FIFO/LILO | stack; queue |
| inserting in a stack is called _______ and removing from it is called _______ | push; pop |
| this is a data structure for maintaining a set of elements, each associated with a key/priority, with the following operations: finding/deleting the element with the highest priority and inserting a new element | priority queue |
| priority queues are implementing using ___ | heaps |
| scheduling jobs on a shared computer uses what data structure | priority queue |
| a _______ G = <V, E> is defined by a pair of two sets: a finite set V of items called vertices and a set E of vertex pairs called edges | graph |
| enumerate the 2 types of graph and their difference | Undirected (two-way arrows), Directed (digraphs, one-way) |
| a graph in which each pair of distinct vertices is connected by a unique edge | complete graph |
| a graph in which the number of edges is close to the maximum possible for that graph | dense graph |
| this is a n x n boolean matrix if |V| is n, and the element on the ith row and jth column is 1 if there?s an edge from ith vertex to the jth vertex; otherwise 0 | adjacency matrix |
| the adjacency matrix of an _______ graph is symmetric | undirected |
| this is a collection of linked lists, one for each vertex, that contain all the vertices adjacent to the list?s vertex | adjacency linked lists |
| enumerate the 2 ways you can represent a graph in code | Adjacency Matrix, Adjacency Linked Lists (AM-ALL) |
| these are graphs or digraphs with numbers assigned to the edges | weighted graphs |
| a ____ from vertex u to v of a graph G is defined as a sequence of adjacent (connected by an edge) vertices that starts with u and ends with v | path |
| a path where all edges are distinct | simple paths |
| this is the number of edges, or the number of vertices - 1 | path length |
| a graph is said to be ______ if for every pair of its vertices u and v there is a path from u to v | connected |
| this is the maximum connected subgraph of a given graph | connected component |
| this is a simple path of a positive length that starts and ends at the same vertex | cycle |
| this is what you call a graph without cycles | acyclic graph |
| this is what you call a directed graph without cycles | directed acyclic graph (DAG) |
| this is what you call a connected acyclic graph | tree (free tree) |
| a graph that has no cycles but is not necessarily connected | forest |
| for every two vertices in a ____ there always exists exactly one simple path from one of these vertices to the other | tree |
| the unique property of trees makes it possible to select an arbitrary vertex in a free tree and consider it as the root of the so called ____ tree | rooted |
| for any vertex v in a tree T, all the vertices on the simple path from the root to that vertex are called ________ | ancestors |
| all the vertices for which a vertex v is an ancestor are said to be _______ of v | descendants |
| if (u, v) is the last edge of the simple path from the root to vertex v, u is said to be the ___ of v and v is called a ___ of u | parent; child |
| vertices that have the same parent are called ____ | siblings |
| a vertex without children is called a ____ | leaf |
| a vertex v with all its descendants is called the ____ of T rooted at v | subtree |
| this is the length of the simple path from the root to the vertex | depth of a vertex |
| this is the length of the longest simple path from the root to a leaf | height of a tree |
| this is a rooted tree in which all the children of each vertex are ordered | ordered tree |
| this is an ordered tree in which every vertex has no more than two children and each children is designated as either a left child or a right child of its parent | binary tree |
| this is a binary tree where each vertex is assigned a number; a number assigned to each parental vertex is larger than all the numbers in its left subtree and smaller than all the numbers in its right subtree | binary search tree |
| a process in which a function calls itself directly or indirectly | recursion |
| a process which breaks a task into smaller subtasks | recursion |
| a powerful technique that can be used in place of iterations | recursion |
| in recursion, this should be defined to avoid infinite loops | base case |
| ________ is when a statement in a function calls itself repeatedly, while ________ is when a loop repeatedly executes until the controlling condition becomes false | recursion; iteration |
| the primary difference between iteration and recursion is that ______ is a process, always applied to a function and ______ is applied to the set of instructions which we want to get repeatedly executed | recursion; iteration |
| ____ uses repetition structure, while ____ uses selection structure | iteration; recursion |
| this occurs with iteration if the loop condition test never becomes false | infinite loop |
| infinite looping uses ___ cycles repeatedly | CPU |
| an iteration terminates when the loop condition ____ | fails |
| why is iteration faster than recursion? | an iteration does not use the stack |
| who consumes more memory? recursion or iteration? | recursion (too much will cause stack overflow) |
| who makes the code longer? recursion or iteration? | iteration |
| this occurs with recursion if the recursion step does not reduce the problem in a manner that converges on some condition (base case) | infinite recursion |
| what can infinite recursion do to the system? | crash it |
| recursion terminates when a _______ is recognized | base case |
| recursion is usually slower than iteration due to the overhead of _______ | maintaining the stack |
| recursion makes the code length _______ | smaller |
| if we compare recursion implementation against recursion it is at least _____ slower | twice |
| enumerate the 4 types of recursion | Direct recursion, Indirect recursion, Tail recursion, Non-tail recursion (DINT) |
| a function is called _____ recursive if it calls the same function again | direct |
| a function is called _____ recursive if it calls another function and then that function calls the original function directly or indirectly | indirect |
| a function is called _____ recursive if the recursive call is the last thing done by the function (there is no need to keep record of the previous state) | tail |
| a function is called _____ recursive if the recursive call is not the last thing done by the function (after returning back, there is something left to evaluate/do) | non-tail |
| the efficiency of an algorithm can be in terms of ___ or ___ | time or space |
| checking whether the algorithm is efficient or not, means ______ the algorithm | analyzing |
| there is a systematic approach that has to be applied for analyzing any given algorithm; and this approach is modelled by a framework called _____________ | analysis framework |
| the _______ of an algorithm can be decided by measuring the performance of an algorithm | efficiency |
| this is the process of investigation of an algorithm's efficiency respect to two resources: running time and memory space | analysis of algorithm |
| enumerate the 4 reasons for selecting the criteria of running time and memory space in algorithm analysis | Simplicity, Generality, Speed, Memory (SGSM) |
| in algorithm analysis, this indicates how fast an algorithm runs | time efficiency / time complexity |
| in algorithm analysis, this is the amount of memory units required by the algorithm including the memory needed for the i/p & o/p | space efficiency / space complexity |
| this describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions | big O notation |
| the __________ of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem | time complexity |
| when time complexity is expressed using big O notation, it is said to be described _______, i.e., as the input size goes to infinity | asymptotically |
| the analysis of _______ and ________ is the major force that drives the design of solutions | algorithms and data structure |
| if there are many solutions to a problem...? | pick the most efficient one |
| how to compare various algorithms? | analyze algorithms |
| this is the process of analyzing the cost of the algorithm | algorithm analysis |
| cost, in terms of algorithm analysis, asks how much ____ does the algorithm require | time & space (memory) |
| the primary efficiency measure for an algorithm is ____ | time |
| all concepts discussed for time analysis also apply to ____ analysis | space |
| cost = ____ + ____ | space + time |
| the running time of an algorithm increases with ____ size and depends on ________ | input; hardware |
| enumerate the 4 issues in the analysis of algorithms | Correctness, Time efficiency, Space efficiency, Optimality (COST) |
| enumerate the 2 approaches in the analysis of algorithms | Theoretical analysis, Empirical analysis (TE) |
| enumerate the 4 reasons to analyze algorithms | Predict performance, Compare algorithms, Provide guarantees, Understand theoretical basis (PCPU) |
| what is the primary practical reason of analyzing algorithms | to avoid performance bugs |
| client gets ____ performance because programmer did not understand performance characteristics | poor |
| the scientific method applied to algorithm analysis is a framework for __________ and __________ | predicting performance and comparing algorithms |
| enumerate the 5 scientific methods applied to algorithm analysis | 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 | experiments must be REPRODUCIBLE, hypothesis must be FALSIFIABLE |
| who created the analytical engine, the first programmable device? | charles babbage |
| two ways of timing a program | manual and automatic |
| an ________ analysis of an algorithm involves running the program for various input sizes and measuring the running time (often in ms) | empirical |
| in data analysis, this is a plot that has the running time T(N) as y-axis and the input size N as x-axis | standard plot |
| in data analysis, this is a plot of the log of the running time log(T(N)) vs. log of the input size log(N) | log-log plot |
| experimental algorithmics analyzes two types of system effects, what are they? | system independent (algorithm, input), system dependent (hardware, software, system) |
| in power law, these effects determine constant a | system independent and dependent effects |
| in power law, these effects determine constant b | system independent effects |
| a type of system effects that deals with the algorithm itself and the input data | 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) | system dependent effects |
| this is the amount of memory required by an algorithm (including the input values) to run | space complexity |
| this details how much memory, in the worst case, is needed at any point in the algorithm | space complexity |
| enumerate the 3 things for any algorithm memory may be used for | Variables (const/temp values), Program instruction, Execution (VPE) |
| this is the extra space or the temporary space used by the algorithm during its execution | auxiliary space |
| space complexity = ______ space + ______ space | auxiliary space + input space |
| enumerate the 3 reasons algorithms use memory space while executing | Instruction space, Environmental stack, Data space (IED) |
| this is the amount of memory used to save the compiled version of instructions | instruction space |
| this memory is used in situations where sometimes an algorithm (function) may be called inside another algorithm (function) | environmental stack |
| this is used when the current variables in a function is pushed onto the system stack because an inner function is called inside it | environmental stack |
| this is the amount of space used by the variables and constants | data space |
| while calculating the space complexity, we only consider the ______ and we neglect the ______ and ______ | data space; instruction space and environmental stack |
| for calculating the ____________, we need to know the value of memory used by different type of datatype variables, which generally varies for different operating systems, but the method for calculating it remains the same | space complexity |
| char and unsigned/signed char types have what size in bytes? | 1 byte |
| bool and __int8 types have what size in bytes? | 1 byte |
| __int16 and (unsigned) short types have what size in bytes? | 2 bytes |
| wchar_t and __wchar_t types have what size in bytes? | 2 bytes |
| float and (unsigned) long types have what size in bytes? | 4 bytes |
| __int32 and (unsigned) int types have what size in bytes? | 4 bytes |
| (long) double and long long types have what size in bytes? | 8 bytes |
| __int64 types have what size in bytes? | 8 bytes |
| to compute the space complexity, we use two factors: ______ and ______ | constant and instance characteristic |
| S(p) = C + Sp, where C (constant) is the space taken by _____ and Sp is the space dependent upon _____ | instruction, variable and identifiers; instance characteristic |
| this is a (typically numeric) measure of the properties of the input data that has a bearing on performance | instance characteristic |
| in the code { int z = a + b + c; return z; }, how many bytes is the total memory requirement? | variables a, b, c, and z are all integer types, hence they will take 4 bytes each, with an addition of 4 more bytes for the returned value totaling to 20 bytes (4 * 4 + 4 = 20) |
| if the space requirement is fixed and is a constant, it is called __________ | constant space complexity |
| in the code { int x = 0; for (int i = 0; i < n; i++) { x = x + a[i]; } return x; }, how many bytes is the total memory requirement? | 4 * n bytes is required for the input array (a[n]), 4 bytes each for each variable (x, n, i, return value), hence the total memory is 4n + 16 which increases linearly as n increases |
| if the space requirement increases linearly with input, it is called _________ | linear space complexity |
| we should always focus on writing algorithm code in such a way that we keep the space complexity _______ | minimum |
| this is the amount of time required by an algorithm to run for completion | time complexity |
| this is a count denoting number of times of execution of a statement | frequency count |
| in _______ system, executing time depends on many factors such as system load, number of other programs running, instruction set used, and speed of hardware | multiuser |
| enumerate the 4 elements to consider in analyzing time complexity | Single or multiprocessor?, Read/write speed to memory, 32 or 64 bit?, Input (SIR-36) |
| a __________ has a single processor, 32 bit, sequential, 1 unit time for arithmetic/logical operations, and 1 unit time for assignment/return operations | model computer |
| enumerate the 9 time complexity classes and their big O notations | 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? | constant |
| binary search has what time complexity class? | logarithmic |
| finding the smallest/largest item in an unsorted array has what time complexity class? | linear |
| fast fourier transform has what time complexity class? | linearithmic/quasilinear |
| bubble sort has what time complexity class? | quadratic |
| naive multiplication of two nxn matrices has what time complexity class? | cubic |
| AKS primality test has what time complexity class? | polynomial |
| solving matrix chain multiplication via brute-force search has what time complexity class? | exponential |
| solving the traveling salesman via brute-force search has what time complexity class? | factorial |
| an algorithm's time complexity is defined as T = 4n^3 + 3n^2 + n + 14, what is it in big O notation and its TC class? | O(n^3) - cubic |
| an algorithm's time complexity is defined as T = 16n + n log(n^3) + 2, what is it in big O notation and its TC class? | O(n log n) - linearithmic/quasilinear |
| an algorithm's time complexity is defined as T = log(n + 5) + 3n + 90, what is it in big O notation and its TC class? | O(n) - linear |
| 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? | O(log n) - logarithmic |
| this is the sum of cost x frequency for all operations | total running time |
| cost depends on ______ and _______ while frequency depends on _______ and ______ | machine and compiler; algorithm and input data |
| in principle, accurate ________ models are available | mathematical |
| 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) | 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) |
| time efficiency is analyzed by determining the ________ of the basic operation as a function of input size | number of repetitions |
| this is the operation that contributes the most towards the running time of the algorithm | basic operation |
| what is the formula for theoretical analysis of time efficiency | 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 ________ | differently |
| searching for key in a list of n items will have what input size measure and basic operation? | input size: number of list's items (n), basic operation: key comparison |
| multiplication of two matrices will have what input size measure and basic operation? | 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? | 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? | input size: n of vertices and/or edges, basic operation: traversing an edge or visiting a vertex |
| in _________ analysis of time efficiency, we select a specific/typical sample of inputs and use a physical unit of time (ms) then analyze the data | empirical |
| enumerate all 3 cases in analyzing efficiency | Worst case, Best case, Average case (WBA) |
| this case is the maximum over inputs of size n | worst case - C_worst(n) |
| this case is the minimum over inputs of size n | best case - C_best(n) |
| this case is the "average" over inputs of size n | average case - C_avg(n) |
| this case is the number of times the basic operation will be executed on typical input | average case |
| is average case the average of the worse and best cases? | no |
| this case is the expected number of basic operations considered as a random variable under some assumption about the probability distribution of all inputs | average case |
| average case is expected under what distribution? | uniform |
| what is the worst, best, and average cases of a sequential search? | worst: n key (key is at the end), best: only comparisons (key is at front), average: (n+1)/2 assuming K is in A (key is in the middle) |
| enumerate the 3 types of formulas for basic operation's count | Exact formula, Formula indicating order of growth with SPECIFIC multiplicative constant, Formula indicating order of growth with UNKNOWN multiplicative constant |
| this is a way of saying/predicting how execution time of a program and the space/memory occupied by it changes with the input size | order of growth |
| this notation gives the worst case possibility for an algorithm | big O notation |
| the part of the program which takes the most amount of time is generally assumed to be the _________ in case of the Big-Oh notation | order of growth |
| enumerate the 3 types of asymptotic order of growth | Big Theta, Big Oh, Big Omega (TOO) |
| we use three types of ______ notations to represent the growth of any algorithm, as input increases | asymptotic |
| this notation is a class of functions that grow no faster than g(n) | O(g(n)) - Big Oh |
| this notation is a class of functions that grow at the same rate as g(n) | Theta(g(n)) - Big Theta |
| this notation is a class of functions that grow at least as fast as g(n) | Omega(g(n)) - Big Omega |
| these are ways of comparing functions that ignores constant factors and small input sizes | asymptotic order of growth (theta, oh, omega) |
| this notation encloses the function from above and below | theta notation |
| this notation represents the upper and the lower bound of the running time of an algorithm | theta notation |
| this notation is used for analyzing the average case complexity of an algorithm | theta notation |
| a function f(n) belongs to the set _____ if there exist positive constants c1 and c2 such that it can be sandwiched between c1g(n) and c2g(n) for sufficiently large n | Theta(g(n)) |
| if a function f(n) lies anywhere in between c1g(n) and c2g(n) for all n >= n0, then f(n) is said to be __________ | asymptotically tight bound |
| this notation represents the upper bound of the running time of an algorithm | big-o notation |
| a function f(n) belongs to the set _____ if there exists a positive constant c such that it lies between 0 and cg(n) for sufficiently large n | O(g(n)) |
| since it gives the worst case running time of an algorithm, it is widely used to analyze an algorithm as we are always interested in the worst case scenario | big-o notation |
| this notation represents the lower bound of the running time of an algorithm | omega notation |
| this notation provides the best case complexity of an algorithm | omega notation |
| a function f(n) belongs to the set _____ if there exists a positive constant c such that it lies above cg(n) for sufficiently large n | Omega(g(n)) |
| for any value of n, the _____ time required by the algorithm is given by Omega(g(n)) | minimum |
| this is a straightforward approach, usually based directly on the problem's statement and definitions of the concepts involved | 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 | brute force |
| (T/F) one strength of brute-force is its wide applicability | T |
| (T/F) one strength of brute-force is its simplicity | T |
| (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) | T |
| (T/F) one weakness of brute-force is its wide applicability | F |
| (T/F) one weakness of brute-force is its simplicity | 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) | F |
| (T/F) one strength of brute-force is that it rarely yields efficient algorithms | F |
| (T/F) one strength of brute-force is that some brute-force algorithms are unacceptably slow | F |
| (T/F) one strength of brute-force is that it is not as constructive as some other design techniques | F |
| (T/F) one weakness of brute-force is that it rarely yields efficient algorithms | T |
| (T/F) one weakness of brute-force is that some brute-force algorithms are unacceptably slow | T |
| (T/F) one weakness of brute-force is that it is not as constructive as some other design techniques | T |
| (T/F) brute-force is as constructive as some other design techniques | F |
| enumerate the 3 algorithms related to brute-force | (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 | selection sort |
| this algorithm maintains two subarrays in a given array | selection sort |
| enumerate the 2 subarrays maintained by selection sort | (1) the subarray which is already sorted, (2) the remaining subarray which is unsorted |
| in every iteration of this algorithm, the minimum element from the unsorted subarray is picked and moved to the sorted subarray | selection sort |
| selection sort algorithm has how many steps? | 5 |
| selection sort has what best time complexity? | O(n^2) |
| selection sort has what worst time complexity? | O(n^2) |
| selection sort has what average time complexity? | O(n^2) |
| selection sort has what space complexity? | O(1) |
| this algorithm involves finding a pattern within a text | string matching |
| this is a string of m characters to search for | pattern |
| this is a (longer) string of n characters to search in | text |
| this involves finding a substring in the text that matches the pattern | string matching |
| this compares a given pattern with all substrings of a given text | string matching |
| in string matching, those comparisons between substring and pattern proceed _____ by ______ unless a mismatch is found | character by character |
| whenever a ______ is found in string matching, the remaining character comparisons by that substring are dropped and the next substring can be selected immediately | mismatch |
| string matching has how many steps? | 3 |
| string matching has what worst time complexity in terms of m and n? | O(mn) |
| enumerate the 3 steps of brute-force string matching | (1) align pattern at beginning of text, (2) compare pattern with each corresponding character until all match or there exists a mismatch, (3) realign pattern until end of text while not found (ACR) |
| 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 | exhaustive search |
| this involves generating a list of all potential solutions to the problem in a systematic manner, evaluating potential solutions one by one, disqualifying infeasible ones, and for an optimization problem, keeping track of the best one found so far | exhaustive search |
| when this ends, it announces the solution(s) found | exhaustive search |
| 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 | traveling salesman problem |
| this is a problem where we find the shortest Hamiltonian circuit in a weighted connected graph | traveling salesman problem |
| this is a cycle that visits every vertex exactly once and returns to the starting vertex | Hamiltonian circuit |
| how many steps does the nearest neighbor algorithm for TSP have? | 5 |
| this approach to TSP involves checking all the edges joined to a starting vertex and choosing one that has the smallest weight | 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) | branch and bound (penalty) method |
| how many steps does the branch and bound (penalty) method for TSP have? | 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 | knapsack problem |
| this is a problem where we find the most valuable subset of the items that can fit into the _____ | knapsack problem |
| what is the worst time complexity of the knapsack problem? | O(2^n) |
| in knapsack, each subset can be represented by a _______ | binary string |
| in this approach, the problem in hand is divided into smaller sub-problems and then each problem is solved independently | 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 | divide and conquer |
| in this approach, those "atomic" smallest possible sub-problem (fractions) are solved | 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 | divide and conquer |
| enumerate the 3 steps of the divide and conquer approach | (1) Divide/Break, (2) Conquer/Solve, (3) Merge/Combine (DCM/BSC) |
| this step in the divide and conquer approach involves breaking the problem into smaller sub-problems | 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 | 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 | Divide/Break |
| at this step in the divide and conquer approach, sub-problems should represent a part of the original problem | Divide/Break |
| this step in the divide and conquer approach receives a lot of smaller sub-problems to be solved | Conquer/Solve |
| at this step in the divide and conquer approach, the problems are considered 'solved' on their own | Conquer/Solve |
| 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 | Merge/Combine |
| this step in the divide and conquer approach works recursively and conquer & merge steps work so close that they appear as one step | Merge/Combine |
| enumerate the 5 algorithms that use the divide and conquer approach | (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 | merge sort |
| merge sort has what worst-case time complexity? | O(n log n) |
| merge sort has what average-case time complexity? | O(n log n) |
| merge sort has what best-case time complexity? | O(n log n) |
| merge sort has what space complexity? | O(n) |
| merge sort has how many steps? | 3 |
| enumerate the 3 steps of merge sort | (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? | 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 | quick sort |
| 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 | quick sort |
| this algorithm partitions an array and then calls itself recursively twice to sort the two resulting subarrays after the partition | quick sort |
| this sorting technique is done by separating the list into two parts; initially, a pivot element is chosen by partitioning algorithm | 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 | pivot |
| quick sort has what worst-case time complexity? | O(n^2) |
| quick sort has what average-case time complexity? | O(n log n) |
| quick sort has what best-case time complexity? | O(n log n) |
| quick sort has what space complexity? | O(log n) |
| the quick sort pivot algorithm has how many steps? | 8 |
| the pivot algorithm normally used takes the ____ element as the pivot | last (highest index) |
| the quick sort algorithm itself has how many steps? | 4 |
| enumerate the 4 steps of quick sort | (1) make the right-most index value the pivot, (2) partition using pivot, (3) quicksort left partition, (4) quicksort right partition |
| this algorithm is a fast search algorithm with run-time complexity of O(log n) | binary search |
| this searching algorithm works on the principle of divide and conquer | binary search |
| for this algorithm to work propertly, the data collection should be in the sorted form | binary search |
| this algorithm looks for a particular item by comparing the middle most item of the collection | binary search |
| in binary search, if a match occurs, the ______ is returned | 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 | left |
| 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 | right |
| binary search continues until the size of the subarray reduces to ____ | zero |
| what is the formula for finding the mid index in binary search? | mid = low + (high - low) / 2 |
| if the element is not found in binary search, what is returned? | -1 |
| if the element in the middle index is less than the target, the new low variable for the next recursion should be set to what? | low = mid + 1 |
| if the element in the middle index is greater than the target, the new high variable for the next recursion should be set to what? | high = mid - 1 |
| this algorithm halves the searchable items and thus reduces the count of comparisons to be made | binary search |
| this algorithm is an algorithm for matrix multiplication | strassen's matrix multiplication |
| this algorithm is named after Volker Strassen, who discovered it in 1969 | strassen's matrix multiplication |
| who discovered Strassen's matrix multiplication? | Volker Strassen (in 1969) |
| what year was Strassen's matrix multiplication discovered? | 1969 |
| this algorithm is faster than the standard matrix multiplication algorithm and is useful in practice for large matrices | strassen's matrix multiplication |
| strassen's algorithm would be ____ than the fastest known algorithms for extremely large matrices | slower |
| this algorithm works for any ring, such as plus/multiply, but not all semirings, such as min/plus or boolean algebra | strassen's matrix multiplication |
| the naive matrix multiplication is so called __________ matrix multiplication | combinatorial |
| Volker Strassen proved that the general matrix multiplication algorithm wasn't optimal at time complexity of ____ | O(n^3) |
| although this algorithm is slightly better than the naive one, its publication resulted in much more research about the concept that led to faster approaches | strassen's matrix multiplication |
| a faster approach to matrix multiplication than both naive and strassen's is called the _______ algorithm | Coppersmith-Winograd |
| strassen's advantage is achieved by decreasing the total number of __________ performed at the expenses of a slight increase in the number of __________ | multiplications; additions |
| in the naive algorithm of matrix multiplication, there were ____ multiplications and ____ additions | eight; four |
| in strassen's algorithm of matrix multiplication, there are ____ multiplications and ____ additions | seven; eighteen |
| 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? | ae + bg |
| 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-RIGHT of the resulting matrix C would be what? | 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? | ce + dg |
| 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? | cf + dh |
| additon of two matrices takes O(__) time | O(n^2) |
| the idea of this method is to reduce the number of recursive calls from 8 to 7 | 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? | p1 = a(f - 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 p2? | 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? | 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? | 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? | p5 = (a + d)(e + 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 p6? | p6 = (b - d)(g + 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 p7? | p7 = (a - c)(e + f) |
| 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-LEFT cell of the resulting matrix C after computing p1-p7? | 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? | 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? | p3 + p4 |
| 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? | p1 + p5 - p3 - p7 |
| generally, this method is not preferred for practical applications because the constants used are high and the naive method works better for small matrices | strassen's matrix multiplication |
| generally, strassen's method is not preferred because for ______ matrices, there are better methods especially designed for them | sparse |
| in strassen's, the submatrices in recursion take extra _____ | space |
| because of the limited precision of computer arithmetic on noninteger values, ____ errors accumulate in strassen's method than in naive method | larger |
| the basic idea behind this alogirhm is to split matrices A and B into 8 submatrices and then recursively compute the submatrices of C | strassen's matrix multiplication |
| using the master theorem with T(n) = _____________, we still get a runtime of O(n^3) | 8T(n/2) + O(n^2) |
| strassen's matrix multiplication has what worst-case time complexity? | O(n^2.8074) |
| strassen's matrix multiplication has what best-case time complexity? | O(1) |
| strassen's matrix multiplication has what space complexity? | O(log n) |
| this problem is a problem of computational geometry | closest pair of points |
| this is a problem where given n points in metric space, find a pair of points with the smallest distance between them | closest pair of points |
| 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 | 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? | O(n^2) |
| using closest pair of points algorithm, instead of the naive O(n^2) method of finding the closest pair of points, we can find the closest pair of points in _______ time | 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 | uniqueness |
| in the computational model of closest-pair that assumed that the floor function is computable in constant time, the problem can be solved in ___________ time | 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 | randomization |
| in closest-pair, as a pre-processing step, the input array is sorted according to what? | x-coordinates |
| in closest-pair, time complexity can be improved to O(n log n) by optimizing the _______ step | sorting of strips (step 5) |
| closest pair of points has what worst-case time complexity? | O(n log n) |
| closest pair of points has how many steps? | 7 |
Created by:
user-1791948