FIT1045 53 workshop 08 solutions PDF

Preview

Summary

FIT1045/1053 Algorithms and Programming Fundamentals inPython – Workshop 08.SolutionsObjectivesAfter this workshop, you should be able to:❼solve simple problems by recursive functions❼implement and understand the difference between depth-first andbreadth-first searchTask 1: Recursive Problem Solving...

Description

FIT1045/1053 Algorithms and Programming Fundamentals in Python – Workshop 08. Solutions

Objectives After this workshop, you should be able to: solve simple problems by recursive functions implement and understand the difference between depth-first and breadth-first search

Task 1: Recursive Problem Solving Part A: Euclid’s Algorithm Re-implement Euclid’s algorithm using a recursive function gcd(a, b). def gcd (a , b ): """ Determ ines greatest common di vi sor of two intege rs . Input : two in tegers a and b such that not a == b ==0 Output : grea test common divis or of a and b For exa mp le : >> > gcd (0 , 4) 4 >>> gcd (10 , 0) 10 >>> gcd (18 , 27) 9 >>> gcd (21 , 13) 1 """ if b == 0: return a else : return gcd (b , a % b )

Part B: List Inversion def reverse ( lst ): """ Computes re ve rse of input sequ en ce . In put : any list ( lst ) Output : reverse of lst For exa mp le : >>> r everse ([1 , 2, 3 , 4]) [4 , 3 , 2 , 1] >> > re ver se ([10 , 11 , 12 , 13 , 14] ) [14 , 13 , 12 , 11 , 10] 1

>>> r ev ers e ([1]) [1] >>> r ev ers e ([]) [] """ if len ( lst ) 0: v = b oun dary . pop () visited += [v ] if v in goals : return visited for w in n ei gh bo ur s ( v , g raph ): if w not in visited and w not in bou ndary : boundary . append ( w) return visited

Part B: Path to goal def p at h_ f ro m_ pr ed li st ( s , e , p red ): rev = [e ] w = e 2

while w != s : w = pred [ w] rev += [ w] res = [] while rev : res += [ rev . pop ()] return res

def dfs _pa th ( graph , s , go als =[]): pred = [ None ] * len ( graph ) visited = set () bou nd ar y = de que ([ s ]) while len ( boundary ) > 0: v = b oun dary . pop () visited . add ( v) if v in goals : return p at h_ fr om _p re dl i st ( s , v , p red ) for w in n ei gh bo ur s ( v , g raph ): if w not in visited and w not in bou ndary : pred [w ] = v boundary . append ( w) return None

def bfs _pa th ( graph , s , go als =[]): pred = [ None ] * len ( graph ) visited = set () bou nd ar y = de que ([ s ]) while len ( boundary ) > 0: v = bo undary . popleft () visited . add ( v) if v in goals : return p at h_ fr om _p re dl i st ( s , v , p red ) for w in n ei gh bo ur s ( v , g raph ): if w not in visited and w not in bou ndary : pred [w ] = v boundary . append ( w) return None

3...