Fermé

Algorithms - Dynamic Programming

I have two questions that I have done and need to get a correct answer to validate:

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 (1, 1) and can move only to the right or down on the board.

1. Give a dynamic programming algorithm expressed recursively without memoization to determine the path the robot should follow to maxi- mize the total value of the coins collected as the robot wanders on the board from cell (1,1) to cell (n,m). Analyze the time required and give corresponding pseudocode.

2. Give the algorithm iteratively with memoization. Analyze the time required and give corresponding pseudocode

------------------------------------------------------------------------------------------------------------------------------

We are given a sequence of n numbers, a1,a2,··· ,an and want to find the longest increasing subsequence (LIS); that is, we want to find indices i1 < i2 < ··· < im such that aij < aij+1 and m is as large as possible. For example, given the sequence 5, 2, 8, 6, 3, 6, 9, 7 we have an increasing subsequence 2, 3, 6, 9 and there is no longer increasing subsequence.

1. Give a recursive dynamic programming recurrence (just give the func- tion) for the LIS of a sequence a1,a2,··· ,an. (Hint : Let Li be the length of the LIS in a1,a2,··· ,ai , let Ai be index of the smallest possible largest element in that increasing subsequence, and let Bi be index of the second-largest element in that increasing subsequence. Express Li recursively. You may assume a dummy element a0 = −∞)

2. Give the algorithm iteratively with memoization. Analyze the time required and give corresponding pseudocode.

Compétences : Java, Algorithme, Programmation C

en voir plus : dynamic programming url tokenize, connect database website dynamic programming, optimal binary search trees dynamic programming, dynamic programming connect database, matlab dynamic programming, dynamic programming matlab code, dynamic programming binary search tree, dynamic programming rapidweaver, help matlab discrete time dynamic programming, matlab dynamic programming example, optimal binary search tree dynamic programming, bottom dynamic programming, dynamic programming solutions corporation, dynamic programming algorithms, dynamic programming in algorithms, digital dynamic range compressor design –– a tutorial and analysis, programming elixir ≥ 1.6 pdf

Concernant l'employeur :
( 2 commentaires ) Minneapolis, United States

Nº du projet : #22071835

11 freelance font une offre moyenne de $35 pour ce travail

utkarshkatiyar19

Hi, I'm an expert in dynamic programming. I'm sure that I can easily do this project for you. We can have a chat about it. Thanks.

%bids___i_sum_sub_32% %project_currencyDetails_sign_sub_33% USD en 1 jour
(427 Commentaires)
7.4
wangbeizou

Hello. I have read your description and I am so interested in your project. I am confident in your project and I can finish it clearly on time. I am well experienced and skillful C/C++ , Java, DP etc. I have +10 ye Plus

%bids___i_sum_sub_35% %project_currencyDetails_sign_sub_36% USD en 2 jours
(191 Commentaires)
6.5
vedant2910

I have a major in Computer Science. I have done various projects in C as you can see in my reviews. I am well versed in Data Structures and algorithms too. I have gone through your questions and know the solution too. Plus

%bids___i_sum_sub_32% %project_currencyDetails_sign_sub_33% USD en 1 jour
(18 Commentaires)
4.3
Jng93Slv3

Hi! I read your requirement and I'm interesting your project very well. I am a full time developer and i can finish in a day I am mastering Java and I'm a good Engineer. And also I have many experience and good skill Plus

%bids___i_sum_sub_32% %project_currencyDetails_sign_sub_33% USD en 1 jour
(4 Commentaires)
3.1
zymerconstantine

Dear Hiring Manager, After reviewing your job description, it’s clear that you’re looking for a candidate that is extremely familiar with the responsibilities associated with the role, and can perform them confidently Plus

%bids___i_sum_sub_35% %project_currencyDetails_sign_sub_36% USD en 7 jours
(1 Évaluation)
1.9
golabian2020

Hi there, I am a computer science graduate and I am expert in related topics. Your description is very clear, I could write the answers for you in a day.

%bids___i_sum_sub_32% %project_currencyDetails_sign_sub_33% USD en 1 jour
(2 Commentaires)
1.2
topman068001

///Python, C#, C/C++, JavaScript, MySQL, .../// I have read your job description carefully and am interested in your project. I saw your project and thought it fits my skills very well. I can complete any very difficul Plus

%bids___i_sum_sub_35% %project_currencyDetails_sign_sub_36% USD en 2 jours
(0 Commentaires)
0.0
yash114

I have got the solution for both of the problems. I am a new freelancer so this project would help me :)

%bids___i_sum_sub_32% %project_currencyDetails_sign_sub_33% USD en 1 jour
(0 Commentaires)
0.0
jhapriety

Though new to this platform, I have been working as a Java developer for the past six+ years. I have varied experiences in Java and I am good with algorithms and data structures. I believe that my experience can be use Plus

%bids___i_sum_sub_35% %project_currencyDetails_sign_sub_36% USD en 4 jours
(0 Commentaires)
0.0
saurabh20696

I am an expert in JAVA and C programming and will be very passionate to work for your project. Your work will be done and hope to discuss and go through all your requirements for this project. And will deliver this pro Plus

%bids___i_sum_sub_35% %project_currencyDetails_sign_sub_36% USD en 7 jours
(0 Commentaires)
0.0
tudortarniceru

Hello! I have been competitive programming in C++ for the past 8 years, earning multiple awards and medals at contests, including the National Olympiad in Informatics. I've also been tutoring people into solving interv Plus

%bids___i_sum_sub_32% %project_currencyDetails_sign_sub_33% USD en 1 jour
(0 Commentaires)
0.0