# Analysis of Python Data Structures and Algorithms (2nd Edition) - Chapter 4 Recursion and Chapter 5 Searching and Sorting

## 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

1. A recursive algorithm must have a base case
2. A recursive algorithm must change its state and move closer to the base case
3. 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:

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)
myTurtle.down()
myTurtle.begin_fill()
myTurtle.goto(points)
myTurtle.goto(points)
myTurtle.goto(points)
myTurtle.end_fill()

def getMid(p1,p2):
return ((p1 + p2) / 2, (p1 + p2) / 2)

def sierpinski(points , degree , myTurtle):
colormap = ["blue","red","green","white","yellow","violet","orange"]

drawTriangle(points,colormap[degree],myTurtle)
if degree > 0:
sierpinski([points,
getMid(points,points),
getMid(points,points,)],
degree - 1,
myTurtle
)
sierpinski([points,
getMid(points, points),
getMid(points, points, )],
degree - 1,
myTurtle
)
sierpinski([points,
getMid(points, points),
getMid(points, points, )],
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.

```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 # 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

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
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
```

### 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)
```

Posted by horstuff on Thu, 14 Jul 2022 02:42:43 +0530