Sample Questions for the Final Examination

1. Algorithm A uses 10nlogn operations, while algorithm B uses n² operations. Determine the value n₀ such that A is better than B for n ³ n₀.

2. Show that log³n is o(n^1/3).

3. Explain the Division method and MAD method of compressing maps in hash table

4. Explain different schemes for collision handing in hash table

5. Draw the 11-item hash table resulting from hashing the keys 12, 44, 13, 88, 23, 94, 11, 39, 20, 16, and 5, using the hash function h(i)=(2i+5)mod 11 and assuming collisions are handled by chaining.

6. Illustrate the performance of the selection-sort, insertion sort, bubble sort, quick sort, merge sort, and heap-sort algorithm, respectively, on the following input sequence: 1, 4, 3, 8, 6, 9, 7, 12, 29, 25.

7. What is a priority queue and priority sort? How to use priority queue to implement selection sort and insert sort?

8. Show the relationship between the number of vertices and the number of edges of a binary tree.

9. Show the relationship between the number of vertices and the height of a balanced binary tree.

10. Explain what an Adaptor design pattern is? How to use a linked list to implement a stack and a queue?

11. Insert items with the following keys (in the given order) into an initially empty binary search tree, AVL tree, 2-4 tree, Red-Black tree, splay tree, and skip list, respectively: 30, 40, 50, 35, 45, 23, 42, 28. Draw the tree after each insertion.

12. Remove items with the following keys (in the given order) from the trees in previous question: 30, 50, 42, 35. Draw the tree after each insertion.

13. Show that the running time of the merge-sort algorithm is the lower bound on all comparison-based sorting algorithms.

14. Explain the Matrix Chain-product problem, and show how this problem can be solved using the dynamic programming method. What is the best way to multiply a chain of matrices with dimensions that are 10´5, 5´2, 2´20, 20´12, 12´4, and 4´60? Show your work.

15. Explain the Task Scheduling problem, and show how this problem can be solved in O(nlogn) time using the greedy method. Suppose you are given a set of tasks specified by pairs of the start times and finish times as T={(1,2), (1,3), (1,4), (2,5), (3,7), (4,9), (5,6), (6,8), (7,9)}. Solve the task scheduling problem for this set of tasks.

16. Explain the Fractional Knapsack problem, and show this problem can be solved using the greedy method. Let S={a, b, c, d, e, f, g} be a collection of objects with benefit-weight values as follows: a:(12,4), b:(10,6), c:(8,5), d:(11, 7), e:(14,3), f:(7,1), g:(9,6). What is an optimal solution to the Fractional Knapsack problem for S assuming we have a sack that can hold objects with total weight 18? Show your work.

17. Let G be a simple connected graph with n vertices and m edges. Explain why O(logm) is O(logn). Suppose we represent G with the edge list structure, why does the insertVertex method runs in O(1) time while the removeVertex method runs in O(m) time? Explain why the DFS traversal runs in O(n²) time if G is represented with the adjacency matrix structure.

18. Given a graph G, list the order in which the edges are labeled by the DFS and BFS traversal, respectively.

19. Given a directed graph G, draw the transitive closure, and compute a topological ordering.

20. Given a weighted graph and a vertex v, find the shortest path from v to all other vertices using Dijistra’s algorithm and Bellman-Ford algorithm, respectively.

21. Given a weighted graph, find a minimum spanning tree using Kruskal’ algorithm, Prim-Jarnik algorithm, and Baruvka’ algorithm, respectively.

22. Draw a flow network with 9 vertices and 12 edges (or given a flow network). Illustrate an execution of the Ford-Fullkerson algorithm on it to find the maximum flow.

23. Explain the following concepts: The forward and backward edges of an augmenting path; Residual capacity of a augmenting path; maximum flow; the capacity of a cut.

24. Given a text “aaabaadaabaaa” and a keyword (pattern) “aabaaa”, draw a figure illustrating the comparisons down by the brute-force pattern matching algorithm.

25. Given a text “aaabaadaabaaa” and a keyword (pattern) “aabaaa”, compute the last function for the Boyer-Moore algorithm and draw a figure illustrating the comparisons down by the Boyer-Moore pattern matching algorithm.

26. Given a text “aaabaadaabaaa” and a keyword (pattern) “aabaaa”, compute the failure function for the KMP algorithm where the alphabet is {a, b, c, d}, and draw a figure illustrating the comparisons down by the KMP pattern matching algorithm.

27. Explain what a NP-complete problem is, and how to prove that a problem is NP-complete.

28. A coloring of a graph G=(V,E) is a mapping C: VàS, where S is a finite set (of “colors”), such that if <v,w> is in E, then C(v)¹C(w); in other words, adjacent vertices are not assigned the same color. The graph coloring decision problem is defined as follows: Given G and a positive integer k, is there a coloring of G using at most k colors? Show that the graph coloring decision problem is in NP.

29. Explain the following concepts: approximate algorithm, an approximation ratio, polynomial-time approximation scheme, d-approximation algorithm

(For questions 18 through 22, you can use any graph in the textbook as the given graph)