Attached the File
Assignment_4.pdf Assignment-4 Part A (Total Points: 35) (Extra Credit: 20) Instructions Submission You can either write your answer using Word/LaTex or take a picture/scan of your hand-written (neat and tidy) solution, then put your solution in one PDF file. Submit your PDF online using Canvas. All submission must be posted before the deadline. Problem 1 (Max Points: 10) Consider the problem of making change for n cents using the fewest number of coins. Assume that each coin's value is an integer. a) Describe a greedy algorithm to make change consisting of quarters, dimes, nickels and pennies. b) Give a set of coin denominations for which the greedy algorithm does not yield an optimal solution. Your set should include a penny so that there is a solution for every value of n. Problem 2 (Max Points: 5) Given a rod of length n inches and an array of prices (pi, for i = 1 n) of all pieces of size smaller than n, the Rod-cutting problem is to determine the maximum value obtainable by cutting up the rod and selling the pieces. You do not need to solve the Rod cutting problem, but instead show, by means of a counter example, that the following greedy strategy does not always determine an optimal way to cut rods. Define the density of a rod of length i to be pi / i, that is its value per inch. The greedy strategy for a rod of length n cuts off a first piece of length i, where 1=< i=""><= n,="" having="" maximum="" density.="" it="" then="" continues="" by="" applying="" the="" greedy="" strategy="" to="" the="" remaining="" piece="" of="" length="" n="" i.="" problem="" 3="" (max="" points:="" 10)="" the="" fibonacci="" numbers="" are="" defined="" by="" recurrence="" f0="0," f1="1" and="" fi="Fi-1" +="" fi-2.="" give="" an="" o(n)="" time="" dynamic-programming="" algorithm="" to="" compute="" the="" nth="" fibonacci="" number="" i.e.="" fn.="" draw="" the="" sub-problem="" graph.="" how="" many="" vertices="" and="" edges="" are="" in="" the="" graph?="" problem="" 4="" (max="" points:="" 10)="" give="" a="" dynamic-programming="" solution="" to="" the="" 0-1="" knapsack="" problem="" that="" runs="" in="" o(nw)="" time="" where="" n="" is="" the="" number="" of="" items="" and="" w="" is="" the="" maximum="" weight="" of="" items="" that="" can="" be="" put="" in="" the="" knapsack.="" provide="" a="" sample="" run="" of="" your="" algorithm="" for="" 4="" items="" (wi,="" vi)="" as="" (1,3),="" (2,4),="" (3,5),="" (4,8)="" where="" wi="" is="" the="" weight="" of="" i-th="" item="" and="" vi="" is="" the="" value="" of="" i-th="" item="" and="" also="" the="" maximum="" weight="" that="" can="" be="" put="" in="" the="" knapsack(w)="" is="" 6.="" give="" the="" maximum="" value="" of="" items="" that="" can="" be="" put="" in="" the="" knapsack.="" problem="" 5="" (max="" points:="" 10)="" [extra="" credit]="" you="" are="" climbing="" a="" staircase.="" it="" takes="" n="" (=""> 0) steps to reach to the top. Each time you can either climb 1, 2 or 3 steps. In how many distinct ways can you climb to the top? Example: Number of stairs: 3 Number of ways: 4 Distinct ways to climb to the top: {(1,1,1), (1, 2), (2, 1), (3)} Note: your algorithm only needs to return the number of distinct ways and not the actual ways to climb to the top. Problem 6 (Max Points: 10) [Extra Credit] Describe an efficient algorithm that, given a set {x1, x2 n} of points on the real line, determines the size of the smallest set of unit-length closed intervals that contains all of the given points. Also give the time complexity of your algorithm. For example: Given points {0.8, 4.3, 1.7, 5.4}, the size of the smallest set of unit-length closed intervals to cover them is 3. Run your algorithm on the following set of points: {0.8, 2.3, 3.1, 1.7, 3.6, 4.0, 4.2, 5.5, 5.2, 1.0, 3.9, 4.7} and determine the size of the smallest set of unit-length closed intervals that contains all of the given points. Assignment_4.pdf Assignment-4 Part B (Total Points: 45) Instructions: Download the attached python file assignment_4.py (make sure to NOT change the name of this file). Follow the instructions and replace all TODO comments in the scaffolding code. 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_4.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="" 15):="" a="" numeric="" sequence="" of="" ai="" is="" ordered="" if="" a1="">< a2="">< ...="">< an.="" let="" the="" subsequence="" of="" the="" given="" numeric="" sequence="" (a1,="" a2,="" ...,="" an)="" be="" any="" sequence="" (ai1,="" ai2,="" ...,="" aik),="" where="" 1=""><= i1="">< i2="">< ...="">< ik=""><= n.="" for="" example,="" sequence="" (1,="" 7,="" 3,="" 5,="" 9,="" 4,="" 8)="" has="" ordered="" subsequences,="" e.="" g.,="" (1,="" 7),="" (3,="" 4,="" 8)="" and="" many="" others.="" all="" longest="" ordered="" subsequences="" are="" of="" length="" 4,="" e.="" g.,="" (1,="" 3,="" 5,="" 8).="" your="" program,="" when="" given="" the="" numeric="" sequence,="" must="" find="" the="" length="" of="" its="" longest="" ordered="" subsequence.="" the="" input="" list="" contains="" the="" elements="" of="" sequence="" -="" n="" integers="" in="" the="" range="" from="" 0="" to="" 10000="" each.="" 1=""><= n=""><= 1000.="" your="" output="" must="" contain="" a="" single="" integer="" that="" which="" is="" the="" length="" of="" the="" longest="" ordered="" subsequence="" of="" the="" given="" sequence.="" sample="" input="" sample="" output="" problem="" 2="" (max="" points="" 15):="" due="" to="" recent="" rains="" (i="" know="" it="" places="" in="" the="" campus,="" which="" is="" represented="" by="" a="" rectangle="" of="" n="" x="" m="" (1=""><= n=""><= 100;="" 1=""><= m=""><= 100)="" squares.="" each="" square="" contains="" either="" water="" ('#')="" or="" dry="" land="" ('-="" ').="" a="" pond="" is="" a="" connected="" set="" of="" one="" or="" more="" squares="" with="" water="" in="" them,="" where="" a="" square="" is="" considered="" adjacent="" to="" all="" eight="" of="" its="" neighbors.="" the="" problem="" is="" to="" figure="" out="" how="" many="" ponds="" have="" formed="" in="" the="" campus,="" given="" a="" diagram="" of="" the="" campus.="" the="" campus="" is="" represented="" by="" a="" grid="" represented="" by="" a="" list="" of="" n="" lines="" of="" characters="" separated="" by="" contains="" m="" characters="" per="" line="" representing="" one="" row="" of="" the="" grid="" (campus)="" .="" each="" character="" is="" either="" '#'="" or="" '-'.="" the="" characters="" do="" not="" have="" spaces="" between="" them.="" write="" a="" program="" to="" compute="" and="" return="" the="" number="" of="" ponds="" in="" the="" campus.="" sample="" input="" sample="" output="" (there="" are="" three="" ponds:="" one="" in="" the="" upper="" left,="" one="" in="" the="" lower="" left,and="" one="" along="" the="" right="" side)="" problem="" 3="" (max="" points="" 15):="" a="" supermarket="" has="" a="" set="" px="" for="" each="" product="" x="" prod="" sold="" by="" a="" deadline="" dx="" that="" is="" measured="" as="" an="" integral="" number="" of="" time="" units="" starting="" from="" the="" moment="" the="" sale="" begins.="" each="" product="" takes="" precisely="" one="" unit="" of="" time="" for="" being="" sold.="" a="" selling="" schedule="" is="" an="" ordered="" subset="" of="" produc="" at="" the="" selling="" of="" each="" product="" x="" sell,="" according="" to="" the="" ordering="" of="" sell,="" completes="" before="" the="" deadline="" dx="" or="" just="" when="" x="" sellpx.="" an="" optimal="" selling="" schedule="" is="" a="" schedule="" with="" a="" maximum="" profit.="" for="" example,="" consider="" the="" products="" prod="{a,b,c,d}" with="" (pa,da)="(50,2)," (pb,db)="(10,1)," (pc,dc)="(20,2)," and="" (pd,dd)="(30,1)." the="" possible="" selling="" schedules="" are="" listed="" in="" table="" 1.="" for="" instance,="" the="" schedule="" sell="{d,a}" shows="" that="" the="" selling="" of="" product="" d="" starts="" at="" time="" 0="" and="" ends="" at="" time="" 1,="" while="" the="" selling="" of="" product="" a="" starts="" at="" time="" 1="" and="" ends="" at="" time="" 2.="" each="" of="" these="" products="" is="" sold="" by="" its="" deadline.="" sell="" is="" the="" optimal="" schedule="" and="" its="" profit="" is="" 80.="" write="" a="" program="" that="" reads="" sets="" of="" products="" from="" the="" input="" and="" computes="" the="" profit="" of="" an="" optimal="" selling="" schedule="" for="" each="" set="" of="" products.="" your="" input="" must="" be="" a="" list="" of="" n="" pairs="" (pi,="" di)="" of="" integers,="" that="" designate="" the="" profit="" and="" the="" selling="" deadline="" of="" the="" i-th="" product.="" note:="" 0="">< n="">< 100,="" 1=""><= pi=""><= 1000="" and="" 1=""><= di=""><= 1000. for output, the program returns the profit of an optimal selling schedule for the set. sample input 1 sample output sample input 2 sample output 2 note the sample input contains two product sets. the first set encodes the products from table 1. the second set is for 7 products. the profit of an optimal schedule for these products is 185. 1000.="" for="" output,="" the="" program="" returns="" the="" profit="" of="" an="" optimal="" selling="" schedule="" for="" the="" set.="" sample="" input="" 1="" sample="" output="" sample="" input="" 2="" sample="" output="" 2="" note="" the="" sample="" input="" contains="" two="" product="" sets.="" the="" first="" set="" encodes="" the="" products="" from="" table="" 1.="" the="" second="" set="" is="" for="" 7="" products.="" the="" profit="" of="" an="" optimal="" schedule="" for="" these="" products="" is="">