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:
        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)

Tags: Algorithm data structure

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