FIT1045 53 workshop 10 solutions PDF

Preview

Summary

FIT1045/1053 Algorithms and Programming Fundamentals inPython – Workshop 10.SolutionsObjectivesAfter this workshop, you should be able to:❼Implement Gaussian Elimination in order to solve linear system problems.❼Understand the difference between Adjacency Lists and Adjacency Matrices.❼Implement a gr...

Description

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

Objectives After this workshop, you should be able to: Implement Gaussian Elimination in order to solve linear system problems. Understand the difference between Adjacency Lists and Adjacency Matrices. Implement a greedy strategy to solve for independent sets.

Task 1: Gaussian Elimination for Singular Matrices Warmup (0.5 Marks) def i s_ u p p e r _ t r i a n g u l a r ( a ): """ Determ ines whether (a ) is upper tri angula r . For e xample : >>> a = [[2 , 1 , 1] , .. . [0 , -8 , -2] , ... [0 , 0 , 1]] >>> i s_u ppe r_tr ian gul ar (a ) True Input : square matrix ( a) Output : True if all en tries of ( a) below diagon al are 0; False ot herwise """ n = len ( a ) for i in range ( n ): for j in range (0 , i ): if a [ i ][ j ] != 0: return False return True

Part A: Row Echelon Form (0.5 Marks) def is_row_echelon (a): """ Checks wether a is in echelon ( stair case ) form . """ n = len ( a ) p = -1 for i in range ( n ): j = 0 while j p: p = j break else : return False return True

Part B: General Forward Elimination (0.5 Marks) def pi vo t_ in de x (a , j , p = Non e ): """ Finds pivot index of matrix a in column j . : param a: matrix with n c olumns : param j: column index less or equal n : return : row index k greater than j such that a[ k ][ j ]!=0 or None if no such index """ n = len ( a ) k = p or j while k < n and a [k ][ j ] == 0: k += 1 return k if k < n else None def echel on (a , b ): """ Computes equi valent system in row ec helon form of input system of linear equation s by means of forward eli minat ion . """ u = deepcopy ( a) c = deepcopy ( b) m = n = len ( a ) p = 0 for j in range ( n ): k = p iv ot_i nd ex (u , j , p ) if k is not None : u[ p] , u[ k] = u [k ], u [p] c[ p] , c[ k] = c [k ], c [p] for i in range ( p +1 , m ): q = u [ i ][ j ] / u [p ][ j ] u [i ] = [ u[ i ][ l ] - q *u [p ][ l ] for l in range ( n )] c[ i] = c [i ] - q* c[ p] p += 1 return u , c

Part C: General Back Substitution (0.5 Marks) def piv ot (j , u ): """ Dete rmines the pivot row of column j in echelon matrix u if it exists . Input : a matrix u in echelon form Output : True if column j c ontains an edge of a stair in the st aircase pattern of u For e xample : >>> u = [[1 , ... [0 , ... [0 , >>> pivot (0 ,

0 , 1] , 1 , 1] , 0 , 0]] u) 2

0 >>> pivot (1 , u ) 1 >>> pivot (2 , u ) """ i = j while u [ i ][ j ] == 0. 0: i - =1 return i if not any ( u[ i ][ k ] for k in range ( j )) else None

def s ol v e_ b y_ b ac k_ su b st i tu t io n (u , b ): """ Solves linear system ux = b for a square matrix u in row echelon form or returns None if no s olution exists . """ n = len ( u ) x = n *[0.0] for i in range (n -1 , -1 , -1): if u [i ][ -1]!=0: break if b[ i ]!=0.0: return None for i in range (n -1 , -1 , -1): p = pivot (i , u) if p is not None : s = sum ([ x[ j] * u [p ][ j] for j in range ( i +1 , n ) ]) x[ i] = ( b[ p] -s ) / u[ p ][ i] return x

Task 2: Maximal Independent Set Problem Warmup: (0 Marks) Adjacency Lists Write a function adjacency matrix(adj lists) that accepts an adjacency list of a graph as input and outputs the adjacency matrix representation of the same graph. For example: >>> adjacency_matrix(lec_graph) [ [0, 0, 1, 0, 1, 1, 1, 1], [0, 0, 1, 1, 0, 1, 1, 1], [1, 1, 0, 0, 0, 0, 1, 1], [0, 1, 0, 0, 1, 0, 0, 1], [1, 0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 0, 0, 0, 0, 0], [1, 1, 1, 0, 1, 0, 0, 1], [1, 1, 1, 0, 1, 0, 0, 1] ] Extension: In case, this was too easy, can you write the function using a single list comprehension? # Warmup def adj ace ncy_ matr ix ( ad j_lists ): """ >>> l ec _g ra ph = [ [2 , 4 , 5 , 6 , 7] , ... [2 , 3 , 5, 6 ,7] , ... [0 , 1 , 6 , 7] , ... [1 , 4 , 7] , ... [0 , 3 , 6] , ... [0 , 1] , ... [0 , 1 , 2 , 4 , 7] , ... [0 , 1 , 2, 4 , 7] ] 3

>>> a djac enc y_m atri x ( lec_gr aph ) [[0 , 0 , 1, 0 , 1, 1, 1 , 1] , [0 , 0 , 1, 1 , 0, 1 , 1, 1] , [1 , 1 , 0, 0 , 0, 0 , 1, 1] , [0 , 1 , 0, 0 , 1, 0 , 0, 1] , [1 , 0 , 0, 1 , 0, 0 , 1, 0] , [1 , 1 , 0, 0 , 0, 0 , 0, 0] , [1 , 1 , 1, 0 , 1, 0 , 0, 1] , [1 , 1 , 1, 0 , 1, 0 , 0, 1]] """ n = len ( adj_lis ts ) return [[ int ( j in a dj _l ists [ i ]) for j in range ( n )] for i in range ( n )]

Part A: (0.5 Marks) Independent Sets # Part A : Ind epende nt Sets def is _i nd se t ( adj_l is ts , a ): """ >>> l ec _g ra ph = [ [2 , 4 , 5 , 6 , 7] , ... [2 , 3 , 5, 6 ,7] , ... [0 , 1 , 6 , 7] , ... [1 , 4 , 7] , ... [0 , 3 , 6] , ... [0 , 1] , ... [0 , 1 , 2 , 4 , 7] , ... [0 , 1 , 2, 4 , 7] ] >>> is _ind set ( lec_graph , []) True >>> is _ind set ( lec_graph , [5]) True >>> i s_ in ds et ( lec_ graph , [0 , 2]) False >>> i s_ in ds et ( lec_ graph , [6 , 5 , 3]) True """ return all (w not in ad j_lists [ v] for v in a for w in a)

Part B: (0.5 Marks) Greedy Maximisation def gree dy_i ndset ( adj_lis ts ): """ The func tion gr eedily selects v ertices in in creasi ng order of the number of neig hbours in the graph ( making sure to only incl ude a vertex to a temp orary solution if the res ulting colle ction is still an ind epedn ent set ). """ def num_neighbours (i): return len ( a dj_lists [ i]) vertices = sorted ( range ( len ( a dj _l is ts )) , key = n um _ne ig hbo ur s ) res = [] for i in vertices : res . a ppend ( i) if not is _indset ( adj_lists , res ): res . pop () return res

Bonus: Counter Example (Not Assessed)

4

Task 3: Advanced Polynomial Interpolation (FIT1053 Only) (1 Mark) Solution.

5...