算法分析與设计考试样卷.docVIP

算法分析与设计复习题 1.Based on what we have discussed in class, state the best asymptotic running time for each of the problems below, using the ”big Oh” notation. It is assumed that T(1) =d for some constant din all the recurrences. If you think the problem is NP-complete, state so (no running time should be given in this case). Just state the answers- you do not need to justify them. 2. Describe the main ideas of the following strategies, and briefly describe the differences between them. (1) divide-and–conquer; (2) dynamic programming； During the course we have studied some important classes of algorithms. Three of these are Divide and Conquer Algorithms, Greedy Algorithms and Dynamic Programming Algorithms. Give non-trivial examples of each of these three types of algorithms and describe them in detai. For each example, explain what makes it such an algorithm. (That is, for your example of a greedy algorithm you should explain exactly what makes it a greedy algorithm, and so on.) Solution: There are lot of possible solutions. Natural examples would be: Divide and Conquer: Mergesort Greedy: Kruskal’s algorithm. Dynamic Programming: Dijkstra’s algorithm or Bellman-Ford’s algorithm. 4. (30 points) Choose T or F for each of the following statements. The best case running time for quicksort to sort an element array is O(nlogn). By the master theorem, the solution to the recurrence T(n)=3T(n/3)+3n is T(n)=O(nlogn). Every binary search tree on n nodes has height O(logn). By using path compression (Union- Find) technique to analyze Kruskal algorithm, the algorithm’s running time is O(mlog*n+nlog*n). Depth-first search of a graph is asymptotically faster than breadth-first search. Kruskal’s algorithm for finding a minimum spanning tree employs dynamic programming. The backtrack technique uses the idea of breath first search to get the optimal value. n!=O(2n). In the worst case, merge sort runs in O(n2）time.science, all the problems are either in P or NP. Kruskal’s a