Assignment-2 (Total Points: 100) Instructions: • Download the attached python file assignment_2.py (make sure to NOT change the name of this file). • Follow the instructions and replace all TODO...

1 answer below »
i have attached the file


Assignment-2 (Total Points: 100) Instructions: • Download the attached python file assignment_2.py (make sure to NOT change the name of this file). • Follow the instructions and replace all TODO comments in the scaffolding code. • Do NOT change the function signature provided in the scaffolding code, but you can add as many functions as you want to help you complete the task. • Test your code as much as you can to make certain it is correct. • Run flake8 in addition to testing your code; I expect professional and clear code with minimal flake8 warnings and having McCabe complexity (<10) from all of you. • create a write up with formatted code and screenshots of your output, running the mccabe complexity command and error free console. • save the write-up as a pdf and submit it along with your python code (file name assignment_2.py) as separate attachments before the due date on canvas. note: running flake 8 flake8 path/to/your/file (for warnings and errors) flake8 --max-complexity 10 path/to/your/file (for complexity) problem 1 (max points 50): the sun is the source of most of the energy that drives the biological and physical processes in the world around us—in oceans and on land it fuels plant growth that forms the base of the food chain, and in the atmosphere, it warms air which drives our weather. the rate of energy coming from the sun changes slightly every second. however, nasa scientist want to focus on the most significant energy increase period in a day, so that they may get better understanding about the sun. they have collected the measurement of the energy level in a range of time, starting from 0. your task is to design a program finding the most significant energy increases period from their daily observation. for example, they observed a sequence of energy level as follows, 100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97 your program should return (7, 11) since from element at index 7 (63) to element at index 11 (106) gives the most significant energy increase. note that the indices start from zero. you need to implement a python program to solve this problem using: a. the brute-force method q(n2). (max points: 10) b. the recursive method q(nlogn). (max points: 25) c. the iterative method q(n). (max points: 15) sample input [100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97] sample output (7, 11) note, if their observation data looks like 110 109 107 104 100, in this case your program should return (0, 1). problem 2 (max points 50): given a n × n matrix a and a positive integer k, compute s = a k . the input contains the following • a matrix a containing n * n nonnegative integers (each less than 100). you can assume that n ≤ 32 and is a power of 2, e.g. 1, 2, 4, 8, 16, 32. • a positive integer k (k ≤ 10). you need to do the following tasks: a. implement a function to multiply two matrices using strassen matrix multiplication method q(nlog27) (max points: 20). b. compute s using the function (from a above) such that the number of times the above function is called is q(k). (max points: 10) c. compute s using the function (from a above) and the divide & conquer approach such that the number of times the above function is called is q(log k). (max points: 20) sample input [[0, 1], [1, 1]], 3 sample output [[1, 2], [2, 3]] # -*- coding: utf-8 -*- from numpy import asarray # todo: replace all todo comments (yes, this one too!) energy_level = [100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97] #============================================================== # the brute force method to solve first problem def find_significant_energy_increase_brute(a): """ return a tuple (i,j) where a[i:j] is the most significant energy increase period. time complexity = o(n^2) """ #todo #============================================================== # the recursive method to solve first problem def find_significant_energy_increase_recursive(a): """ return a tuple (i,j) where a[i:j] is the most significant energy increase period. time complexity = o (n logn) """ #todo #============================================================== # the iterative method to solve first problem def find_significant_energy_increase_iterative(a): """ return a tuple (i,j) where a[i:j] is the most significant energy increase period. time complexity = o(n) """ #todo #============================================================== # the strassen algorithm to do the matrix multiplication def square_matrix_multiply_strassens(a, b): """ return the product ab of matrix multiplication. assume len(a) is a power of 2 """ a = asarray(a) b = asarray(b) assert a.shape == b.shape assert a.shape == a.t.shape assert (len(a) & (len(a) -1)) == 0, "a is not a power of 2" #todo #============================================================== # calculate the power of a matrix in o(k) def power_of_matrix_navie(a, k): """ return a^k. time complexity = o(k) """ #todo #============================================================== # calculate the power of a matrix in o(log k) def power_of_matrix_divide_and_conquer(a, k): """ return a^k. time complexity = o(log k) """ #todo #============================================================== def test(): assert(find_significant_energy_increase_brute(energy_level) == (7, 11)) assert(find_significant_energy_increase_recursive(energy_level) == (7, 11)) assert(find_significant_energy_increase_iterative(energy_level) == (7, 11)) assert((square_matrix_multiply_strassens([[0, 1], [1, 1]], [[0, 1], [1, 1]]) == asarray([[1, 1], [1, 2]])).all()) assert((power_of_matrix_navie([[0, 1], [1, 1]], 3) == asarray([[1, 2], [2, 3]])).all()) assert((power_of_matrix_divide_and_conquer([[0, 1], [1, 1]], 3) == asarray([[1, 2], [2, 3]])).all()) #todo: test all of the methods and print results. if __name__ == '__main__': test() #================================================ from="" all="" of="" you.="" •="" create="" a="" write="" up="" with="" formatted="" code="" and="" screenshots="" of="" your="" output,="" running="" the="" mccabe="" complexity="" command="" and="" error="" free="" console.="" •="" save="" the="" write-up="" as="" a="" pdf="" and="" submit="" it="" along="" with="" your="" python="" code="" (file="" name="" assignment_2.py)="" as="" separate="" attachments="" before="" the="" due="" date="" on="" canvas.="" note:="" running="" flake="" 8="" flake8="" path/to/your/file="" (for="" warnings="" and="" errors)="" flake8="" --max-complexity="" 10="" path/to/your/file="" (for="" complexity)="" problem="" 1="" (max="" points="" 50):="" the="" sun="" is="" the="" source="" of="" most="" of="" the="" energy="" that="" drives="" the="" biological="" and="" physical="" processes="" in="" the="" world="" around="" us—in="" oceans="" and="" on="" land="" it="" fuels="" plant="" growth="" that="" forms="" the="" base="" of="" the="" food="" chain,="" and="" in="" the="" atmosphere,="" it="" warms="" air="" which="" drives="" our="" weather.="" the="" rate="" of="" energy="" coming="" from="" the="" sun="" changes="" slightly="" every="" second.="" however,="" nasa="" scientist="" want="" to="" focus="" on="" the="" most="" significant="" energy="" increase="" period="" in="" a="" day,="" so="" that="" they="" may="" get="" better="" understanding="" about="" the="" sun.="" they="" have="" collected="" the="" measurement="" of="" the="" energy="" level="" in="" a="" range="" of="" time,="" starting="" from="" 0.="" your="" task="" is="" to="" design="" a="" program="" finding="" the="" most="" significant="" energy="" increases="" period="" from="" their="" daily="" observation.="" for="" example,="" they="" observed="" a="" sequence="" of="" energy="" level="" as="" follows,="" 100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97="" your="" program="" should="" return="" (7,="" 11)="" since="" from="" element="" at="" index="" 7="" (63)="" to="" element="" at="" index="" 11="" (106)="" gives="" the="" most="" significant="" energy="" increase.="" note="" that="" the="" indices="" start="" from="" zero.="" you="" need="" to="" implement="" a="" python="" program="" to="" solve="" this="" problem="" using:="" a.="" the="" brute-force="" method="" q(n2).="" (max="" points:="" 10)="" b.="" the="" recursive="" method="" q(nlogn).="" (max="" points:="" 25)="" c.="" the="" iterative="" method="" q(n).="" (max="" points:="" 15)="" sample="" input="" [100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97]="" sample="" output="" (7,="" 11)="" note,="" if="" their="" observation="" data="" looks="" like="" 110="" 109="" 107="" 104="" 100,="" in="" this="" case="" your="" program="" should="" return="" (0,="" 1).="" problem="" 2="" (max="" points="" 50):="" given="" a="" n="" ×="" n="" matrix="" a="" and="" a="" positive="" integer="" k,="" compute="" s="A" k="" .="" the="" input="" contains="" the="" following="" •="" a="" matrix="" a="" containing="" n="" *="" n="" nonnegative="" integers="" (each="" less="" than="" 100).="" you="" can="" assume="" that="" n="" ≤="" 32="" and="" is="" a="" power="" of="" 2,="" e.g.="" 1,="" 2,="" 4,="" 8,="" 16,="" 32.="" •="" a="" positive="" integer="" k="" (k="" ≤="" 10).="" you="" need="" to="" do="" the="" following="" tasks:="" a.="" implement="" a="" function="" to="" multiply="" two="" matrices="" using="" strassen="" matrix="" multiplication="" method="" q(nlog27)="" (max="" points:="" 20).="" b.="" compute="" s="" using="" the="" function="" (from="" a="" above)="" such="" that="" the="" number="" of="" times="" the="" above="" function="" is="" called="" is="" q(k).="" (max="" points:="" 10)="" c.="" compute="" s="" using="" the="" function="" (from="" a="" above)="" and="" the="" divide="" &="" conquer="" approach="" such="" that="" the="" number="" of="" times="" the="" above="" function="" is="" called="" is="" q(log="" k).="" (max="" points:="" 20)="" sample="" input="" [[0,="" 1],="" [1,="" 1]],="" 3="" sample="" output="" [[1,="" 2],="" [2,="" 3]]="" #="" -*-="" coding:="" utf-8="" -*-="" from="" numpy="" import="" asarray="" #="" todo:="" replace="" all="" todo="" comments="" (yes,="" this="" one="" too!)="" energy_level="[100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97]" #="=============================================================" #="" the="" brute="" force="" method="" to="" solve="" first="" problem="" def="" find_significant_energy_increase_brute(a):="" """="" return="" a="" tuple="" (i,j)="" where="" a[i:j]="" is="" the="" most="" significant="" energy="" increase="" period.="" time="" complexity="O(n^2)" """="" #todo="" #="=============================================================" #="" the="" recursive="" method="" to="" solve="" first="" problem="" def="" find_significant_energy_increase_recursive(a):="" """="" return="" a="" tuple="" (i,j)="" where="" a[i:j]="" is="" the="" most="" significant="" energy="" increase="" period.="" time="" complexity="O" (n="" logn)="" """="" #todo="" #="=============================================================" #="" the="" iterative="" method="" to="" solve="" first="" problem="" def="" find_significant_energy_increase_iterative(a):="" """="" return="" a="" tuple="" (i,j)="" where="" a[i:j]="" is="" the="" most="" significant="" energy="" increase="" period.="" time="" complexity="O(n)" """="" #todo="" #="=============================================================" #="" the="" strassen="" algorithm="" to="" do="" the="" matrix="" multiplication="" def="" square_matrix_multiply_strassens(a,="" b):="" """="" return="" the="" product="" ab="" of="" matrix="" multiplication.="" assume="" len(a)="" is="" a="" power="" of="" 2="" """="" a="asarray(A)" b="asarray(B)" assert="" a.shape="=" b.shape="" assert="" a.shape="=" a.t.shape="" assert="" (len(a)="" &="" (len(a)="" -1))="=" 0,="" "a="" is="" not="" a="" power="" of="" 2"="" #todo="" #="=============================================================" #="" calculate="" the="" power="" of="" a="" matrix="" in="" o(k)="" def="" power_of_matrix_navie(a,="" k):="" """="" return="" a^k.="" time="" complexity="O(k)" """="" #todo="" #="=============================================================" #="" calculate="" the="" power="" of="" a="" matrix="" in="" o(log="" k)="" def="" power_of_matrix_divide_and_conquer(a,="" k):="" """="" return="" a^k.="" time="" complexity="O(log" k)="" """="" #todo="" #="=============================================================" def="" test():="" assert(find_significant_energy_increase_brute(energy_level)="=" (7,="" 11))="" assert(find_significant_energy_increase_recursive(energy_level)="=" (7,="" 11))="" assert(find_significant_energy_increase_iterative(energy_level)="=" (7,="" 11))="" assert((square_matrix_multiply_strassens([[0,="" 1],="" [1,="" 1]],="" [[0,="" 1],="" [1,="" 1]])="=" asarray([[1,="" 1],="" [1,="" 2]])).all())="" assert((power_of_matrix_navie([[0,="" 1],="" [1,="" 1]],="" 3)="=" asarray([[1,="" 2],="" [2,="" 3]])).all())="" assert((power_of_matrix_divide_and_conquer([[0,="" 1],="" [1,="" 1]],="" 3)="=" asarray([[1,="" 2],="" [2,="" 3]])).all())="" #todo:="" test="" all="" of="" the="" methods="" and="" print="" results.="" if="" __name__="=" '__main__':="" test()="" #="">
Answered 1 days AfterOct 19, 2021

