by using the following book introduction to Algorithms 3rd.Edition.

I need a help with the attached question I set the price to be $35

 4.pdf

Illinois Institute of Technology
Department of Computer Science Homework Assignment 4
CS 430 Introduction to Algorithms
Spring Semester, 2017 Due: Wednesday, March 1, 2017
1. Problem 16-1 on pages 446–447, adding
(d) i. As given on page 447, but use dynamic programming in its recursive formulation
ii. As given on page 447, but use dynamic programming in its iterative formulation
iii. Analyze the time required. (e) Suppose that, in part (d), we add the restriction that each denomination can be used just once.
Modify your algorithm to determine if making change for n cents is possible.
2. Coins of various values are placed on the cells of an n × m chess board. Let the upper left corner cell
be (1, 1) and the lower right cell be (n, m); cell (i, j) has coins valued at cij . A robot starts at cell (0, 0
and can move only to the right or down on the board.
(a) Give a dynamic programming algorithm expressed recursively without memoization to determine
the path the robot should follow to maximize the total value of the coins collected as the robot
wanders on the board. Analyze the time required.
(b) Give the algorithm iteratively with memoization. Analyze the time required.
3. Consider a weighted form of the activity selection problem of CLRS3 section 16.1 in which each of the n
activities is weighted by its importance (the weight is unrelated to the starting and finishing times and
to the duration). We want to choose a subset of non-conflicting activities with the highest total weight.
(a) Prove that the heuristic of choosing the earliest finishing time does not always result in an optimal
schedule.
(b) Give an O(n2 ) algorithm to compute an optimal schedule.

• 1493690886-4.pdf

ComputerScienceExpert

(11)

Status NEW Posted 02 May 2017 02:05 AM My Price 9.00

-----------

Attachments

file 1493690888-Solutions file 2.docx preview (51 words )

H-----------ell-----------o S-----------ir/-----------Mad-----------am ----------- Th-----------ank----------- yo-----------u f-----------or -----------you-----------r i-----------nte-----------res-----------t a-----------nd -----------buy-----------ing----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n. -----------Ple-----------ase----------- pi-----------ng -----------me -----------on -----------cha-----------t I----------- am----------- on-----------lin-----------e o-----------r i-----------nbo-----------x m-----------e a----------- me-----------ssa-----------ge -----------I w-----------ill----------- be----------- qu-----------ick-----------ly -----------onl-----------ine----------- an-----------d g-----------ive----------- yo-----------u e-----------xac-----------t f-----------ile----------- an-----------d t-----------he -----------sam-----------e f-----------ile----------- is----------- al-----------so -----------sen-----------t t-----------o y-----------our----------- em-----------ail----------- th-----------at -----------is -----------reg-----------ist-----------ere-----------d o-----------n -----------THI-----------S W-----------EBS-----------ITE-----------. ----------- Th-----------ank----------- yo-----------u -----------

Not Rated(0)

• Buy Answer