Solution for HW 4, CS 3114, Spring 2018
------------------------------------------------------------------------------------
Q1:
a b c d e f g h i j k node added / distance
--------------------------------------------------------------------------------
0 x x x x x x x x x x
add 5 3 1 x x x x x x x a / 0
4 2 add x x 4 x x x x d / 1
3 add x 7 4 x x x x c / 2
add 5 7 4 x x x x b / 3
5 7 add x x x x g / 4
add 6 7 x x x e / 5
add 7 9 12 x f / 6
add 9 12 10 h / 7
add 10 10 i / 9
add 10 j / 10
add k / 10
Q2:
Pass 1:
a --> b --> e --> h
<-- add h
<-- add e
<-- add b
a --> c --> d
<-- add d
c --> g --> j --> i --> k
<-- add k
<-- add i
<-- add j
<-- add g
<-- add c
a --> f
<-- add f
<-- add a
So a solution is: a f c g j i k d b e h
Q3:
a) Algorithm:
Sort S into ascending order, alphabetically.
Traverse S linearly (sorting does not help at this point);
for each string Z in S, search S for the reversal of Z (sorting
would allow using binary search here).
Cost, excluding sorting:
Theta( N log N) since we do N binary searches on S
b) Algorithm:
Sort S based on the reversals of the strings in S.
Binary search S for X; a match indicates X is in S, and X is a
suffix of itself; otherwise the search will either terminate at
string that has X as a suffix, or at a string that does not have
X as a suffix.
Cost, excluding sorting:
Theta(log N) since we do a single binary search on S
c) Algorithm:
Sort S alphabetically.
For each prefix of X, binary search S for the prefix; if that is
found, then binary search S for the rest of X; it that is found,
we have a match, if not, extend the prefix by one character and
repeat.
Cost, excluding sorting:
Theta( length(X) * log N )
d) Algorithm:
For each string Z in S, perform a substring search for X. This
can be optimized by not comparing against strings in S that are
shorter than X, and one could optimize that by first sorting S
based on the lengths of strings.
Cost, excluding sorting:
Theta( N * cost of substring operation )