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 )