MOD 1-4

Help!

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?

🗑

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?

🗑

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/F) one strength of brute-force is its simplicity

🗑

(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/F) one weakness of brute-force is its wide applicability

🗑

(T/F) one weakness of brute-force is its simplicity

🗑

(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)

🗑

(T/F) one strength of brute-force is that it rarely yields efficient algorithms

🗑

(T/F) one strength of brute-force is that some brute-force algorithms are unacceptably slow

🗑

(T/F) one strength of brute-force is that it is not as constructive as some other design techniques

🗑

(T/F) one weakness of brute-force is that it rarely yields efficient algorithms

🗑

(T/F) one weakness of brute-force is that some brute-force algorithms are unacceptably slow

🗑

(T/F) one weakness of brute-force is that it is not as constructive as some other design techniques

🗑

(T/F) brute-force is as constructive as some other design techniques

🗑

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?

🗑

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?

🗑

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?

🗑

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?

🗑

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?

🗑

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?

🗑

the pivot algorithm normally used takes the ____ element as the pivot

last (highest index)

🗑

the quick sort algorithm itself has how many steps?

🗑

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?

🗑

Review the information in the table. When you are ready to quiz yourself you can hide individual columns or the entire table. Then you can click on the empty cells to reveal the answer. Try to recall what will be displayed before clicking the empty cell.

To hide a column, click on the column name.

To hide the entire table, click on the "Hide All" button.

You may also shuffle the rows of the table by clicking on the "Shuffle" button.

Or sort by any of the columns using the down arrow next to any column heading.
If you know all the data on any row, you can temporarily remove it by tapping the trash can to the right of the row.

Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.

Normal Size Small Size show me how

Created by: user-1791948