Essay writing (2-3 paragraph)

Homework 6_2

Answer the following questions: (10 point each)

1. For each of the sequence w = <e1, . . . , elast> below, determine whether they are subsequences of the following data sequence:

<{A, B}{C, D}{A, B}{C, D}{A, B}{C, D}>

subjected to the following timing constraints:

mingap = 0 (interval between last event in ei and first event in ei+1 is > 0)

maxgap = 2 (interval between first event in ei and last event in ei+1 is ≤ 2)

maxspan = 6 (interval between first event in e1 and last event in elast is ≤ 6)

ws = 1 (time between first and last events in ei is ≤ 1)

a. w = < {A}{B}{C}{D}> Answer:

b. w = < {A} {B, C, D} {A}> Answer:

c. w = < {A} {A,B, C, D} {A}> Answer:

d. w = < {B, C} {A, D} {B, C}> Answer:

e. w = < {A, B, C, D} {A, B, C, D}> Answer:

2. Draw all candidate subgraphs obtained from joining the pair of graphs shown in Figure below Assume the edge-growing method is used to expand the subgraphs.

Answer:

2