CS173: Intro to Computer Science - Dynamic Programming
Activity Goals
The goals of this activity are:
- To explain the benefits of Dynamic Programming
- To implement Dynamic Programming to improve the runtime performance of a given algorithm
The Activity
Directions
Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to take notes for the group, and appoint another member to discuss your findings with the class. After class, think about the questions in the reflective prompt and respond to those individually. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.
Model 1: The Fibonacci Sequence
Questions
- Despite the concise code, what is inefficient about this approach to the Fibonacci sequence?
- Try removing the recursive function calls: replace assignments or returns with array assignments, and write a loop instead.
- Is your loop solving the problem from the top-down or bottom-up? That is, is your loop counting up or down, and why? How is this similar or different from the recursive approach?
Submission
Submit your answers to the questions using the Collaborative Spaces section of OneNote. You can add a page with your name and your group members' names, and today's date, as the title. Under the appropriate section (i.e., "Class Notes", "Collaborative Spaces", "Reflective Prompts") that you can select on the left side of the screen, you can click "Add Page" on the right side. You can answer any reflective prompt questions in the Reflective Journal section of your OneNote Classroom personal section.