Module 2 Flashcards
Memorization
It is a process in which a function calls itself directly or
indirectly.
Recursion
It is a process which breaks a task into smaller subtasks.
Recursion
(smaller subtask)
It is a powerful technique that can be used in place of
iterations.
Recursion
(powerful technique)
True or False. A base case should be defined to avoid infinite loops.
True
The ________ is when a loop repeatedly executes until the controlling condition becomes false.
Iteration
(loop repeatedly executes)
True or False. Recursion and Iteration both repeatedly execute the set of instructions.
True
True or False. Recursion is applied to the set of instructions which we want to get repeatedly executed.
False
(ITERATION is applied to the set of instructions which we want to get repeatedly executed)
True or False. Recursion is a process, always applied to a function.
True
Iteration uses _______ structure.
Repetition
True or False. An infinite loop occurs with iteration if the loop condition test never becomes true and Infinite looping uses CPU cycles repeatedly.
False
(An infinite loop occurs with iteration if the loop condition test never becomes FALSE)
True or False. An iteration does not use the stack so it’s faster than recursion.
True
True or False. An iteration terminates when the loop condition is satisfied.
False
( An iteration terminates when the loop condition FAILS)
Recursion uses ______ structure.
Selection
True or False. Iteration consumes less memory but makes the code longer.
True
True or False. Recursion terminates when a base case is recognized.
True
True or False. Infinite recursion occurs if the recursion step does not reduce the problem in a manner that converges on some condition (base case) and Infinite recursion can crash the system.
True
True or False. Recursion is usually faster than iteration despite the overhead of maintaining the stack.
False
(Recursion is usually SLOWER than iteration DUE TO the overhead of maintaining the stack)
True or False. Recursion uses less memory than iteration.
False
(Recursion uses MORE memory than iteration)
True or False. Recursion makes the code smaller.
True
What are the 4 types of recursion?
(DINT)
- Direct Recursion
- Indirect Recursion
- Tail Recursion
- Non-Tail Recursion
This type of recursion calls the same function again.
Direct Recursion
This type of recursion calls another function which then calls the same function again.
Indirect Recursion
This type of recursion has a recursive call as the last thing done by the function.
Tail Recursion
(recursive call is the last thing done)
This type of recursion’s recursive call is not the last thing done by the recursion.
Non-Tail Recursion
(recursive call is not the las thing done)
True or False. The efficiency of an algorithm can only be in terms of time.
False
(can be in terms of TIME AND SPACE)
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
The _________ of an algorithm can be decided by
measuring the performance of an algorithm.
Efficiency
Analysis of algorithm is the process of investigation
of an algorithm’s efficiency respect to two resources. What are these two resources?
- Running Time
- Memory Space
The reason for selecting the two criteria of analysis of algorithm are?
(SGSM)
- Simplicity
- Generality
- Speed
- Memory
_________________ indicates
how fast an algorithm runs.
Time efficiency or /time complexity
_________________ is the amount of memory units required by the
algorithm including the memory needed for the i/p & o/p.
Space Efficiency or Space complexity
In mathematics, computer science, and related fields, _______________ 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
(describes the limiting behavior of a function)
True or False. When time complexity is expressed using big O notation, the time complexity is said to be described asymptotically, i.e., as the input size goes to infinity.
True
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
(amount of time taken)
True or False. Analysis of algorithms and data structure is the major force that drives the design of solutions.
True
What are the scientific methods in the framework for predicting performance and comparing algorithms?
(OHPVV)
- OBSERVE the natural world
- HYPOTHESIZE a model that is consistent with observations
- PREDICT events using hypothesis
- VERIFY the predictions by making further observations
- VALIDATE by repeating until the hypothesis and observations agree
What are the principles in the framework for predicting performance and comparing algorithms?
- Experiments must be REPRODUCIBLE
- Hypothesis must be FALSIFIABLE
It refers to the amount of memory required by an algorithm
(including the input values to the algorithm) to run.
Space complexity
It is the extra space or the temporary space used by the algorithm during it’s execution.
Auxiliary Space
While executing, what are the three reasons that algorithms use memory space?
(DIE)
- Data Space
- Instruction Space
- Environmental Stack
It is the amount of memory used to save the compiled version of instructions.
Instruction Space
It is the amount of space used by the variables and constants.
Data Space
It is a count denoting number of
times of execution of a statement.
Frequency Count
