|
|
| Page | 3/24 | | Date | 03.05.2017 | | Size | 186.06 Kb. |
| - 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
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);
- 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
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
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
Share with your friends: |
|
|
