Part A. CLOSED BOOK (50 minutes) Complete and submit before starting

Part B.

A1. [4 points each] Give one or two sentence descriptions of each of the

following terms.

1. Sparse Matrix________________________________________________

2. Decision tree: _______________________________________________

3. Redundant digit set: __________________________________________

4. Data Structure Conversion: _____________________________________

5. Time Complexity: ____________________________________________

6. Algorithm Paradigm: __________________________________________

________________________________________________________________

A2. [18 points].Describe and contrast as succinctly as possible, the following three related disciplines.

1. Algorithm Engineering:

2. Algorithm Analysis:

3. Complexity Theory:

A3. [8 points each]. Give the best time complexity bound that you are aware of

for each of the following problems and give a couple of key words

identifying a method to achieve the result. The time complexity bound

should be for the worst case.

1. Determining the components of a graph: __________________________

2. Reordering an array of n numbers to correspond to a heap: ___________

________________________________________________________________

3. Converting an integer from octal to hex: ___________________________

4. Verifying a binary tree to be a binary search tree: __________________________

________________________________________________________________

5. Finding the two largest and the two smallest of a set of n numbers: _____

________________________________________________________________

A.4. (40 points) The following describes an oriented (rooted), ordered tree in parent array form, i.e., vertex 1 is the root and vertex p(i) is the parent of vertex i.

i	1	2	3	4	5	6	7	8	9	10	11	12	13	14
p(i)	0	1	1	1	2	2	3	4	6	8	8	9	11	11

(a) Draw the tree, and give the postorder traversal of the tree. Postorder traversal

(b) Give the leftmost-child, right-sibling representation of the tree.

(c) Considering the tree as a graph, give the adjacency list data structure representation of this tree, starting each list with the parent and then listing the children left-to-right.

(d) Give the time complexity for each of the following operations in each data structure for an oriented (rooted) ordered tree such as above. Assume the adjacency list starts with the parent and then lists the children left-to-right.

Operation	Parent Array	Leftmost child, right sibling	Adjacency list structure
Parent (of vertex x)	O (1)
Leftmost child (vertex x)
Right sibling (of vertex x)

PART B. (30 minutes) OPEN BOOK

(a) 1. [40 points] For the following list of positive integers (15, 3, 12, 5, 3, 2, 11, 7, 1, 20), the smallest missing integer is 4 and the smallest missing consecutive pair of integers is 8, 9. In general, given a list of n integers p₁, p₂, …, p_n where 1 £ pi £ k for all 1 £ i £ n, describe an algorithm for finding the smallest positive integer and smallest pair of consecutive positive integers not in the list. Describe the time and space complexity of your algorithm in terms of n and/or k. Can you argue that your algorithm achieves the best possible time or space behavior for this problem?

(10 point follow-up; only for the 7350 students) Assume the maximum integer value k is not known (i.e., can be much greater than n). How does this effect your solution? Can you give a revision to handle this case so that the resources depend only on n (just discuss)?

NOTE: You may just describe your algorithm briefly without writing step-by-step implementation. Your discussion will be graded on clarity, succinctness, correctness, and appropriate algorithm efficiency analysis.