Developing Efficient Algorithms Flashcards
What is the problem with measuring algorithm efficiency by testing the running time of the programs?
- Many tasks run concurrently on a computer. The execution time of a particular program depends on the system load.
- The execution time depends on specific input. Consider, for example, linear search and binary search. If an element to be searched happens to be the first in the list, linear search will find the element quicker than binary search.
What is “the big O notation”?
Computer scientists use the Big O notation to represent the “order of magnitude”. Using this notation, the complexity of the linear search algorithm is O(n), pronounced as “order of n”.
What do we measure algorithm efficiency by?
We measure their growth rates in relation to input growth/size.
What is best-case input and worst-case input?
An input that results in the shortest execution time possible is called the best-case input.
An input that results in the longest execution time possible is called the worst-case input.
What are best-case and worst-case analysis good for?
They are not representative, but worst-case analysis is very useful, because you can be assured that the algorithm will never be slower than the worst case.
What is average-case analysis?
Average-case analysis attempts to determine the average amount of time among all possible inputs of the same size. Average-case analysis is ideal, but difficult to perform, because for many problems it is hard to determine the relative probabilities and distributions of various input instances. Worst-case analysis is easier to perform, so the analysis is generally conducted for the worst case.
The linear search algorithm requires n comparisons in the worst case and n/2 comparisons in the average case if you are nearly always looking for something known to be in the list.
Using the Big O notation, what are the algorithmic complexity of n and n/2 respectively?
Both cases require O(n) time. The multiplicative constant (1/2) can be omitted. Algorithm analysis is focused on growth rate. The multiplicative constants have no impact on growth rates. The growth rate for n/2 or 100n is the same as for n.
When do we need algorithm analysis?
When there’s a possibility for large input sizes we should perform algorithm analysis. If the input size is small, there is no significance in estimating an algorithm’s efficiency.
What is the complexity of an algorithm that takes n - 1 time to execute?
The Big O notation allows you to ignore the nondominating part (e.g., -1 in the expression n - 1) and highlight the important part (e.g., n in the expression n - 1). Therefore, the complexity of this algorithm is O(n).
What is meant by “complexity of contant time”?
The Big O notation estimates the execution time of an algorithm in relation to the input size. If the time is not related to the input size, the algorithm is said to take constant time with the notation O(1). For example, a method that retrieves an element at a given index in an array takes constant time, because the time does not grow as the size of the array increases.
What is the algorithmic complexity of.
1+2+3+…+(n-2)+(n-1) = (n(n-1))/2
?
O(n^2)
Consider the time complexity for the following loop:
for (i = 1, i
It is a constant time, c, for executing
k = k + 5;
Since the loop is executed n times, the time complexity for the loop is
T(n) = (a constant c) * n = O(n)
What is a quadratic algorithm?
An algorithm with the O(n^2) time complexity is called a quadratic algorithm. The quadratic algorithm grows quickly as the problem size increases. If you double the input size, the time for the algorithm is quadrupled. Algorithms with a nested loop are often quadratic.
What is the time complexity of the following selection statement?
if ( list.contains(e)) {
- System.out.println(e);
}
else
- for (Object t: list) {
- System.out.println(t);
- }Suppose the list contains n elements. The execution time for list.contains(e) is O(n). The loop in the else clause takes O(n) time. Hence, the time complexity for the entire statement is
T(n) = if test time + worst-case time(if clause, else clause)
= O(n) + O(n) = O(n)
Consider the computation of a^n for an integer n. A simple algorithm would multiply a n times, as follows:
result = 1;
for (int i = 1; i
The algorithm takes O(n) time. Without loss of generality, assume n = 2^k. You can improve the algorithm using the following scheme:
result = a;
for (int i = 1; i
What is a logarithmic algorithm?
An algorithm with the O(log(n)) time complexity is called a logarithmic algorithm. The logarithmic algorithm grows slowly as the problem size increases. If you square the input size of any logarithmic time algorithm, you only double the time of execution. So a logarithmic-time algorithm is very efficient.
What is an exponential algorithm?
An algorithm with O(2^n) time complexity is called an exponential algorithm. As the input size increases, the time for the exponential algorithm grows exponentially. Exponential algorithms are not practical for large input sizes.
The Tower of Hanoi algorithm is exponential. Suppose the disk is moved at a rate of 1 per second. It would take 136 years to move 32 disks, and 585 billion years to move 64 disks.
What is dynamic programming?
Dynamic programming is the process of solving subproblems that overlap, then combining the solutions of the subproblems to obtain an overall solution.
The key idea behind dynamic programming is to solve each subproblem only once and store the results for subproblems for later use to avoid redundant computing of the subproblems.
What is a brute-force algorithm?
Brute force refers to an algorithmic approach that solves a problem in the simplest or most direct or obvious way. As a result, such an algorithm can end up doing far more work to solve a given problem than a cleverer or more sophisticated algorithm might do. On the other hand, a brute-force algorithm is often easier to implement than a more sophisticated one and, because of this simplicity, sometimes it can be more efficient.
Is there any practical considerations when comparing two algorithms of equal time complexity?
The Big O notation provides a good theoretical estimate of algorithm efficiency. However, two algorithms of the same time complexity are not necessarily equally efficient.
What is the divide-and-conquer approach?
The divide-and-conquer approach divides the problem into subproblems, solves the subproblems, then combines the solutions of the subproblems to obtain the solution for the entire problem. Unlike the dynamic programming approach, the subproblems in the divide-and-conquer approach don’t overlap. A subproblem is like the original problem with a smaller size, so you can apply recursion to solve the problem.
What is the backtracking approach?
Backtracking is a refinement of the brute force approach, which systematically searches for a solution to a problem among all available options.
The backtracking approach searches for a candidate solution incrementally, abandoning that option as soon as it determines that the candidate cannot possibly be a valid solution, and then looks for a new candidate.
What is computational geometry?
Computational geometry is to study the algorithms for geometrical problems. It has applications in computer graphics, games, pattern recognition, image processing, robotics, geographical information systems, and computer-aided design and manufacturing.
Estimating algorithm efficiency is ___
A. to measure their actual execution time.
B. to estimate their execution time.
C. to estimate their growth function.
C. to estimate their growth function.
Which of the following complexity is O(nlogn)
A. 300n + 400nn
B. 23nlogn + 50
C. 45n + 45nlogn + 503
D. nn*n + nlogn
B and C are correct
What is the number of iterations in the following loop:
int count = 5;
while (count
The correct answer is E
Explanation: Consider n = 5, 0 iteration. Consider n = 6, 1 iteration. Consider n = 7, 1 iteration. Consider n = 8, 1 iteration. Consider n = 9, 2 iterations. Consider n = 10, 2 iterations. Consider n = 11, 2 iterations. Consider n = 12, 3 iterations. Consider n = 13, 3 iterations. Consider n = 14, 3 iterations. Consider n = 15, 4 iterations. (ceiling((15-5)/3) = 4.
For a sorted list of 1024 elements, a binary search takes at most ___ comparisons. Note that to check whether an element is greater than, equal to, or less than the other element is considered as one comparison here.
A. 11
B. 100
C. 512
D. 6
A. 11.
O(1) is __
A. constant time
B. logarithmic time
C. linear time
D. log-linear time
A. constant time
The time complexity for the selection sort algorithm in the text is __
A. O(nlogn)
B. O(n^2)
C. O(logn)
D. O(2^n)
B. O(n^2)
The time complexity for the insertion sort algorithm in the text is ___
A. O(nlogn)
B. O(n^2)
C. O(logn)
D. O(2^n)
B. O(n^2)
The time complexity for the recursive Fibnacci algorithm in the text is __
A. O(nlogn)
B. O(n^2)
C. O(logn)
D. O(2^n)
D. O(2^n)
The time complexity for the Euclid?s algorithm is __
A. O(n)
B. O(n^2)
C. O(logn)
D. O(2^n)
C. O(logn)
The time complexity for the Sieve of Eratosthenes algorithm is __
A. O(n)
B. O(n^(1.5)/logn)
C. O(logn)
B. O(n^(1.5)/logn)
The time complexity for the the closest pair of points problem using divide-and-conquer is __
A. O(n)
B. O(nlogn)
C. O(logn)
D. O(2^n)
B. O(nlogn)
The gift-wrapping algorithm for finding a convex hull takes __
A. O(n)
B. O(nlogn)
C. O(logn)
D. O(n^2)
D. O(n^2)
The Graham’s algorithm for finding a convex hull takes ___
A. O(n)
B. O(nlogn)
C. O(logn)
D. O(n^2)
B. O(nlogn)
