WorksheetsALGO MODULE 2 FA2
Total questions: 82
Worksheet time: 43mins
A process in which a function calls itself directly or indirectly
(a)
A process which breaks a task into smaller subtasks
(a)
A powerful technique that can be used in place of iterations.
(a)
repeatedly execute the set of instructions
Iteration
Recursion
Both
when a statement in a function calls itself repeatedly.
Iteration
Recursion
Both
when a loop repeatedly executes until the controlling condition becomes false
Iteration
Recursion
Both
uses repetition structure
Iteration
Recursion
Both
does not use the stack so it's faster
Iteration
Recursion
Both
consumes less memory.
Iteration
Recursion
Both
makes the code longer.
Iteration
Recursion
Both
uses selection structure.
Iteration
Recursion
Both
usually slower due to the overhead of maintaining the stack.
Iteration
Recursion
Both
uses more memory
Iteration
Recursion
Both
It calls the same function again
Direct recursion
Indirect recursion
Tail recursion
Non-tail recursion
a function calls another function, which in turn calls the first function again.
Direct recursion
Indirect recursion
Tail recursion
Non-tail recursion
if the recursive call is the last thing done by the function. There is no need to keep record of the previous state.
Direct recursion
Indirect recursion
Tail recursion
Non-tail recursion
if the recursive call is not the last thing done by the function. After returning back, there is some something left to evaluate
Direct recursion
Indirect recursion
Tail recursion
Non-tail recursion
There is a systematic approach that has to be applied for analyzing any given algorithm. This systematic approach is modelled by a framework called as
Analysis framework
space
efficiency of an algorithm
the process of investigation of an algorithm’s efficiency respect to two resources.
Analysis of algorithm
space
efficiency of an algorithm
framework for predicting performance and comparing algorithms
Analysis of algorithm
scientific method
efficiency of an algorithm
describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions
Analysis of algorithm
scientific method
efficiency of an algorithm
big O notation
time complexity
quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem.
Analysis of algorithm
scientific method
efficiency of an algorithm
big O notation
time complexity
indicates how fast an algorithm runs
Time efficiency or time complexity
Space Efficiency or space complexity
amount of memory units required by the algorithm including the memory needed for the i/p & o/p.
Time efficiency or time complexity
Space Efficiency or space complexity
must be reproducible
experiments
hypothesis
must be falsifiable
experiments
hypothesis
which scientific method is this: _______ some features of the natural world
Observe
Hypothesize
Predict
Verify
Validate
which scientific method is this: _______ a model that is consistent with the observations
Observe
Hypothesize
Predict
Verify
Validate
which scientific method is this: _______ events using the hypothesis
Observe
Hypothesize
Predict
Verify
Validate
which scientific method is this: _______ the predictions by making further observations
Observe
Hypothesize
Predict
Verify
Validate
which scientific method is this: _______ by repeating until the hypothesis and observation agree
Observe
Hypothesize
Predict
Verify
Validate
cpu, memory, cache
hardware
software
system
compiler, interpreter, garbage collector
hardware
software
system
OS, network, other apps
hardware
software
system
The amount of memory required by an algorithm (including the input values to the algorithm) to run.
Space complexity
Time complexity
Total running time
sum of cost x frequency for all operations
Space complexity
Time complexity
Total running time
how much memory, in the worst case, is needed at any point in the algorithm.
Space complexity
Time complexity
Total running time
the extra space or the temporary space used by the algorithm during
it's execution.
Space complexity
Time complexity
Total running time
Auxiliary space
Auxiliary Space + Input space = ?
Space complexity
Time complexity
Total running time
Auxiliary space
The amount of time required by an algorithm to run for completion.
Space complexity
Time complexity
Total running time
Auxiliary space
Frequency count
a count denoting number of times of execution of a statement.
Space complexity
Time complexity
Total running time
Auxiliary space
Frequency count
the amount of memory used to save the compiled version of instructions
Instruction space
Environmental stack
Data space
Space complexity
amount of space used by the variable and constants
Instruction space
Environmental stack
Data space
Space complexity
while calculating the Space Complexity of any algorithm, we usually consider only ________ and we neglect the Instruction Space and Environmental Stack
Instruction space
Environmental stack
Data space
Space complexity
bool, char, unsigned char, signed char, ___int8
1 byte
2 bytes
4 bytes
8 bytes
___int16, short, unsigned short, wchar_t, __wchar_t
1 byte
2 bytes
4 bytes
8 bytes
What is the basic operation when solving for graph problems
division
visiting a vertex
multiplication of two numbers
key comparison
float, ___int32, int, unsigned int, long, unsigned long
1 byte
2 bytes
4 bytes
8 bytes
double, __int64, long double, long long
1 byte
2 bytes
4 bytes
8 bytes
constant
O(1)
O (log n)
O(n)
O(n log n)
O(n^2)
logarithmic
O(1)
O (log n)
O(n)
O(n log n)
O(n^2)
linear
O(1)
O (log n)
O(n)
O(n log n)
O(n^2)
linearithmetic / quasilinear
O(1)
O (log n)
O(n)
O(n log n)
O(n^2)
quadratic
O(1)
O (log n)
O(n)
O(n log n)
O(n^2)
cubic
O(n^3)
O(n^k), k >= 1
O(a^n), a >= 1
O(n!)
polynomial
O(n^3)
O(n^k), k >= 1
O(a^n), a >= 1
O(n!)
exponential
O(n^3)
O(n^k), k >= 1
O(a^n), a >= 1
O(n!)
factorial
O(n^3)
O(n^k), k >= 1
O(a^n), a >= 1
O(n!)
log(n^2)
constant
logarithmic
linear
linearithmetic / quasilinear
quadratic
n, 2n + 5
constant
logarithmic
linear
linearithmetic / quasilinear
quadratic
n log n, log n!
constant
logarithmic
linear
linearithmetic / quasilinear
quadratic
n^2 + n, n^10
polynomial
exponential
factorial
linearithmetic / quasilinear
quadratic
1.1^n, 10^n
polynomial
exponential
factorial
linearithmetic / quasilinear
quadratic
how many nanoseconds will it take to: add an integer
2.1
2.4
5.4
4.6
4.2
how many nanoseconds will it take to: multiply an integer
2.1
2.4
5.4
4.6
4.2
how many nanoseconds will it take to: divide an integer
2.1
2.4
5.4
4.6
4.2
how many nanoseconds will it take to: add a floating point
2.1
2.4
5.4
4.6
4.2
how many nanoseconds will it take to: multiply a floating point
2.1
2.4
5.4
4.6
4.2
how many nanoseconds will it take to: divide a floating point
13.5
91.3
129.0
4.6
4.2
how many nanoseconds will it take to: sine
13.5
91.3
129.0
4.6
4.2
When the input size measures the matrix dimension or total number of elements what is the basic operation
division
multiplication of two numbers
visiting a vertex
key comparison
how many nanoseconds will it take to: arctangent
13.5
91.3
129.0
4.6
4.2
Order of growth of an algorithm is a way of saying/predicting how execution
time of a program and the space/memory occupied by it changes with the
input size.
true
false
class of functions f(n) that grow no faster than g(n)
class of function f(n) that grow at same rate as g(n)
class of function f(n) that grow at least as fast as g(n)
encloses the function from above and below. Since it represents the upper and the lower bound of the running time of an algorithm, it is used for analyzing the average case complexity of an algorithm.
Big theta
Big Oh
Big Omega
represents the upper bound of the running time of an algorithm. Thus, it gives the worst case complexity of an algorithm.
Big theta
Big Oh
Big Omega
represents the lower bound of the running time of an algorithm. Thus, it provides best case complexity of an algorithm.
Big theta
Big Oh
Big Omega
This algorithmic check for the efficiency looking at the max input of n
best
average
worst
none
In a multi-user system _____ depends on many factors such as: System load, Number of other programs running, Instruction set used and Speed of underlying hardware
Space complexity
Executing time
CPU count
Time Complexity
Finding the smallest or largest item in an unsorted array
linear
cubic
quadratic
constant
