2.2-1 Express the function n^3/1000-100n^2-100n+3 in terms of theta-notation. Solution: theta(n^3)
2.2-2 Write an algorithm for selection sort. What loop invariant does this algorithm maintain? Why does it need to run for only the first n-1 elements, rather than for all n elements? Give the best-case and worst-case running times of selection sort in theta-notation. Solution:
The loop invariant is the sorted sub-array A[1,..,i]. The last element is trivially sorted. The best case is pre-sorted, the worst case is anti-sorted.
2.2-3 Consider linear search again. How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be an element in the array? How about in the worst case? What are the average-case and worst-case running times of linear search in theta-notation? Solution: Since it is equally like that the element is in the first or second half subarray, half of the elements will be searched on average. in the worst case, all of the elements will be searched. Both have linear run times n/2 and n, so T(n)=theta(n).
2.2-4 How can we modify any algorithm to have a good best-case running time? Solution: Assign a correct pre-calculated output for a selected input and have this checked (in constant time). Usually not useful.
Monday, March 4, 2013
Chapter 2 Section 1 Exercises Intro to Algorithms CLRS (3rd)
2.1-1 Using figure 2.2 as a model, illustrate the operation of insertion sort on the array A=<31,41,59,26,41,58>. Solution: Check <31,41,59,26,41,58> Continue. Check <31,41,59,26,41,58> Continue. Check <31,41,59,26,41,58> Swap/Check <31,41,26,59,41,58> Swap/Check <31,26,41,59,41,58> Swap/Check <26,31,41,59,41,58> Continue. Check <26,31,41,59,41,58> Swap/Check <26,31,41,41,59,58> Continue. Check <26,31,41,41,59,58> Swap/Check <26,31,41,41,58,59> End.
2.1-2 Rewrite the INSERTION-SORT procedure to sort into non-increasing instead of non-decreasing order. Solution:
2.1-3 Consider the searching problem:
Input: A sequence of n numbers in a list A and a value v.
Output: An index i such that v=A[i] or the special value NIL if v does not appear in A. Write linear search, which scans through the sequence looking for v. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.
Solution: At the start of each iteration of the loop, the value has not appeared for the checked values in the subarray A[1,..,j]. This is our loop invariant.
2.1-4 Consider the problem of adding two n-bit binary integers, stored in two n-element arrays A and B. The sum of the two integers should be stored in binary form in an (n+1)-element array C.
2.1-2 Rewrite the INSERTION-SORT procedure to sort into non-increasing instead of non-decreasing order. Solution:
2.1-3 Consider the searching problem:
Input: A sequence of n numbers in a list A and a value v.
Output: An index i such that v=A[i] or the special value NIL if v does not appear in A. Write linear search, which scans through the sequence looking for v. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.
Solution: At the start of each iteration of the loop, the value has not appeared for the checked values in the subarray A[1,..,j]. This is our loop invariant.
2.1-4 Consider the problem of adding two n-bit binary integers, stored in two n-element arrays A and B. The sum of the two integers should be stored in binary form in an (n+1)-element array C.
Solution:
Chapter 1 Problems Intro to Algorithms CLRS (3)
1-1 Comparison of running times
For each function f(n) and time t in the following table, determine the largest size n of a problem that can be solved in time t, assuming that the algorithm to solve the problem takes f(n) microseconds.
Solution: 1 month = 30 days, 1 year = 365 days. Click to enlarge
For each function f(n) and time t in the following table, determine the largest size n of a problem that can be solved in time t, assuming that the algorithm to solve the problem takes f(n) microseconds.
Solution: 1 month = 30 days, 1 year = 365 days. Click to enlarge
Chapter 1 Section 2 Exercises Intro to Algorithms CLRS (3)
1.2-1 Give an example of an application that requires algorithmic content at the application level, and discuss the function of the algorithms involved. Solution: Any application which seeks an optimized output (efficient paths for example).
1.2-2 Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8n^2 steps, while merge sort runs in 64nlgn steps. For which values of n does insertion sort beat merge sort? Solution: We find where they're equal and note that they're both increasing. 8n^2=64nlgn -> n = 1.1 or n=43.56. These serve as the endpoints of the interval for which insertion sort beats merge sort. In other words, use insertion sort for n<44 (since the n=1 case is trivially sorted).
1.2-3 What is the smallest value of n such that an algorithm whose running time is 100n^2 runs faster than an algorithm whose running time is 2^n on the same machine? Solution: Solve for the points of intersection as in 1.2-2 to find n=0.1 or n=14.3. This makes sense since if n=0, 0<1, but 100n^2 grows quickly on small positive values until 14.3, when the values are then dominated by 2^n.
1.2-2 Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8n^2 steps, while merge sort runs in 64nlgn steps. For which values of n does insertion sort beat merge sort? Solution: We find where they're equal and note that they're both increasing. 8n^2=64nlgn -> n = 1.1 or n=43.56. These serve as the endpoints of the interval for which insertion sort beats merge sort. In other words, use insertion sort for n<44 (since the n=1 case is trivially sorted).
1.2-3 What is the smallest value of n such that an algorithm whose running time is 100n^2 runs faster than an algorithm whose running time is 2^n on the same machine? Solution: Solve for the points of intersection as in 1.2-2 to find n=0.1 or n=14.3. This makes sense since if n=0, 0<1, but 100n^2 grows quickly on small positive values until 14.3, when the values are then dominated by 2^n.
Introduction to Algorithms, 3rd
Cormen, Leiserson, Rivest, Stein
1.2 Exercises
Chapter 1 Section 1 Exercises Intro to Algorithms CLRS (3)
1.1-1 Give a real-world example that requires sorting or a real-world example that requires computing a convex hull. Solution: Finding the median of a set of values requires sorting. Finding a convex hull would be required to determine the small amount of fencing required to enclose a set of points (trees?) with a circular (or shape x) fence.
1.1-2 Other than speed, what other measures of efficiency might one use in a real-world setting? Solution: memory cost, bandwidth, etc.
1.1-3 Select a data structure that you have seen previously, and discuss is strengths and limitations. Solution: An array, dictionary, matrix, linked list
1.1-4 How are the shortest-path and traveling-salesman problems given above similar? Solution: The shortest path problem asks for a shortest route between two points on a graph. The travelling salesman asks for the shortest path that visits all points on the graph and returns to the starting point. The difference is that the first problem involves only two points whereas the second involves all points.
1.1-5 Come up with a real-world problem in which only the best solution will do. Then come up with one in which a solution that is "approximately" the best is good enough. Solution: Calculating landing speed for an airplane, the trajectory of a missile or satellite, and the key to a crypto-system all require an exact solution. Approximate: statistics.
Introduction to Algorithms, 3rd
Cormen, Leiserson, Rivest, Stein
1.1 Exercises
Subscribe to:
Comments (Atom)