Algorithms For Dummies

 

»

A diagonal backward movement hints at a substitution in the first string if the 

letters on the row and column differ (otherwise, no edit needs to be done)

 

»

An upward movement dictates a deletion of a letter in the first string

 

»

A left backward move indicates that an insertion of a new letter should be 

done on the first string

In this example, the backtracking points out the following transformations (two 

deletions and one substitution):

Saturday => Sturday => Surday => Sunday

FIGURE 16-2: 

Transforming 

Sunday into 

Saturday.

---

320

 

   

  PART 5 

 Challenging Difficult Problems

FIGURE 16-3: 

Highlighting what 

transformations 

are applied.

---

CHAPTER 17

  Using Randomized Algorithms 

     321

IN THIS CHAPTER

 

» Understanding how randomness can 

prove smarter than more reasoned 

ways