Algorithms and Analysis

COSC2123/3119

Dynamic Programming in Action: The Knapsack-Maze Challenge

1 Learning Outcomes

This assessment relates to four learning outcomes of the course which are:

•  CLO 1: Compare, contrast, and apply the key algorithmic design paradigms: brute force, divide and conquer, decrease and conquer, transform and conquer, greedy, dynamic pro- gramming and iterative improvement;

•  CLO 3: Define, compare, analyse, and solve general algorithmic problem types: sorting, searching, graphs and geometric;

•  CLO 4: Theoretically compare and analyse the time complexities of algorithms and data structures; and

•  CLO 5:  Implement, empirically compare, and apply fundamental algorithms and data structures to real-world problems.

2 Overview

Across multiple tasks in this assignment, you will design and implement algorithms that navi- gate a maze to collect treasures. You will address both fully observable settings (where treasure locations are known) and partially observable ones (where treasure locations are unknown), which requires strategic exploration and value estimation when solving the maze. Some of the components ask you to critically assess your solutions through both theoretical analysis and controlled empirical experiments to encourage reflection on the relationship between algorithm design and real-world performance. The assignment emphasizes on strategic thinking and the ability to communicate solutions clearly and effectively.

Important Notes

Please read all the following information before attempting your assignment.

•  This is an individual assignment.  You may not collude with any other person (or peo- ple) and plagiarize their work.  Everyone is expected to present the results of their own thinking and writing. Never copy another student’s work (even if they “explain it to you first”) and never give your written work to others. Keep any conversation high-level and never show your solution to others. Never copy from the Web or any other resource or use Generative AI like ChatGPT to generate solutions or the report. Suspected cases of collusion or plagiarism will be dealt with according to RMIT Academic integrity policy.

•  This assignment requires submitting both a written report and your implemented code via GitHub Classroom. You must include your report file in the repository and tag your submission appropriately (with the tag  submission) before the deadline.   Detailed instructions for submission via GitHub Classroom are provided in the assignment repos- itory.

•  Before implementing any code, please carefully read the README section provided in the skeleton code repository and add or modify code only within the files explicitly marked with the comment / *  PLEASE  UPDATE  THIS  FILE .   */.   Any changes outside these marked sections may negatively affect the reliability of your solution and could cause your submission to fail our automated tests.

•  You are expected to properly use git version control and commit regularly, with clear and meaningful messages to reflect the progress of your development. Submitting your entire solution in a single commit, or in just a few large commits, is considered poor practice. Please note that marks from automatic tests will be adjusted based on how well you follow these practices. A submission that works perfectly but shows no evidence of a thoughtful development process will receive zero marks. Full marks will only be awarded when correct implementation is paired with clear evidence of good version control and development discipline.

•  Respect the word and page limits specified for the report.  Content beyond the specified limits will not be read and will not be considered in marking.

•  Strictly adhere to the assignment submission deadline. The deadline will not be extended under any circumstances, except in the event of natural disasters or similar emergencies.

•  Please check the Ed forum discussion for further clarifications about specifications.  In addition, Week 7 workshops are dedicated to walk you through the key elements of the assignment. Elham will also go through different aspects of the assignment each week, so even if you cannot make it to the lectorials, make sure to check the recordings.

•  In the submission (your PDF file for the report) you will be required to certify that the submitted solution represents your own work only by including the following statement:

3 Assessment details

The assignment is broken up into a number of tasks, to help you progressively complete the project. Please note that although completing one task can assist with subsequent tasks, each task can be attempted independently.  Moreover, the tasks are designed in a way that even in cases where your implementation does not fully achieve the expected output, you can still dis- cuss and present the theoretical aspects of your algorithmic design through your report.

Motivation

You are to assist an adventurer searching for treasure. They have heard tales about a maze filled with valuable treasures.  The Adventurer’s goal is to enter the maze, find and collect as many treasures as they can, and then leave through a different exit. Once they enter, the entrance will close behind them, so they must find another way out!

Figure 1: A breakdown of all the information available to The Adventurer.  The layout of the maze (made up of n × m cells), as well as entrance/exit locations and treasure locations (in- cluding the value and weight of each treasure). The book tells The Adventurer the information in the centre column - number of treasures, total value and total weight of all treasures.

