MOD 6_ZYBOOKS 7_RECURSION & ALGORITHM Flashcards
(36 cards)
What is a recursive algorithm?
A recursive algorithm is an algorithm that breaks the problem into smaller subproblems and applies the same algorithm to solve the smaller subproblems.
What is the base case?
A recursive algorithm must describe how to actually do something, known as the base case.
What is a recursive function?
A function that calls itself is a recursive function.
What are the 2 steps to creating a recursive function?
What are 2 common errors when creating recursive functions?
A common error is to not cover all possible base cases in a recursive function. Another common error is to write a recursive function that doesn’t always reach a base case. Both errors may lead to infinite recursion, causing the program to fail.
What are “outer” and “inner” functions?
Typically, programmers will use two functions for recursion. An “outer” function is intended to be called from other parts of the program, like the function int CalcFactorial(int inVal). An “inner” function is intended only to be called from that outer function, for example a function int CalcFactorialHelper(int inVal). The outer function may check for a valid input value, e.g., ensuring inVal is not negative, and then calling the inner function. Commonly, the inner function has parameters that are mainly of use as part of the recursion, and need not be part of the outer function, thus keeping the outer function more intuitive.
Before writing a recursive function, a programmer should determine?
1) Does the problem naturally have a recursive solution?
2) Is a recursive solution better than a non-recursive solution?
What is an algorithm?
An algorithm describes a sequence of steps to solve a computational problem or perform a calculation. An algorithm can be described in English, pseudocode, a programming language, hardware, etc. as long as the algorithm precisely describes the steps of a computational procedure.
What is a computational problem?
A computational problem specifies an input, a question about the input that can be answered using a computer, and the desired output.
VIEW: Example computational problems and common algorithms
What are NP-complete problems and what are their characteristics?
Algorithm efficiency is typically measured by?
The algorithm’s computational complexity.
What is computational complexity?
Computational complexity is the amount of resources used by the algorithm.
What are the most common resources considered by computational complexity?
Runtime and memory usage.
What is an algorithm’s runtime complexity?
An algorithm’s runtime complexity is a function, T(N), that represents the number of constant time operations performed by the algorithm on an input of size N.
What is meant by an algorithm’s best case and worst case scenario?
An algorithm’s best case is the scenario where the algorithm does the minimum possible number of operations. An algorithm’s worst case is the scenario where the algorithm does the maximum possible number of operations.
VIEW: Input data size must remain a variable
What is an algorithm’s space complexity?
An algorithm’s space complexity is a function, S(N), that represents the number of fixed-size memory units used by the algorithm for an input of size N.
Ex: The space complexity of an algorithm that duplicates a list of numbers is S(N) = 2N + k, where k is a constant representing memory used for things like the loop counter and list pointers.
What is an algorithm’s auxiliary space complexity?
An algorithm’s auxiliary space complexity is the space complexity not including the input data.
Ex: An algorithm to find the maximum number in a list will have a space complexity of S(N) = N + k, but an auxiliary space complexity of S(N) = k, where k is a constant.
What is a constant time operator?
In practice, designing an efficient algorithm aims to lower the amount of time that an algorithm runs. However, a single algorithm can always execute more quickly on a faster processor. Therefore, the theoretical analysis of an algorithm describes runtime in terms of number of constant time operations, not nanoseconds.
A constant time operation is an operation that, for a given processor, always operates in the same amount of time, regardless of input values.
VIEW: Common constant time operations
What are lower and upper bounds?
Given a function T(N), an infinite number of lower bounds and upper bounds exist. Ex: If an algorithm’s best case runtime is T(N) = 5N + 4, then subtracting any nonnegative integer yields a lower bound: 5N + 3, 5N + 2, and so on. So two additional criteria are commonly used to choose a preferred upper or lower bound. The preferred bound:
1) Is a single-term polynomial and
2) bounds T(N) as tightly as possible.
What is an asymptotic notation?
Asymptotic notation is the classification of runtime complexity that uses functions that indicate only the growth rate of a bounding function.
What 3 asymptotic notations are commonly used in complexity analysis?
