- [20 Pts] During computer processor manufacturing, distances among transistors are minimized so that higher speeds can be achieved with low power consumption. The following diagram shows a source and connection between transistors. The source needs to send signals to all transistors that minimizes the travelling distance of the signal. Determine the connection paths in the circuit so that all the transistors are connected and a signal from the source can reach all the transistors by traveling minimum distance to reach each transistor from the source.
- a) Identify the best suitable algorithm from the four algorithms given in solving this problem (Bellman-Ford, Dijkstra, Prims, Kruskals). Justify your selection.
b)Apply the algorithm identified above in designing the best circuit. Clearly show how you arrived that your solution by showing intermediate steps.
- Dynamic Programming [20 Pts]
[12 Pts] Longest Common Subsequence [LCS] : In order to determine the LCS, first we create the table
| LCS-LENGTH(X, Y) /* computes the length of an LCS of X and Y */m = length(X) n = length(Y)for i = 0 to m do /* initialize trivial */ c[i, 0] = 0 /* subproblems */ for j = 1 to n doc[0, j] = 0for i = 1 to m do for j = 1 to n doif xi = yj thenc[i, j] = c[i-1, j-1]+1 /* case xi = yj */elseif c[i-1, j] > c[i, j-1] then c[i, j] = c[i-1, j]elsec[i, j] = c[i, j-1]return c[m, n] |
C[i,j] that determine the length of a longest common subsequence of two sequences. Using the table C[i,j] we can construct a LCS. The following algorithm can be used to create the table C[i,j]
- a) Determine the length of the LCS (Longest common subsequence) of following two sequences by constructing C[i, j] table. Make sure you indicate all the distances and bridges properly. Sequence X should be in rows and the sequence Y should be columns in C[i, j] table.
X=ABCMB, Y=ACMXB
b)Using table C[i,j] above, construct a longest common subsequence. Clearly show how you traversed the table above to determine the LCS.
Reviews
There are no reviews yet.