HW03 - An Exploration of Dynamic Programming

A practical tour from recursion to memoization, tabulation, and beyond.

Background

Before proceeding with this lab, the student should take the time to read:

• A quick review of the Fibonacci recurrence and mathematical induction.
• An overview of Dynamic Programming (DP): overlapping subproblems & optimal substructure. (See the article Simplifying Dynamic Programming)
• A short read on Gang of Four (GoF) Design Patterns, and in particular, the
  • GoF Strategy Pattern and why decoupling algorithms from clients improves design
  • GoF Abstract Factory Pattern and how it is useful when a system needs flexibility in creating related objects without tightly coupling to specific classes.

Objective

Upon successful completion of this assignment, the student has learned how to

• Implement Fibonacci with multiple strategies: naïve recursion, top-down (memoization), bottom-up (tabulation), iterative O(1), and fast doubling (O(log n)).
• Compare time/space trade-offs across DP techniques and justify their use.
• Encapsulate algorithms behind a GoF Strategy interface for clean substitution at runtime.
• Write C++ that passes clang-tidy bounds-safety guidance (prefer .at() over operator[]).
• Handle edge cases robustly (invalid input and 64-bit overflow beyond F(92)).
• Validate correctness with GoogleTest unit tests.

Getting Started

After accepting this assignment with the provided GitHub Classroom Assignment link, decide how you want to work with your newly created repository:

• Using Codespaces directly in your web browser that employees the Visual Studio Code online IDE, or
• Using the IDE of your choice on your local machine

See setup for more details around setting up your development environment once you’ve cloned your assignment.

Tasks

This assignment consists of the following tasks:

• Task 1: Implement a naive strategy
• Task 2: Implement a top-down strategy (memoization)
• Task 3: Implement a bottom-up strategy (tabulation)
• Task 4: Implement an iterative strategy (O(1))
• Task 5: Implement a fast doubling strategy (O(log n))

Once accomplished, you will have contributed to a large program built on sound engineering design principles. The following class diagram shows the classes involved.

Figure 1: Design Patterns in play for homework 3.

In this assignment, you’ll be implementing five different strategies for computing the nth number of the Fibonacci sequence.

Below are generalizations of the Strategy pattern employed in this application.

Figure 2: Generalized Class Diagram for the Strategy Pattern.

Figure 3: Generalized Sequence Diagram for the Strategy Pattern.

Task 1: Implement a naive strategy

Enumerated below are the essential steps to completing this task. For a deeper dive before you begin, see the Task 1 Details document.

1. Navigate to the include/csc232.h header file and toggle the TEST_TASK1 macro definition from FALSE to TRUE and erase the corresponding TODO comment.
2. Open the src/main/cpp/naive_strategy.cpp source file and implement the compute method accordingly.
3. Use the unit_tests target to verify your solution.
4. When you are happy with the results of your verification, stage, commit, and push your changes to GitHub.

Task 2: Implement a top-down strategy (memoization)

Enumerated below are the essential steps to completing this task. For a deeper dive before you begin, see the Task 2 Details document.

1. Navigate to the include/csc232.h header file and toggle the TEST_TASK2 macro definition from FALSE to TRUE and erase the corresponding TODO comment.
2. Open the src/main/cpp/top_down_memo_strategy.cpp source file and implement the compute method accordingly.
3. Use the unit_tests target to verify your solution.
4. When you are happy with the results of your verification, stage, commit, and push your changes to GitHub.

Task 3: Implement a bottom-up strategy (tabulation)

Enumerated below are the essential steps to completing this task. For a deeper dive before you begin, see the Task 3 Details document.

1. Navigate to the include/csc232.h header file and toggle the TEST_TASK3 macro definition from FALSE to TRUE and erase the corresponding TODO comment.
2. Open the src/main/cpp/bottom_up_tabulation_strategy.cpp source file and implement the compute method accordingly.
3. Use the unit_tests target to verify your solution.
4. When you are happy with the results of your verification, stage, commit, and push your changes to GitHub.

Task 4: Implement an iterative strategy (O(1))

Enumerated below are the essential steps to completing this task. For a deeper dive before you begin, see the Task 4 Details document.

1. Navigate to the include/csc232.h header file and toggle the TEST_TASK4 macro definition from FALSE to TRUE and erase the corresponding TODO comment.
2. Open the src/main/cpp/iterative_strategy.cpp source file and implement the compute method accordingly.
3. Use the unit_tests target to verify your solution.
4. When you are happy with the results of your verification, stage, commit, and push your changes to GitHub.

Task 5: Implement a fast doubling strategy (O(log n))

Enumerated below are the essential steps to completing this task. For a deeper dive before you begin, see the Task 5 Details document.

1. Navigate to the include/csc232.h header file and toggle the TEST_TASK5 macro definition from FALSE to TRUE and erase the corresponding TODO comment.
2. Open the src/main/cpp/fast_doubling_strategy.cpp source file and implement the compute method accordingly.
3. Use the unit_tests target to verify your solution.
4. When you are happy with the results of your verification, stage, commit, and push your changes to GitHub.

Submission Details

Before submitting your assignment, be sure you have pushed all your changes to GitHub. If this is the first time you’re pushing your changes, the push command will look like:

git push -u origin develop

If you’ve already set up remote tracking (using the -u origin develop switch), then all you need to do is type

git push

As usual, prior to submitting your assignment on Brightspace, be sure that you have committed and pushed your final changes to GitHub. Once your final changes have been pushed, create a pull request that seeks to merge the changes in your develop branch into your main branch.

You can use gh to create this pull request right from your command-line prompt:

gh pr create --assignee "@me" --title "Some appropriate title" --body "A message to populate description, e.g., Go Bills!" --head develop --base main --reviewer msu-csc232-fa25/graders

An “appropriate” title is at a minimum, the name of the assignment, e.g., LAB02 or HW04, etc.

Once your pull request has been created, submit the URL of your assignment repository (i.e., not the URL of the pull request) as a Text Submission on Brightspace. Please note: the timestamp of the submission on Brightspace is used to assess any late penalties if and when warranted, not the date/time you create your pull request. No exceptions will be granted for this oversight.

Due Date

Your assignment submission is due by 23:59 Monday 02-March-2026.

Grading Rubric

This assignment is worth 5 points.

Criteria	Exceeds Expectations	Meets Expectations	Below Expectations	Failure
Pull Request (20%)	Submitted early, correct url	Submitted on-time; correct url	Incorrect URL	No pull request was created or submitted
Code Style (20%)	Exemplary code style	Consistent, modern coding style	Inconsistent coding style	No style whatsoever or no code changes present
Correctness^ (60%)	All unit tests pass	At least 80% of the unit tests pass	At least 60% of the unit tests pass	Less than 50% of the unit tests pass

^ The Google Test unit runner will calculate the correctness points based purely on the fraction of tests passed.

Late Penalty

• In the first 24-hour period following the due date, this assignment will be penalized 20%.
• In the second 24-hour period following the due date, this assignment will be penalized 40%.
• After 48 hours, the assignment will not be graded and thus earns no points.

Disclaimer & Fair Use Statement

This repository may contain copyrighted material, the use of which may not have been specifically authorized by the copyright owner. This material is available in an effort to explain issues relevant to the course or to illustrate the use and benefits of an educational tool. The material contained in this repository is distributed without profit for research and educational purposes. Only small portions of the original work are being used and those could not be used to easily duplicate the original work.