CSE 5350/7350 Due
Date:
D.W. Matula
28 Sept. MMVI
Homework
Set # 2
Data
Structure Engineering for Algorithm Design
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](13 + 2 points). Design and analyze an
on-the-fly algorithm for converting a binary search tree to an ordered doubly
linked list following the inorder traversal of the
data. Utilize a loop invariant (text p.17) to argue the correctness of your
algorithm. 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 = 59, 83, 68, 40, 82, 54, 88, 33, 19, 50, 75, 17.
2 [Decision Tree]
a. Construct a decision tree that finds the median of 5 elements in at most 6 comparisons. What is the average case number of comparisons for your solution?
b. Construct a decision tree for inserting 5 numbers into a heap that employs the smallest number of comparisons:
(i) in the worst case,
(ii) in the average
case.
3. [Heapify](13 + 2 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 six element list: a1, a2, a3, a4,
a5, a6.What is then the worst case and average case
number of comparisons to Heapify six 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. [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.
4.
[Graph (Matrix) Reordering](13 + 2 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 - 4 graph.
Reorder by determining a maximum adjacency search order(see Project 1(a) on class homepage) with "ties"
broken lexicographically.
HW2 - 4 graph in adjacency list form:
o a: c, f, g, h;
o b: c, d;
o c: a, b, g, h;
o d: b, e, f, h;
o e: d, f, h;
o f: a, d, e, g;
o g: a, c, f;
o h: a, c, d, e.
5. [Sparse matrix
multiplication](13 + 2 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 << n2. 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 4. 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
o 1: 3, 5, 7
o 2: 4, 8
o 3: 5, 8
o 4: 2, 6
o 5: 1, 2, 7, 8
o 6: 3
o 7: 1, 5, 6
o 8: 6, 7
6. [Table compression] (13 + 2)[Ref: Proc. 17th Symp. Computer Arithmetic, IEEE, June 2005, pp. 156-163].