Errata for Problem Solving with Algorithms and Data Structures using Python

Note: Throughout the text, some of the code listings contain a \ (backslash) character. This character is not a typo. It is used as a continuation character so that the line is not broken across physical lines in the text listing. They are necessary due to the maximum line size imposed by the page margins.

Chapter 1 - Introduction

• Page 7: The resources at the end of the chapter were left out. The list of references is found on page 347. A great place to learn more about Python is the python.org official website.
• Page 16: The string module does not have to be imported to use string methods
• Page 27: Two simple accessor methods should also be provided.

      1         def getNum(self):
      2            return self.num
      3            
      4         def getDen(self):
      5            return self.den

Chapter 2 - Stacks and Queues

• Page 68: TYPO-Third line from the bottom: Let's look again at to the operators... (to should be deleted)
• Page 69: Figure 2.8-The right most operator should be - instead of . (the margins cut the -)
• Page 95: Problem 5-Implement a queue such that the REAR of the queue is at the end of the list

Chapter 3 - Recursion

• Page 100: Listing 3.1 Since sum is a built-in function, it is probably not a good idea to use it as a variable name

Chapter 4 - Analysis, Sorting, and Searching

• Pages 131-133: In the timing examples we used time.clock(). There are other time and clock functions, for example time.time() and os.times(). However, the module documentation suggests that time.clock() should be used for benchmarking.
• Page 130,132,134: Listing 4.1, 4.3 Since sum is a built-in function, it is probably not a good idea to use it as a variable name
• Page 136: Figure 4.1 is simply not dark enough to see all of the graphs, especially the exponential.
• Page 142: Listing 4.9 (delete line 4) The variable stop is not used in this version.
• Page 163: Fifth line from the bottom-short should be sort.
• Section 4.4: Sorting: We assume there are no duplicate items in the list. Some implementations will require minor modifications to handle duplicate values.
• Thanks to Mark Fienup from the University of Northern Iowa for this modification to QuickSort. Commented lines are original.

    1 def quickSort(alist):
    2     quickSortHelper(alist,0,len(alist)-1)
    3 
    4 def quickSortHelper(alist,first,last):
    5     if first<last
    6         splitpoint = partition(alist,first,last)
    7         quickSortHelper(alist,first,splitpoint-1)
    8         quickSortHelper(alist,splitpoint+1,last)
    9         
   10 def partition(alist,first,last):
   11     pivotvalue = alist[first]
   12     leftmark = first+1
   13     rightmark = last
   14 
   15     done = False
   16 
   17     while not done:
   18 
   19 #        while leftmark <= rightmark and alist[leftmark] < pivotvalue: 
   20         while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
   21             leftmark = leftmark + 1
   22 
   23 #        while alist[rightmark] > pivotvalue and rightmark >= leftmark:
   24         while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
   25             rightmark = rightmark -1
   26 
   27         if rightmark < leftmark:
   28             done = True
   29         else:
   30             alist[leftmark],alist[rightmark]= alist[rightmark],alist[leftmark]
   31 
   32     alist[first],alist[rightmark]= alist[rightmark],alist[first]
   33 
   34     return rightmark
   35 
   36 
   37 
   38 
   39 
   40 

• Page 182: Problem #8 This improvement is typically used for quick sort, not merge sort. You might call the list length limit the "partition limit".

Chapter 5 - Trees

• Page 184: Figure 5.1 rightmost leaf should be HouseFly.
• Page 195: delete the last a on the first line.
• Page 196: Listing 5.8-the comma in getRootVal should be deleted-no other parameters
• Page 212: Listing 5.18-Add first line class TreeNode:
• Page 216: Listing 5.23-line 2 delete the 'd' in childrend
• Page 217: Figure 5.17 caption should read: Deleting Node 25 not 29
• Page 221: Listing 5.28 The else in line 33 needs a statement. Add 33.5: print "Trying to remove a non-existant node"

Page 221: Listing 5.28