As shown in Figure 1, in their possession The Adventurer has:

• an enchanted bag with carrying capacity c (the maximum weight it can hold);

• a mystical map, which tells them:

– the layout of the maze (which is fully connected but may have cycles and is always rectangular of size n × m with square cells) including the entrances, exits, and walls;

– the location, li , weight wi  and value vi  of each treasure i; The location of a treasure is in the form of (col, row), where 0 ≤ col ≤ m - 1 and 0 ≤ row ≤ n - 1. As can be seen in the Treasure Set T in Figure 1, the row numbers start from bottom to top and the column numbers start from left to right. The treasures are also sorted using a bottom-to-top, left-to-right sweep.

• a magical book, which contains:

– the number of treasures in the maze |T| ;

– the total value of all the treasures in the maze and

– the total weight of all the treasures in the maze

Objective

Your objective is to assist The Adventurer in gathering as many valuable treasures as their knapsack can carry. Mathematically, you wish to:

where:

•  si   = 1 means the ith  treasure is picked up while si   = 0 means the ith  treasure is left behind;

•  P = ⟨(i, j), ...⟩ is the ordered multiset of cells The Adventurer plans to visit (where the first element is the entrance, the last element is the exit, and each element is adjacent to the previous element).

In other words, we wish to find the shortest path through the maze that maximises the value of our knapsack, subject to the condition that the total weight of the knapsack is less than or equal to its maximum carrying capacity.

Completing Tasks A, B, C, and D will take you through different methods for completing this objective. Please read each Task carefully, and implement only what is asked in each Task.

Figure 2: A solution for The Adventurer given the specific problem in Figure 1.  We can see that the optimal treasures have been selected in the treasure set T, their positions highlighted on the map, and a route has been planned that takes The Adventurer through each cell containing an optimal treasure to collect before going through the exit.

Task A: Maximising Knapsack Capacity using Recursion (5 marks)

In order to accomplish the objective, it would probably be prudent to start by planning which treasures are the best to collect. To begin, put together a recursive strategy to find which com- bination of treasures would be best to collect: For the knapsack problem, the algorithm recur- sively calculates the optimal solution to sub-problems by considering each treasure’s inclusion and exclusion.

Implementation Task - 5 marks

Implement the below algorithm for recursive knapsack using the skeleton code provided.  En- sure that the input and outputs of the function are as described.

Algorithm 1 RecursiveKnapsack(T, c, k)

Input: T, a map of treasures where treasure IDs are mapped to location, weight, value pairs, i.e., ti   : (li , wi , vi ), a positive integer c of knapsack carrying capacity, a positive integer k of number of treasures, i.e., |T| .

Output: A list of locations,  Lopt  that correspond to optimal treasures to collect,  a positive integer, wopt  as the total weight of the treasures in the knapsack and a positive integer, vopt  as the optimal value given the knapsack capacity.

Lopt  ← empty ; wopt  ← 0 ; vopt ← 0

if c = 0 or k = 0 then

Return Lopt , wopt  and vopt

location ← location of the treasure in the kth  location

weight ← weight of the treasure in the kth  location

value ← value of the treasure in the kth  location

if weight > c then

Return RecursiveKnapsack(T, c, k - 1)

include location, include weight include value = RecursiveKnapsack(T, c - weight, k - 1) exclude location, exclude weight, exclude value = RecursiveKnapsack(T, c, k - 1)

if include value + value > exclude value then

Lopt  ← Lopt ∪ {location}

wopt  = wopt + weight

vopt  = vopt + value

else

Lopt  ← exclude location

wopt  = exclude weight

vopt  = exclude value

Return Lopt , wopt  and vopt

Report Task - 0 mark

You are NOT required to write anything in your report for Task A.

Task B: Maximising Knapsack using Dynamic Programming (7 marks)

For Task A, you implemented a recursive algorithm to solve the knapsack problem in order to find the optimal treasures to collect when you enter the maze.  As a fail-safe to ensure you have definitely found the best solution, you must implement another method using dynamic programming. If you are correct, both solutions should come to the same conclusion!

Whilst the approach in Task A required recursion to find solutions to sub-problems, dynamic programming allows you to store previous solutions to sub-problems and use them to solve future problems. We do this by filling in a dynamic-programming table such that:

