SUNY Geneseo Department of Computer Science

Introduction to Backtracking

Return to List of Lectures

Questions?

Dynamic Programming Question from Exam

Casino with n games played in increasing order, game i wins $w_i, moving from game i to j costs $m_ij

W(i) = max expected winnings for playing game i and later

• = w_i + max( (max | n ≥  j > i : W(j) - m_ij ), -m_i∞ ) if i < n
• = w_n - m_n∞ if i = n

Answer is W(0), with w₀ defined as the money you enter with

Algorithm

    let W[0..n] be a new array
    W[n] = wn - mn∞
    for i = n-1 down to 0
        q = -mi∞
        for j = i+1 to n
            if W[j] - mij > q then q = W[j] - mij
        W[i] = q
    return W[0]

Breaking Substitution Ciphers

Systematically replace each letter of the alphabet with some other to convert plaintext to ciphertext

For example

• A -> C
• B -> A
• C -> D
• D -> B
• “A BAD CAD” -> “C ACB DCB”

Breaking a substitution cipher is essentially search for the right reverse substitution

How might you do this algorithmically?

• Dictionary needs to be large and fast
• Initial algorithm ideas

        for w = 1 to number of words
            l = length of word w
            for each word X of length l in dictionary
                try substituting X for word i until a substitution “succeeds” (i.e., no contradiction, user accepts phrase)
            if nothing succeeded, go back to word w-1 (backtrack)

Recursion makes backtracking easier to realize

    boolean solve( w, ciphertext, dictionary, substitutions )
            // true = solved, false = not solved
        if w > length of ciphertext
            offer substitutions to user
            if user accepts
                return true
            else
                return false
        else
            l = length of word w
            for each X of length l in dictionary
                update substitutions, checking for contradictions
                if update possible
                    if solve( w+1, .... )
                        return true
            return false

Next

Algorithmic knowledge for breaking substitution ciphers

• Hash tables for dictionaries
• Backtracking for search
• 2-part programming assignment

For Tuesday: Hash tables

• Chapter 11 up to but not including “Analysis of hashing with chaining”
• Page 253 through middle of 258