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



Download 186.06 Kb.
Page3/24
Date03.05.2017
Size186.06 Kb.
1   2   3   4   5   6   7   8   9   ...   24

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?
      • Linked List
        • 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

Download 186.06 Kb.

Share with your friends:
1   2   3   4   5   6   7   8   9   ...   24




The database is protected by copyright ©sckool.org 2020
send message

    Main page