CSE 5350/7350                                                                       Due Date:

D.W. Matula                                                                           Feb. 24, 2004

Homework Set # 2

Data Structure Engineering for Algorithm Design

(Revised: Feb. 05. 2004)

Data Structures deals with the representation and organization of data to support efficient:

·        storage

·        access

·        execution of operations

·        display of results.  

1.  [Data structure conversion](15 points). Design and analyze an algorithm for converting a binary search tree to an ordered doubly linked list following the inorder traversal of the data. Have your algorithm use as little extra space as possible, with "in place" the goal. Perform a walkthrough for the sequence S where the elements of S are first processed left-to-right to build the search tree. Then apply your algorithm to convert the binary search tree to a doubly linked list, showing the status of the conversion at each node of the search as it is consumed and moved into the doubly linked list.

S = 61, 36, 81, 13, 42, 21, 52, 12, 15, 73, 92.

2.  [Heapify](15 points). The array form of a heap (i.e. a binary heap array) has the children of the element at position i in positions (left @ 2i, right @ 2i+1). For a balanced ternary heap array the three children of the element at position i are at positions (left @ 3i-1, middle @ 3i, right @ 3i+1). The term "Heapify" refers to the algorithm that builds a binary heap array from right-to-left (leaf-to-root in binary tree form) given the size of the array to be built. The term "Ternary Heapify" here refers to the analogous algorithm that builds a balanced ternary heap array in right-to-left order.

            a. Heapify the sequence S of Problem 1, and give the number of comparisons required.

            b. Do the same as (a) for Ternary Heapify.

c. Build the decision tree determined by the comparisons employed to Heapify a seven element list: a1, a2, a3, a4, a5, a6, a7.What is then the worst case and average case number of comparisons to Heapify seven elements? Is this optimal in either case?

d. Do the same as (c) for Ternary Heapify.

e. Determine the smallest value for the constant c for right-to-left Heapify comparisons (valid for all n) and support your result.

f. Same as (e) for Ternary Heapify. 

g. [5 point bonus (optional)] Count the number of distinct heap and ternary heap structures for n = 1, 2, ..., 25. Determine good lower bound constants c2, c3, where any heap building procedure, respectively ternary heap building procedure, must make at least c2n + O(1), respectively c3n + O(1), comparisons using the decision tree model.

3.  [Graph (Matrix) Reordering](15 points). Let the adjacency list representation of a graph ( 0, 1  symmetric matrix ) be given by a packed edge list. Describe an algorithm for reordering the edge list in place so all adjacency lists follow a new vertex ordering given by a permutation p(1), p(2), ..., p(n). Apply your algorithm to the graph given by the packed edge list stored as example HW2 - 3 graph. Reorder by determining a maximum adjacency search order with "ties" broken lexicographically.    

HW2 - 3 graph in adjacency list form:

4.  [Sparse matrix multiplication](15 points). Describe an efficient sparse matrix multiplication procedure for two n x n matrices stored in "adjacency list" form. Assume matrix A has mA non zero entries and matrix B has mB non zero entries, with n << mA << mB. Describe why your algorithm will generate the n × n matrix product in adjacency list form in time O (n mA).

            Apply your algorithm for multiplying the two 8 × 8  0,1 matrices A1, B1 where A1 is given by the following adjacency list of unit entries and B1 is given by the adjacency list of  unit entries of  Problem 3. Count the actual number of multiplications used in this matrix product and explain why it is considerably less than the bound n mA (which is 8 × 19 =152) in this case.

Adjacency List For 0,1 Matrix A1

5.  (7350 only)[Multiplier recoding]. Design and analyze an algorithm for "Booth" multiplier recoding where the input operand is a borrow-save number using the redundant binary digit set {-1,0,1} and the output is the number converted to the radix 4 digit set {-2, -1, 0, 1, 2}. Your solution should avoid conversion to standard binary as an intermediate step and operate in time independent of the digit length of the operand.

5.  (5350 only)
a.[Dynamic Set Operation Implementation] Text problem 10-1, page 217.

b.[Lexicographic Ordering] Text problem 12-2, page 269.