Answer To: Assignment-2 (Total Points: 100) Instructions: • Download the attached python file assignment_2.py...

Sathishkumar answered on Oct 21 2021
119 Votes
# -*- coding: utf-8 -*-
from numpy import asarray
import timeit
# TODO: Replace all TODO comments (yes, this one too!)
global C,x1,lst1,B1,i,j,lv
ENERGY_LEVEL = [100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97]
ENERGY_
LEVEL1 = [110,109,107,104,100,98,97]
C=ENERGY_LEVEL
lst1=[]
x1=[]
#TODO
B1=1
i=-1
j=0
lv=()
#==============================================================
# The brute force method to solve first problem
def find_significant_energy_increase_brute(A):
"""
Return a tuple (i,j) where A[i:j] is the most significant energy increase period.
time complexity = O(n^2)
"""
#TODO
C=A
lst=[]
x=[]
#TODO
B=1
for i in range(len(A)):
for j in range(B,len(A)):
x.append(C[j]-A[i])
m=C[j]-A[i]
n=[i,j,m]
lst.append(n)
B+=1
ii=max(x)
ir=x.index(ii)
er_poit=lst[ir]
lv=[er_poit[0],er_poit[1]]
return tuple(lv)

#==============================================================
# The recursive method to solve first problem
def find_significant_energy_increase_recursive(A):
"""
Return a tuple (i,j) where A[i:j] is the most significant energy increase period.
time complexity = O (n logn)
"""
#TODO
global C,x1,lst1,B1,i,j,lv
i+=1
#j+=1
if i==len(A):

ii=max(x1)
#print(ii)
ir=x1.index(ii)
#print(ir)
er_poit=lst1[ir]
#print(lst1[ir])
lv=[er_poit[0],er_poit[1]]
return tuple(lv)
else:
for j in range(B1,len(A)):
x1.append(C[j]-A[i])
m=C[j]-A[i]
n=[i,j,m]
lst1.append(n)
#print(n)
#print(n)

B1+=1
find_significant_energy_increase_recursive(A)
return (tuple(lv))
#==============================================================
# The iterative method to solve first problem
def find_significant_energy_increase_iterative(A):
"""
Return a tuple (i,j) where A[i:j] is the most significant energy increase period.
time complexity = O(n)
"""
#TODO
C=A
lst,x=[],[]
B=1
for i in range(len(A)):
for j in range(B,len(A)):
x.append(C[j]-A[i])
...
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here