Algorithms Sample Questions | Recurrences | Set 2
- Question 1: What is the complexity of T(n)?
- Θ( 1⁄n )
- Θ( 1⁄n2 )
- Θ( 1 )
- Θ( ln( n ) )
- Question 2: Determine (count) the total possible number of strings of length N with four characters {a, b, c, d} containing an even number of “a”s? [ C(N) is abbreviate of the function Count(N) to serve this purpose.]
- C(N) = 5.0 * 3N-1 – 1.0 *5N-1
- C(N) = 1.0 * 4N + 6
- C(N) = 0.5 *2N + 0.5 *4N
- C(N) = 1.0 * 2N + 2.0*(3)N
Example: For n = 1, there are 3 distinct strings: C(3) = 3
- b, c, d.
- aa, bb, cc, dd, bc, bd, cb, cd, db, dc
- The first character can be either one of possible characters “b”, ”c”, or “d” except “a”. In this case, the aim is to find the number of strings of remaining length “N-1” which are made of an even number of “a” s.
- C(N) = 3* C(N-1)
- The first character might be “a”, and one of “a”s is already occurred; therefore, the number of possible strings with odd numbers of “a”s should be counted. This number cannot be called C(N-1), but C(n) still can be achieved by using C(N-1).
- C(N) = 4N-1 – C(N-1), where:
- 4N-1: total number of possible strings of length (N-1) with four characters
- C(N-1): number of strings of length(N-1) made of an even number of “a”s.
- C(N) = 4N-1 – C(N-1), where:
- For n = 1, there are 3 distinct strings: b, c, d.
- Or, for n = 2, 10 possible strings are: aa, bb, cc, dd, bc, bd, cb, cd, db, dc
- Question 3: Which one of the recurrence functions does not have a solution of polynomial form?
- Option (1) has exponential solution: In order to find the homogeneous solution of the equation presented in first option, the roots of its characteristic equation is required:
- Option (2): The equation of second option can be easily solved by substitution technique:
- Option (3): In according to master theorem, the complexity of the equation proposed in third option is of .
- Option (4): Forth option equation lies into the case 3 of the master theorem; hence its complexity is of .
- Question 4: which one give the best estimation of F(n) asymptotic complexity?
100}\end{cases} " title="Rendered by QuickLaTeX.com" height="80" width="369" style="vertical-align: -33px;">
- O( n3 )
- Ω( n2 )
- O( n2 )
- Θ( n2 )
- [Finding as tightest boundary as possible] Best asymptotic estimation is when the complexity behavior is expressed by Θ-notation. This is mostly based on average performance of algorithms, so-called the average case scenario, which needs complicated analysis that the programmers prefer to use other notations like O (); however, still it is a good practice to try to find the tightest boundary as possible.
- [Notations talk about infinity] The mathematic asymptotic notations delineate the behavior of complexity functions in infinity, or when “n” tends toward a very large amount. Infinity is a hypothetical and abstract concept which cannot be reached in real life. For the purpose of calculations, and to have an idea of a function behavior, the number which should be considered is solely depend on the problem. In this problem seems to be no limit on the input data size “n”.
- [Being aware of the test-makers’ traps] In order to get rid of the potential traps provided by the test-makers, an enough large value shall be assigned to n; in this problem small values like 100, or 1000 shall not be chosen. As there is a need to compare the complexity of n3 for n < 100, versus n2 for n > 100, the values greater than 1000 is acceptable that causes n2 excel n3 for n = 100 . Even if we were about to re-calculate F(100) at each call time, for n> 1000, n2 is always greater than F(100) which is of order n3 for small values such as n=100. The value of F(100) can be simply ignored in required calculations for n > 1000.
- [In real world applications, It would sometimes be efficient to use some AUXILIARY MEMORY SPACE to gain some speed] In this problem, it would be a great idea to use an auxiliary memory space of Θ(1) to save the result of F(100) at once for future use, without having to recalculate F(100) at each call time for n>100. So the complexity of F(100) would be of O(1), maybe just to read a value, and the complexity of F(n) would be of Θ(n2) for n>100.
- Question 5: Which one specifies appropriate ranges for k and α (alpha), where the following asymptotic expression holds?
- α ≥ 0 & k ≤ α
- α ≥ 0.1 & k ≥ 0
- α > 1 & k ∈ R
- α > 0 & k ∈ R
for k ∈ R & α>0
The polynomial expressions cannot contain variables with fractional exponents; therefore, this problem is even more inclusive as it takes such fractional values. As a result, this problem statement describes how easily polynomial expressions grows faster than the logarithm functions.Source:
- MIT Asymptotic cheat sheet
- A compilation of Iran university exams (with a bit of summarization, modification, and also translation)
Contact Us