Analysis of Python Data Structures and Algorithms (2nd Edition) - Chapter 4 Recursion and Chapter 5 Searching and Sorting
Chapter 4 Recursion
4.2.2 The Three Principles of Recursion
- A recursive algorithm must have a base case
- A recursive algorithm must change its state and move closer to the base case
- A recursive algorithm must recursively call itself
4.2.3 Convert integers to strings of arbitrary bases
def toStr(n , base):
convertString = "0123456789ABCDEF"
if n < base:
return convertString[n]
else:
return toStr(n // base,base) + convertString[n % base]
x = 12
print(toStr(x,2))
4.4 Recursive visualization
- Draw spirals recursively using turtle module
from turtle import *
myTurtle = Turtle()
myWin = myTurtle.getscreen()
def drawSpiral(myTurtle,lineLen):
if lineLen > 0:
myTurtle.forward(lineLen)
myTurtle.right(90)
drawSpiral(myTurtle,lineLen - 5)
drawSpiral(myTurtle,100)
myWin.exitemclick()
- draw fractal tree
from turtle import *
myTurtle = Turtle()
myWin = myTurtle.getscreen()
def tree(branchLen,t):
if branchLen > 5:
myTurtle.forward(branchLen)
myTurtle.right(20)
tree(branchLen - 15,myTurtle)
myTurtle.left(40)
tree(branchLen - 10,myTurtle)
myTurtle.right(20)
myTurtle.backward(branchLen)
myTurtle.left(90)
myTurtle.up()
myTurtle.backward(300)
myTurtle.down()
myTurtle.color("green")
tree(110,myTurtle)
myWin.exitonclick()
- Draw the Sierpinski triangle
from turtle import *
def drawTriangle(points,color,myTurtle):
myTurtle.fillcolor(color)
myTurtle.up()
myTurtle.goto(points[0])
myTurtle.down()
myTurtle.begin_fill()
myTurtle.goto(points[1])
myTurtle.goto(points[2])
myTurtle.goto(points[0])
myTurtle.end_fill()
def getMid(p1,p2):
return ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2)
def sierpinski(points , degree , myTurtle):
colormap = ["blue","red","green","white","yellow","violet","orange"]
drawTriangle(points,colormap[degree],myTurtle)
if degree > 0:
sierpinski([points[0],
getMid(points[0],points[1]),
getMid(points[0],points[2],)],
degree - 1,
myTurtle
)
sierpinski([points[1],
getMid(points[0], points[1]),
getMid(points[1], points[2], )],
degree - 1,
myTurtle
)
sierpinski([points[2],
getMid(points[2], points[1]),
getMid(points[0], points[2], )],
degree - 1,
myTurtle
)
myTurtle = Turtle()
myWin = myTurtle.getscreen()
myPoints = [(-500,-250),(0,500),(500,-250)]
sierpinski(myPoints,5,myTurtle)
myWin.exitonclick()
4.5 Complex recursion problems
- Tower of Hanoi
Solving the Tower of Hanoi problem with Python
def moveDisk(fromPole, toPole):
print("Moving disk from %d to %d" % (fromPole,toPole))
def moveTower(height , fromPole , toPole , withPole):
if height >= 1:
moveTower(height - 1,fromPole,withPole,toPole)
moveDisk(fromPole,toPole)
moveTower(height - 1,withPole,toPole,fromPole)
if __name__ == '__main__':
plate = 5
moveTower(5,1,3,2)
4.6 Exploring the maze
Recursive solution
4.7 Dynamic Programming
Classic problem: changing coins
Suppose a vending machine manufacturer wants to give out the fewest coins per transaction.
A customer uses a one dollar bill to buy an item worth 37 cents. How many coins do you need to give to the customer?
Answer: 6 [2 for 25 cents, 1 for 10 cents, 3 for 1 cent]
Greedy Algorithm: Start with the highest denomination coin (25 cents), use as many coins as possible, then use the second largest denomination coin as much as possible → try to solve the problem to the greatest extent possible.
- Solve the change problem using recursion
def recMC(coinValueList,change):
minCoins = change
if change in coinValueList:
return 1
else:
for i in [c for c in coinValueList if c <= change]:
numCoins = 1 + recMC(coinValueList,change - i)
if numCoins < minCoins:
minCoins = numCoins
return minCoins
# Coin Type
coins = [1,5,10,25]
# need to make up
target = 63
print(recMC(coins,target))
67716925 recursive calls to find the optimal solution
- Solving the Change Problem Using Dynamic Programming
def dpMakeChange(coinValueList , change , minCoins):
for cents in range(change - 1):
coinCount = cents
for j in [c for c in coinValueList if c <= cents]:
if minCoins[cents - j] + 1 < coinCount:
coinCount = minCoins[cents - j] + 1
minCoins[cents] = coinCount
return minCoins[change]
- Likou 322. Change Exchange
You are given an array of integers coins , representing coins of different denominations; and an integer amount , representing the total amount.
Calculates and returns the minimum number of coins required to make up the total amount. Returns -1 if none of the coin combinations make up the total amount.
You can think of an infinite amount of each type of coin.
answer
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [float('inf')] * (amount + 1)
# dp[i] represents the minimum number of coins needed to make i dollars
dp[0] = 0 # Gather 0 yuan, not a single coin
# Final thoughts
for coin in coins:# Iterate over all coin types
for i in range(coin , amount + 1): # Starting from the current coin type, i represents the amount to be collected
# dp[number of amount - current coin] represents the number of coins needed to make up the amount of [ ] after removing the coin, and then calculate the minimum value with dp[i]
dp[i] = min(dp[i] , dp[i - coin] + 1)
if dp[amount] != float("inf"):
return dp[amount]
else:
return - 1
Chapter 5 Searching and Sorting
5.2.1 Sequential search of unordered list (time complexity O(n))
def sequentialSearch(alist,item):
pos = 0
found = False
while pos < len(alist) and not found:
if alist[pos] == item:
found = True
else:
pos = pos + 1
return found
myList = [1,7,4,5,2]
target = 4
print(sequentialSearch(myList,target))
Sequential search of an unordered list, omitted
5.2.2 Binary search
- Recursive version (time complexity is logarithmic)
def binnarySearch(alist,item):
if len(alist) == 0:
return False
else:
midpoint = len(alist) // 2
if alist[midpoint] == item:
return True
else:
if item < alist[midpoint]:
return binnarySearch(alist[:midpoint],item)
else:
return binnarySearch(alist[midpoint:],item)
myList = [1,2,3,4,5]
target = 4
print(binnarySearch(myList,target))
5.2.3 Hashing
By hashing, a data structure can be constructed with a time complexity of O(1) for finding the target element
Hash table: A collection of elements in which the elements are stored in a way that is easy to find, each position in the hash table is often called a slot, in which an element can be stored. Integer marks each slot starting from 0.
A hash function associates elements in a hash table with where they belong.
For any element in the hash table, the hash function returns an integer between 0 ~ m-1 [m is the number of elements]
-
remainder function: use remainder as hash value: i.e. use element % size of table
The slot occupancy is called the load factor λ = number of elements / hash table size
When searching for the objective function, just use the hash function to calculate the slot number and see if there is a value in the corresponding slot.
Sometimes a hash function will put two elements into the same slot → collision (collision)
1. Hash function
Given a set of elements, each element can be mapped to a different slot, such a hash function is called a perfect hash function.
One way to build a perfect hash function is to grow the hash table so that it can hold each element, so that each element has its own slot [possibly wasted space]
Goal: Create such a hash function: the number of collisions is minimal, the calculation is convenient, and the elements are evenly distributed in the hash table.
→ Extended remainder function
- folding method
- square method
! The hash function must be efficient so that it does not become a burden on the storage and search process. If the hash function is too complex, computing the slot number may be more work than when doing a sequential or binary search, which is not what hashing is intended for.
2. Handling conflicts
When two elements are assigned to the same slot, there must be a systematic approach to placing the second element in the hash table
-
Open addressing: try to find the next empty slot or address in the hash table → aka linear probing
Disadvantage: Aggregation phenomenon. If there are too many collisions in one slot, linear probing will fill up the slots near it.
-
Extended Linear Probing
Rehashing: generally refers to the process of finding another slot after a collision.
-
Square detection
Instead of taking a fixed stride, the hash value is incremented by a re-hash function
-
Chaining method: Allows multiple elements to exist in the same position in the hash table. Conflict occurs, still insert [chain]
3. Implement mapping abstract data types
Python implements the HashTable class with two lists
class HashTable:
def __init__(self):
#Specifies the initial size of the hash table
self.size = 11
self.slots = [None] * self.size
self.data = [None] * self.size
def put(self,key,data):
hashvalue = self.hashfunction(key,len(self.slots))
if self.slots[hashvalue] == None:
self.slots[hashvalue] = key
self.data[hashvalue] = data
else:
if self.slots[hashvalue] == key:
self.data[hashvalue] = data
else:
nextslot = self.rehash(hashvalue,len(self.slots))
while self.slots[nextslot] != None and self.slots[nextslot] != key:
nextslot = self.rehash(nextslot,len(self.slots))
if self.slots[nextslot] == None:
self.slots[nextslot]= key
self.data[nextslot] = data
else:
self.data[nextslot] = data
def get(self,key):
startslot = self.hashfunction(key,len(self.slots))
data = None
stop = False
found = False
position = startslot
while self.slots[position] != None and not found and not stop:
if self.slots[position] == key:
found = True
data = self.data[position]
else:
position = self.rehash(position,len(self.slots))
if position == startslot:
stop = True
return data
def __getitem__(self, key):
return self.get(key)
def __setitem__(self, key, data):
self.put(key,data)
def hashfunction(self,key,size):
return key % size
def rehash(self,oldhash,size):
return (oldhash + 1) % size
4. Analyze the hash search algorithm
5.3 Sorting
5.3.1 Bubble sort
Bubble sort iterates over the list multiple times. It compares adjacent elements and will swap out of order. Each round of traversal puts the next maximum value in the correct position. Essentially, each element finds its place by "bubbling up".
- Python implements bubble sort
def bubbleSort(alist):
for passnum in range(len(alist) - 1, 0 ,-1):
for i in range(passnum):
if alist[i] > alist[i + 1]:
temp = alist[i]
alist[i] = alist[i+1]
alist[i+1] = temp
5.3.2 Selection sort
Selection sort improves upon bubble sort by doing only one exchange each time the list is traversed. To achieve this, selection sort looks for the maximum value on each pass, and puts it in the correct position after the pass.
- Python implements selection sort
def selectionSort(alist):
for fillslot in range(len(alist - 1),0,-1):
positionOfMax = 0
for location in range(1,fillslot + 1):
if alist[location] > alist[positionOfMax]:
positionOfMax = location
temp = alist[fillslot]
alist[fillslot] = alist[positionOfMax]
alist[positionOfMax] = temp
5.3.3 Insertion Sort
Maintain an ordered sublist at the lower end of the list, and "insert" each new element into this sublist one by one. Figure 5-16 shows the process of insertion sort.
- Python implements insertion sort
def insertionSort(alist):
for index in range(1,len(alist)):
currentvalue = alist[index]
position = index
while position > 0 and alist[position -1 ] > currentvalue:
alist[position] = alist[position - 1]
position = position - 1
alist[position] = currentvalue
5.3.4 Hill sort
Hill sort, also known as "decrement-increment sort", improves insertion sort by dividing the list into several sublists and applying insertion sort to each sublist. How to split the list is the key to Hill sorting - not continuous splitting, but using increment i (sometimes called step size) to select all elements with interval i to form a sublist.
- Implementing Hill Sorting Using Python
def gapInsertionSort(alist, start, gap):
for i in range(start + gap,len(alist),gap):
currentvalue = alist[i]
position = i
while position >= gap and alist[position - gap] > currentvalue:
alist[position] = alist[position - gap]
position = position - gap
alist[position] = currentvalue
def shellSort(alist):
sublistcount = len(alist) // 2
while sublistcount > 0:
for startposition in range(sublistcount):
gapInsertionSort(alist,startposition,sublistcount)
print("After increments of size",sublistcount,"The list is ",alist)
sublistcount = sublistcount // 2
5.3.5 Merge Sort
A recursive algorithm that splits a list in two at a time. If the list is empty or has only one element, it is ordered by definition (the base case). If the list has more than one element, split the list in two and recursively call mergesort on both parts. When the two parts are in order, the basic operation of merging is performed. Merge refers to the process of merging two smaller ordered lists into one ordered list.
- Merge Sort in Python
def mergeSort(alist):
print("Splitting " , alist)
if len(alist) > 1:
mid = len(alist) // 2
lefthalf = alist[:mid]
righthalf = alist[mid:]
mergeSort(lefthalf)
mergeSort(righthalf)
i = 0
j = 0
k = 0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
alist[k] = lefthalf[i]
i += 1
else:
alist[k] = righthalf[j]
j += 1
k += 1
while i < len(lefthalf):
alist[k] = lefthalf[i]
i += 1
k += 1
while j < len(righthalf):
alist[k] = righthalf[j]
j += 1
k += 1
print("Merging ",alist)
5.3.6 Quick Sort
The quick sort algorithm first selects a reference value. The function of the reference value is to help split the list. In the final sorted list, the location of the reference value is often referred to as the split point at which the algorithm splits the list to make sub-calls to quicksort.
- Quicksort in Python
def partition(alist, first, last):
pivotvalue = alist[first]
leftmark = first + 1
rightmark = last
done = False
while not done:
while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
leftmark = leftmark + 1
while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
rightmark = rightmark - 1
if rightmark < leftmark:
done = True
else:
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp
temp = alist[first]
alist[first] = alist[rightmark]
alist[rightmark] = temp
return rightmark
def quickSortHelper(alist, first, last):
if first < last:
splitpoint = partition(alist,first,last)
quickSortHelper(alist,first,splitpoint - 1)
quickSortHelper(alist,splitpoint + 1,last)
def quickSort(alist):
quickSortHelper(alist,0,len(alist) - 1)