CSCI 3212 Lab 6

Due Sunday, 04/14/2024, by midnight (23:59, EST), on Blackboard

Announcements

1. Dynamic Programming

  • Objective:

Understanding and applying memoization and tabulation techniques.
Identifying problems that can be solved with dynamic programming.
Analyzing the time and space complexity of dynamic programming solutions.

1.1. Part I: Introduction

1.1.1. An Overview

Dynamic programming is a method for efficiently solving complex problems by breaking them down into simpler subproblems. It’s a powerful technique in the field of computer science, particularly in the realm of algorithms and optimization. The core idea behind dynamic programming is to avoid recomputing the solution to a subproblem that has already been solved, thereby reducing the overall computation time.

At its heart, dynamic programming relies on two key concepts:

  • Overlapping Subproblems: This occurs when a problem can be broken down into subproblems, which are reused several times. For example, in calculating the Fibonacci sequence, fib(5) requires fib(4) and fib(3), while fib(4) requires fib(3) and fib(2). Here, fib(3) is an overlapping subproblem.

  • Optimal Substructure: This property means that the optimal solution to a problem can be constructed from the optimal solutions of its subproblems. In other words, if we know the optimal solutions to the subproblems, we can combine them to find the overall optimal solution.

Dynamic programming solutions typically use two approaches: Memoization and Tabulation.

  • Memoization is a top-down approach where you solve the problem by first solving all its subproblems and storing their results in a table (usually an array or dictionary). If the subproblem is encountered again, the solution is retrieved from the table, avoiding recalculation.

  • Tabulation is a bottom-up approach where you solve all the subproblems first and use their solutions to build up solutions to bigger problems. This method fills up a table in a manner that each entry in the table depends on previous entries, thus systematically solving for the final solution.

Dynamic programming is widely used in various domains such as bioinformatics, finance, and operations research, solving problems related to optimization, sequencing, and scheduling, among others. In this lab, we will explore dynamic programming through practical coding exercises, starting with fundamental problems and progressing to more complex challenges.

1.1.2. Pre-Lab Preparation

  • Reading Assignment: see the shared google folder. Pay attention to the basics of dynamic programming, including memoization, tabulation, and the identification of overlapping subproblems and optimal substructure.

  • Pre-Lab Video: see the shared google folder. Walks through the dynamic programming approach, particularly focusing on the Fibonacci sequence, to ensure all students come in the lab with a foundational understanding.

1.2. Part II: Exercises

1.2.1. Exercises:

1.3. Lab Report

  • Students should submit a lab report that includes:

    1. Source code for all implemented algorithms.

    2. A brief description of each algorithm’s implementation.

    3. Comparative analysis results with discussion.

    4. Reflection on what was learned and any challenges encountered.

1.3.1. Lab Tasks:

  • Implementation: For each exercise, implement a solution using the required data structure or algorithm. Pay attention to the unique challenges each problem presents.

  • Analysis: After implementing your solution, analyze its time and space complexity.

1.3.2. Lab Report Instructions:

  • Your Solution(s): Outline your approach, providing both pseudocode and source code. Discuss the time and space complexities.

  • Reflection: Reflect on the learning process. What challenges did you encounter, and how did you overcome them?

2. Submission Guide

  • Each student only submits one file, lab_6_firstname_lastname.zip (file size less than 5 M), including

    1. A Code folder for your Java code files, including all the programming tasks mentioned above.

    2. Notes_lab_6_lastname.txt for your notes, including all the writing tasks mentioned above.

3. Notes

  • Submit your zip file for lab 6 to Blackboard.

  • Lab assignments will typically be due by midnight on Sunday.