# These notes are intended for use by students in cs1501 at the University of Pittsburgh and no one else

 Page 3/24 Date 03.05.2017 Size 186.06 Kb. #18863

## Finding Words in a Boggle Board

• Naturally, not all recursive calls may be possible
• We cannot go back to the previous letter since it cannot be reused
• Note if we could words could have infinite length
• We cannot go past the edge of the board
• We cannot to to any letter that does not yield a valid prefix to a word
• Practically speaking, this will give us the greatest savings
• For example, in the board shown (based on our dictionary), no words begin with FY, so we would not bother proceeding further from that prefix
• Execution tree is pruned here as well
• Show example on board

## Assignment 1 Note

• Building a crossword puzzle is yet another problem
• In this case words are only in a straight line across or down
• However, words affect each other
• Choice of a word in one direction could affect many words in the other direction
• For more details go to recitation

## Implementation Note

• Since a focus of this course is implementing algorithms, it is good to look at some implementation issues
• Consider building / unbuilding strings that are considered in the Boggle game
• Forward move adds a new character to the end of a string
• Backtrack removes the most recent character from the end of the string
• In effect our string is being used as a Stack – pushing for a new letter and popping to remove a letter

## Implementation Note

• We know that Stack operations push and pop can both be done in Θ(1) time
• Unfortunately, the String data type in Java stores a constant string – it cannot be mutated
• So how do we “push” a character onto the end?
• In fact we must create a new String which is the previous string with one additional character
• This has the overhead of allocating and initializing a new object for each “push”, with a similar overhead for a “pop”
• Thus, push and pop have become Θ(N) operations, where N is the length of the string
• Very inefficient!

## Implementation Note

• For example:
• S = new String(“ReallyBogusLongStrin”);
• S = S + “g”;
• Consider now a program which does many thousands of these operations – you can see why it is not a preferred way to do it
• To make the “push” and “pop” more efficient (Θ(1)) we could instead use a StringBuffer (or StringBuilder)
• append() method adds to the end without creating a new object
• Reallocates memory only when needed
• However, if we size the object correctly, reallocation need never be done
• Ex: For Boggle (4x4 square)
• S = new StringBuffer(16);

## Review of Searching Methods

• Consider the task of searching for an item within a collection
• Given some collection C and some key value K, find/retrieve the object whose key matches K
• Z
• J
• P
• K
• Q
• K

## Review of Searching Methods

• How do we know how to search so far?
• Well let's first think of the collections that we know how to search
• Array/Vector
• Unsorted
• How to search? Run-time?
• Sorted
• How to search? Run-time?
• Unsorted
• How to search? Run-time?
• Sorted
• How to search? Run-time?

## Review of Searching Methods

• Binary Search Tree
• Slightly more complicated data structure
• Run-time?
• Are average and worst case the same?
• So far binary search of a sorted array and a BST search are the best we have
• Both are pretty good, giving O(log2N) search time
• Can we possibly do any better?
• Perhaps if we use a very different approach

## Digital Search Trees

• Consider BST search for key K
• For each node T in the tree we have 4 possible results
• T is empty (or a sentinel node) indicating item not found
• K matches T.key and item is found
• K < T.key and we go to left child
• K > T.key and we go to right child
• Consider now the same basic technique, but proceeding left or right based on the current bit within the key

## Digital Search Trees

• Call this tree a Digital Search Tree (DST)
• DST search for key K
• For each node T in the tree we have 4 possible results
• T is empty (or a sentinel node) indicating item not found
• K matches T.key and item is found
• Current bit of K is a 0 and we go to left child
• Current bit of K is a 1 and we go to right child
• Look at example on board

## Digital Search Trees

• Run-times?
• Given N random keys, the height of a DST should average O(log2N)
• Think of it this way – if the keys are random, at each branch it should be equally likely that a key will have a 0 bit or a 1 bit
• Thus the tree should be well balanced
• In the worst case, we are bound by the number of bits in the key (say it is b)
• So in a sense we can say that this tree has a constant run-time, if the number of bits in the key is a constant
• This is an improvement over the BST

## Digital Search Trees

• But DSTs have drawbacks
• Bitwise operations are not always easy
• Some languages do not provide for them at all, and for others it is costly
• Handling duplicates is problematic
• Where would we put a duplicate object?
• Follow bits to new position?
• Will work but Find will always find first one
• Actually this problem exists with BST as well
• Could have nodes store a collection of objects rather than a single object