• Listing in text does not correctly delete the root of a binary search tree

    1 def delete_key(self,key):
    2     if self.key == key:
    3         if not (self.leftChild or self.rightChild): # if no children
    4             if self == self.parent.leftChild:  # if I'm a left child
    5                 self.parent.leftChild = None
    6             else:
    7                 self.parent.rightChild = None
    8         elif (self.leftChild or self.rightChild) and \
    9                  (not (self.leftChild and self.rightChild)): # if one child
   10             if self.leftChild:  # if I have only a left child
   11                 if self.parent:  # if I'm not the root node
   12                     if self == self.parent.leftChild:
   13                         self.parent.leftChild = self.leftChild
   14                     else:
   15                         self.parent.rightChild = self.leftChild
   16                     self.leftChild.parent = self.parent
   17                 else:  # if I am the root node, slide up the left child
   18                     self.key = self.leftChild.key
   19                     self.payload = self.leftChild.payload
   20                     self.leftChild = self.leftChild.leftChild
   21                     self.rightChild = self.leftChild.rightChild
   22                     if self.leftChild:
   23                         self.leftChild.parent = self
   24                     if self.rightChild:
   25                         self.rightChild.parent = self
   26             else:  # if I have only a right child
   27                 if self.parent:  # if I'm not the root node
   28                     if self == self.parent.leftChild:
   29                         self.parent.leftChild = self.rightChild
   30                     else:
   31                         self.parent.rightChild = self.rightChild
   32                     self.rightChild.parent = self.parent
   33                 else:  # if I am the root node, slide up the right child
   34                     self.key = self.rightChild.key
   35                     self.payload = self.rightChild.payload
   36                     self.leftChild = self.rightChild.leftChild
   37                     self.rightChild = self.rightChild.rightChild
   38                     if self.leftChild:
   39                         self.leftChild.parent = self
   40                     if self.rightChild:
   41                         self.rightChild.parent = self
   42         else:  # if two children, then replace self with successor
   43             succ = self.findSuccessor()
   44             succ.spliceOut()
   45             self.key = succ.key
   46             self.payload = succ.payload
   47     else: # continue looking
   48         if key < self.key:
   49             if self.leftChild:
   50                 self.leftChild.delete_key(key)
   51             else:
   52                 print "trying to remove a non-existant node"
   53         else:
   54             if self.rightChild:
   55                 self.rightChild.delete_key(key)
   56             else:
   57                 print "trying to remove a non-existant node"
   58 

• Page 230: Figure 5.23 does not show the third swap, 27 and 17 should change positions
• Page 231: Listing 5.33-delete line 3: child is not used (it is subsumed by the condition in line 2)
• Page 231: Listing 5.33-also, lines 13-15 can be deleted as this case will never happen when called from percDown
• Page 231: Listing 5.34-Line Missing between 4 and 5: self.heapList.pop()

Chapter 6 - Graphs

• Page 244: Listing 6.1 needs to import the sys module import sys. Also, there is a continuation character missing in line 18
• Page 249: fourth line from bottom of page...being should be begin
• Page 252: Figure 6.8(b) The link from page to pope should really go from page to pale

Page 261: Listing 6.9

Although the dfs algorithm in the text works fine, the following recursive version of DFS is more appropriate for use with the topological sort.

00001: # DFS implementation using adjGraph where nodes contain an adj list reference to other nodes
00002: 
00003: time = 0
00004: 
00005: def dfs(theGraph):
00006:     for u in theGraph:
00007:         u.setColor('white')
00008:         u.setPred(-1)
00009:     time = 0
00010:     for u in theGraph:
00011:         if u.getColor() == 'white':
00012:             dfsvisit(u)
00013: 
00014: def dfsvisit(u):
00015:     global time
00016:     u.setColor('gray')
00017:     time = time+1
00018:     u.setDiscovery(time)
00019:     for v in u.getAdj():
00020:         if v.getColor() == 'white':
00021:             v.setPred(u)
00022:             dfsvisit(v)
00023:     u.setColor('black')
00024:     time = time + 1
00025:     u.setFinish(time)
00026: 

• Page 263: The recipe should be for 3/4 cup of milk and 1 cup of mix to match the diagrams
• Page 264: Step 2 in Topological sort: Save the vertices in a list in decreasing order of finish time.
• Page 266: Figure 6.19 should have a reflexive edge from C to C (not seen due to the color of the block)

Page 276: Listing 6.11

• The version of Prim's algorithm in listing 6.11 contains typos...missing parenthesis on getDistance in line 7. The cost method is actually called getCost (lines 11,13, and 14).

00001: def prim(G,w,start):
00002:     PQ = PriorityQueue()
00003:     for v in G:
00004:         v.setDistance(sys.maxint)
00005:         v.setPred(None)
00006:     start.setDistance(0)
00007:     PQ.buildHeap([(v.getDistance(),v) for v in G])
00008:     while not PQ.isEmpty():
00009:         u = PQ.delMin()
00010:         for v in u.getAdj():
00011:             if v in PQ and u.getCost(v) < v.getDistance():
00012:                 if v.getPred() != None:
00013:                     G.findEdge(v,v.getPred()).remove()
00014:                 v.setPred(u)
00015:                 v.setDistance(u.getCost(v))
00016:                 PQ.decreaseKey(v,u.getCost(v))

Chapter 7