Transcript Power Point XP

Assignment 5 Debrief
Andy Wang
Data Structures, Algorithms,
and Generic Programming
Word Ladder Game
Idea: Find a way to transform one
word to another through words that
are one character away
Example: bunny  tiger
bunny  funny  funky  funks 
finks  fines  tines  tiles  tiler
 tiger
Bunny to Tiger?
Brute Force Approach
start
atart..ztart, saart..smart..szart, start..stzrt, staat..stazt, stara..starz
d
amart..zmart, saart..szart, smart..smzrt, smaat..smazt, smara..smarz
…
n = number of words in a dictionary
Speed complexity: O(ad), a = 5*26
Space complexity: O(n)
Brute Force Approach
Speed complexity: (26*5)d
Suppose d = 4, we need 300,000,000
steps
Space complexity:
5 char/word * 5000 words = 25,000
characters
Adjacency Graph Approach
Idea: go through only words that are
one character away
dear
bear, fear,.., year, dear, dead
dear, fear, …year, boar, beer, bead…beap
…
Adjacency Graph Approach
Need to build an adjacency graph
bear: dear, fear, …year, boar, beer,
bead…beap
dear: bear, fear,.., year, dear, dead
Need to avoid revisiting the same
words
Do a BFS to find the shortest path
Building the Adjacency Graph
For each word, do pair-wise
comparisons against all words
If a word is one character away,
append to its list
n = number of words in a dictionary
Speed complexity: O(n2)
Space complexity: O(n2)
Building the Adjacency Graph
Speed complexity
5 comparisons to determine a word is
one character away
For each word, it needs to perform 5
comparisons/word * 5,000 words =
25,000 comparisons
For 5,000 words, we need 125,000,000
comparisons
best case = average case = worst case
Building the Adjacency Graph
Space complexity
If every word is one character away from
every word in a dictionary…
We need 5 char/word * 5,000 words *
5,000 words = 125,000,000 characters
(worst case)
Average case: ~130,000 characters
(from empirical measurements)
Can We Do Better?
O(n) speed?
Visualizing the Solution Space
Try a simpler case
Three-letter words
Visualize ‘cat’
Visualizing (c, a, t)
a
c
(c, a, t)
t
Visualizing (c, a, t)
a
c
(c, a, t)
t
(r, a, t)
r
Visualizing (c, a, t)
(b, a, t)
(r, a, t)
(c, a, t)
a
t
You can make words that are one
character apart by collapsing one of
the dimensions
Collapsing the Solution Space?
Idea: Use hashing
Create map<string, set<string>>
For cat, hash the following
*at
c*t
ca*
After processing bat, cat, and rat
map[“*at”] will contain bat, cat, and rat
Hash-Based Graph Construction
Speed complexity: O(n)
5 char/word * 5000 words = 25,000
hashing operations
Space complexity: O(n)
5 char/word * 5000 words = 25,000
characters
Modified BFS
Each word expands into several lists
dear
*ear, d*ar, de*r, dea*
(bear, fear,.., year, dear, dead)
*ear, b*ar, be*r, bea*
(dear, fear, …year, boar, beer, bead…beap)
…
BFS Complexity
Speed complexity: O(n + edges)
Since each word is visited at most once
Storage complexity: O(n)