for i  ∈ {0, 1,..., T} and j  ∈  {0, 1,..., c}.  F(i, j) is the most valuable subset of the first i treasures that fit into a knapsack with capacity j and F(0, j) = F(i,  0) = 0 makes up our initial conditions - the optimal solution if we have no treasures or a knapsack with a carrying capacity of 0.

Intuition

For each F(i, j), we consider picking up treasure i for a knapsack with carrying capacity j. We therefore check the last optimal solution where the new treasure would be able to fit in our bag (F(i, j - wi )) and see if this value (plus the value of the current treasure vi ) exceeds the optimal solution if the treasure is not picket up which is captured by F(i - 1, j). The optimal solution for the subproblem is the maximum of these two values. The index F(|T|, c) will hold the maximum value the knapsack can take for all the treasures.

Implementation Task - 5 marks

In the provided skeleton code, implement the dynamic programming solution to the knapsack problem using memory functions (or lazy/sparse programming).  Your function should take in exactly the same input arguments as Task A. It should return a tuple containing the loca- tion for the optimal treasures to take, the total weight of the items in the knapsack and the value (again, just as Task A does).  Your function also needs to generate a csv file to save the dynamic programming table where each row correspond to the ith  treasure and every col- umn (separated by a comma) corresponds to a capacity between 0 to c (a function to convert a dynamic-programming table to CSV file is provided for you). The snapshot in Figure 3 shows the dynamic programming table using memory functions for the example provided in Fig- ure 1. You can find the relevant information regarding memory functions in the lecture notes and lecture recordings of Week 9.

Report Task - 2 marks

In your report, write the pseudo-code for this problem (use the pseudo-code in Task A as a guide for how to do this). Briefly explain the potential benefits and downsides of this approach against the approach in task A. Total page limit for Task B is one page.

Figure  3:    Example  of  a dynamic  programming  ta- ble constructed using mem- ory functions. Cells marked with # indicate subproblems that  were  never  computed during the execution. Non # entries represent the values computed and stored for the function F(i, j).

Task C: Analysis of the Complete Problem (8 marks)

Now you are sure which treasures to collect, you can begin finding an optimal path P to enter the maze through the entrance, pick up the optimal treasures, and leave the maze through the exit. Luckily, the mystical map calculates this for you! But you’d like to know how it works...

In this task, you will empirically compare the two algorithms you implemented in Tasks A and B. You are provided with a function findItemsAndCalculatePath in the skeleton code. This function: (1) Takes as input the maze structure, entrances, exits, treasure layout and knapsack strategy (recursive or DP); and (2) executes a path-finding solution to find the shortest possible path from an entrance to an exit while collecting all the treasures that result in the optimal output. Your task is to (i) understand this function and to (ii) conduct a meaningful empirical analysis of your two strategies in Task A and B.

Implementation Task - 0 mark

While you are required to implement and run tests as part of this task, no marks are awarded for the implementation itself. Marks will be given based solely on the quality of your analysis, experimental design, and discussion in the report (see bellow).

Report Task - 8 marks

Your report should include:

1. Algorithm Complexity Analysis: Prove:

(a)  the theoretical time complexities of both knapsack solutions from Tasks A and B; and

(b)  the theoretical time complexity for the function findItemsAndCalculatePath.

2. Empirical Design:  Highlight which variables you believe are important when calcu- lating the algorithmic complexity of the function findItemsAndCalculatePath with the recursive/dynamic-programming knapsack solution.  Explain why this is the case, and why you chose to ignore other variables (if any).

3. Empirical Analysis: Provide a thorough analysis using one or more plots to compare the running time of findItemsAndCalculatePath with the two different knapsack strategies from Task A and B. How would you interpret your observation?

4. Reflection: Discuss whether your empirical results align with your theoretical complex- ity predictions. If there are discrepancies, explain possible causes — e.g., implementation details, constant factors, etc.

Total page limit for Task C is two pages.

Task D: Maximizing Knapsack Value without Having the Map (10 marks)

In this task, we consider a scenario where The Adventurer explores a maze to collect treasures without knowing their exact locations.   The full maze structure (maze layout) is known in advance, but the locations of treasures are not. The adventurer only knows:

•  The total number of treasures, |T|, present somewhere in the maze; and

• the total combined value of all treasures, v; and

• treasures combined weight w and minimum weight 1.

Figure 4: The new problem presented to The Adventurer.  The maze layout, total number of treasures, and their total value and weight are known in advance.  However, the locations of each these treasures, as well as their specific attributes, is a mystery.

The Adventurer assumes that (i) there is only one entrance and one exit in the maze, and (ii) all cells have equal chance to have a treasure.  In other words, the initial probability of a cell containing a treasure is equal to On top of all this, the maze is full of terrors - The Adventurer wishes to minimise exploration (where possible).  They must navigate the maze and search the cells strategically to collect treasures and maximize the net reward objective:

Reward = knapsack value - cells explored

Your task is to design and implement an algorithm to employ a treasure search after entering the maze which aims to maximize collected treasure value while minimizing the number of cells explored.  Your solution must strategically decide which cells to explore, taking into account the trade-off between the value of potential treasures and the exploration cost associated with

Figure 5: Example of different probability distributions for treasure placement.  The uniform distribution (left) implies that all cells have an equal probability to have a treasure (4% in a 5 by 5 maze). The other two examples show different scenarios where the yellow cells have the highest probability to have a treasure followed by green and blue cells.

entering additional cells.  The implementation should use the prior knowledge of the maze’s layout, total treasure count, cumulative treasure value, and weight distribution, to effectively balance exploration and exploitation.

Implementation Task - 5 marks

Implement your solution in the provided code skeleton for Task D. Your solution receives as input, the maze, T, v and w, and outputs the sequence of cells explored from the entrance to the exit (repetitions are allowed, i.e. re-entering a cell you have already visited does not count as a new explored cell) as well as the selected treasures.  Your solutions will be tested against our own solution, and marks will be awarded based on a weighting system in terms of the total Reward gained.

Report Task - 5 marks

The written report must include:

1. Algorithms Design: Regardless of whether or not you have implemented your solution, in your report describe your exploration and treasure-selection strategy. Include pseudo- code and explain how your approach balances between expected treasure value and cell cost. Clearly discuss the complexity of your solution with regard to the input;

2. Assumptions Explain how your algorithm handles different probability models for trea- sure placement. Clearly discuss if and how your solution can handle cases where there is a spatial bias in the distribution of the treasures, e.g., the probability of having a treasure is higher for cells that are more distant from the entrance and exits.  See Figure 5 for some potential examples. Please note that your answer does not need to focus on finding a solution for a specific probability distribution. You are only required to discuss if and how your solution could be impacted by the change in the initial assumption.

Total page limit for Task D is two pages.

4 Assessment

The project will be marked out of 30. The assessment in this project will be broken down into several parts for each Task. The criteria discussed in Table 1 will be considered when allocating marks.

5 Late Submission Penalty

Late submissions will incur a 10% penalty on the total marks of the corresponding assessment task per day or part of day late, i.e, 3 marks per day.  Submissions that are late by 5 days or more are not accepted and will be awarded zero, unless special consideration has been granted. Please ensure your submission is correct (more details in the FAQ Resources available via the Ed Forum) as re-submissions after the due date and time will be considered as late submissions. We strongly advice you submit at least one hour before the deadline. Late submissions due to slow Internet will not be looked upon favorably, even if it is a few minutes late. Any claim of late submission due to slow Internet will require documentation and evidence that submission attempts were made at least one hour before the deadline.

6 Academic integrity and plagiarism (standard warning)

Academic integrity is about honest presentation of your academic work. It means acknowledg- ing the work of others while developing your own insights, knowledge and ideas.  You should take extreme care that you have:

•  Acknowledged words, data, diagrams, models, frameworks and/or ideas of others you have quoted (i.e. directly copied), summarised, paraphrased, discussed or mentioned in your assessment through the appropriate referencing methods.

•  Provided a reference list of the publication details so your reader can locate the source if necessary. This includes material taken from Internet sites. If you do not acknowledge the sources of your material, you may be accused of plagiarism because you have passed off the work and ideas of another source without appropriate referencing, as if they were your own.

RMIT University treats plagiarism as a very serious offense constituting misconduct.  Plagia- rism covers a variety of inappropriate behaviours, including:

• Failure to properly document a source

•  Copyright material from the internet or databases

•  Collusion between students

For further information on our policies and procedures, please refer to this link.