CSE 7350/5350 D.W. Matula	Homework Set # 3	Due date: 22 March '05
	Total Points: 60
	Greedy Paradigm Applications
Grading Policy: Unless otherwise stated all problems are 10 points each. Partial credit is available on all problems. Late homework submitted within one week after the due date will incur a 10 point penalty on that homework set. (Videotape students add two weeks to deadlines.)

 

 

1. [FIFO Scheduling](15 points) Consider the greedy first-come first-serve coloring of interval graphs (see text problem 16.1-3, p. 379) where the n intervals all start and stop at integral times 0, 1, 2, …, t for t <= n. Intervals that overlap only at end points are not to be considered to yield edges in the interval graph. Describe an O (n) procedure for first building the event list data structure (described in class) from the list of intervals assumed given by start and stop times. Then describe and analyze an implementation of the coloring procedure employing the event list data structure that operates in O (n) time and space that colors with a minimum number of colors. Provide a walkthrough of your coloring algorithm for the graph with the event list abcbdecfegahiifjdhgj, where the first occurrence of each letter is its start time and the second occurrence its stop time.

 Provide an algorithm determining the degrees of all vertices in O (n) time from the event list for the interval graph. Walkthrough your algorithm for the above graph (provide a drawing of the graph).

 

 

 

 

 

2. [Matching Substrings] A matching substring pair of length k in a binary bit string b₁, b₂...b_n is a pair b_ib_i+1... b_i+k-1 = b_jb_j+1...b_j+k-1, with i not equal to j, of identical k-bit substrings.

(a) Determine a maximum length binary string with no matching substring pair of length 4.
(b) Describe the suffix tree algorithm for determining a longest matching substring pair and give its time and space complexity.

3. [Radix Conversion] Employ the DGT algorithm to convert representations as follows:

i) The values 90, 1000, and 3967 to the complete number systems with digit set {0, 1, 2} base 3, digit set {-4, -3, -2, -1, 0, 1, 2, 3, 4} base 9, digit set {-4, -2, -1, 0, 1, 2, 4} base 7, and digit set {-16, -8, -4, -2, -1, 0, 1, 2, 4, 8, 16} base 11.

ii) The value 4379 to all redundant representations in the redundant number systems with digit set {-2, -1, 0, 1, 2} base 4 and digit set {-7, -6, ..., 6, 7} base 8.

 

4. [Division] Divide the 16 digit value N by the six digit integer D obtaining the quotient Q and remainder (or sign of the remainder) R by the following division algorithms. Discuss your steps and method for obtaining the remainder (or remainder sign in (c)).

• (a) Long division (show only six digits of the answer with partial remainder);
• (b) Prescaled division (using a 4 digit reciprocal);
• (c) Convergence division (using a 4 digit reciprocal).

N = 2468097531086357

D = 427983

 

 

 

 

 

 

 

 

 

5. [Graph Degree Structures](15 points) Describe data and record structures for vertex ordering and vertex or edge coloring (or labeling) and a suitably greedy graph search algorithm to solve each of the following problems in the time bound indicated. Illustrate each algorithm with vertex or edge coloring (or labeling) on a graph or tree designed to teach your algorithm. The graph (or tree) should have at least 16 vertices and a maximum degree of at least 4. The graph should be connected with a minimum degree 3.

i) Find a maximum independent set in a tree in time O(|V|).

ii) Find a smallest last vertex ordering and a subgraph maximizing the minimum degree for your graph.

iii) Find some “k-connected” pair of vertices u, v in the graph having k = min {degree (u), degree (v)} edge disjoint distinctly colored (labeled) paths between u and v in time O (|V|+ |E|) using maximum adjacency search. Identify all the sets of pairwise k-edge-connected vertices using the "k-1 cycle" observation discussed in class.

Journal. [40 points](Due Date: 30 Apr. ’05) Prepare an 8-10 page journal of algorithm case studies summarizing the results of what you consider to be the most classic examples of algorithm design methodology. Classify your case studies as follows: I) Divide-and-Conquer; II) Dynamic Programming; III) Greedy; IV) Other. Within each class identify your case studies by application areas, specifically:

1.  Sorting/selection
2.  Graphs/network
3.  Arithmetic
4.  Computational geometry.
5.  Scheduling
6.  String matching/compression
7.  Other (distinct from 1-5)

 In total your survey should include some 30 to 50 case study summaries:
 For example:

 Paradigm: Divide-and-Conquer

 Field: Arithmetic

 Problem: n x n bit integer multiply.

 Result: 2n bit product in time complexity O (n ^ log₂3)

 Method: (One paragraph with highlights of method and illustration)

 Reference: (Textbook pages or other reference for more complete review)