short-paper

A Dynamic Programming Based Solution to the Two-Dimensional Jump-It Problem

Authors:

Jamil Saquer,

Razib IqbalAuthors Info & Claims

ACMSE '17: Proceedings of the 2017 ACM Southeast Conference

Pages 219 - 222

https://doi.org/10.1145/3077286.3077290

Published: 13 April 2017 Publication History

Get Access

Abstract

This paper introduces the two-dimensional Jump-It problem, which is a board playing optimization problem. We present a dynamic programming based solution that finds the optimal cost of playing the game in O(mn), where m and n are the dimensions of the playing board. We also show how the solution can be extended to find a path that leads to playing the game with the optimal cost.

References

[1]

Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. 2009. Introduction to Algorithms, 3rd ed., Cambridge, MA: MIT Press, 2009.

Digital Library

Google Scholar

[2]

Jon Kleinberg and Eva Tardos. 2005. Algorithm Design, Boston, MA: Pearson, 2005.

Digital Library

Google Scholar

[3]

Jamil Saquer and Lloyd Smith. 2016. Simplifying dynamic programming, In Proceedings of the 5th International Conference on Informatics and Applications, Takamatsu, Japan, 159--164.

Google Scholar

[4]

Jamil Saquer and Razib Iqbal. 2017. A Python source code for finding an optimal path for the 2D JumpIt problem. {online} http://people.missouristate.edu/riqbal/algorithms/

Google Scholar

Recommendations

Generalized Dynamic Programming for Stochastic Combinatorial Optimization

In stochastic versions of combinatorial optimization problems, the objective is to maximize or minimize a function of random variables. For many problems of this type, conventionally applied dynamic programming DP may fail to generate an optimal ...
Dynamic Programming Approach for Large Scale Unit Commitment Problem
CSNT '11: Proceedings of the 2011 International Conference on Communication Systems and Network Technologies

In this paper, the large scale Unit Commitment (UC) problem has been solved using Dynamic Programming (DP) and the test results for conventional DP, Sequential DP and Truncation DP are compared with other stochastic techniques. The commitment is such ...
DPGame: Game-Based Learning for Dynamic Programming Algorithms
Entertainment Computing – ICEC 2024
Abstract
Dynamic programming is one of the most challenging topics in data structures and algorithms courses. Students often struggle to grasp dynamic programming techniques and apply them to solve problems. The common advice to students is to study lots ...

Comments

Information & Contributors

Information

Published In

ACMSE '17: Proceedings of the 2017 ACM Southeast Conference

April 2017

275 pages

ISBN:9781450350242

DOI:10.1145/3077286

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 April 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Short-paper
Research
Refereed limited

Conference

ACM SE '17

Sponsor:

ACM SE '17: SouthEast Conference

April 13 - 15, 2017

GA, Kennesaw, USA

Acceptance Rates

ACMSE '17 Paper Acceptance Rate 21 of 34 submissions, 62%;

Overall Acceptance Rate 502 of 1,023 submissions, 49%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
90
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Recommendations

Generalized Dynamic Programming for Stochastic Combinatorial Optimization

Dynamic Programming Approach for Large Scale Unit Commitment Problem

DPGame: Game-Based Learning for Dynamic Programming Algorithms

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations