CSE 7350/5350 D.W. Matula	Homework Set # 3	Due date: 27 March 2008
	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. (Distance students add two weeks to deadlines.)

---

1. [FIFO Scheduling](15 points) Consider the greedy first-come first-serve coloring of interval graphs, 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 from the list of intervals assumed given by start and stop times. The event list is a temporally ordered sequence with each interval occuring twice. The first occurrence of each interval is determined by its start time and the second occurrence by its stop time. 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.

[7350 only] 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).

Reference: Text Problem 16.1-3, p. 379

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 substrings of length 4.
(b) Describe the suffix tree algorithm for determining a longest matching substring pair and give its time and space complexity.

Reference: See notes on web page.

3. [Radix Representation] 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.

iii) The homework 3.3 notes on the homepage for the class illustrates the rooted graph giving the set of all carry save redundant representations for the 5-bit odd values 1, 3, ..., 31. Draw a similar graph for the borrow save redundant representations.

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

Reference: See notes on web page.

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 18 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.

Reference: For (ii) see web page Project Description for Exam Scheduling.
                    For (iii) see web page Project Description for Maximum Adjacency
                    Search and the example walkthrough.

Journal. [40 points](Due Date: 02 May 2008) 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.  Bioinformatics
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)