Reference no: EM133870999

Algorithms and Analysis

Dynamic Programming in Action: The Knapsack-Maze Challenge

Learning Outcome 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;

Learning Outcome 2: Define, compare, analyse, and solve general algorithmic problem types: sorting, searching, graphs and geometric;

Learning Outcome 3: Theoretically compare and analyse the time complexities of algorithms and data structures; and

Learning Outcome 4: Implement, empirically compare, and apply fundamental algorithms and data structures to real-world problems.

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.

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! Expert online assignment help in the USA!

Task A: Maximising Knapsack Capacity using Recursion
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
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.

Task B: Maximising Knapsack using Dynamic Programming
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:

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-1, 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
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
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.

Task C: Analysis of the Complete Problem
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
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:
Algorithm Complexity Analysis: Strongly justify (perhaps with reference to the equa- tions and/or pseudo-code):
the theoretical time complexities of both knapsack solutions from Tasks A and B; and
the theoretical time complexity for the function findItemsAndCalculatePath.
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).

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?
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.

Task D: Maximizing Knapsack Value without Having the Map
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.

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 |T | . 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 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
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.

For a solution to be valid, it must:
have a path P that begins at the entrance;
have a path P that ends at the exit;
have a path P such that each sequential element is adjacent, so if Pk = (i, j) then:
Pk+1 = (i + 1, j) or (i - 1, j) or (i, j + 1) or (i, j - 1)
and Pk+1 and Pk do not have a wall between them.
the weight of the items in the knapsack must not exceed its capacity; and
the solution cannot use prior knowledge of item locations - a cell can only be checked for an item after it has been visited (and so must be added to the path P).

Report Task

The written report must include:
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;

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 6 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.

Attachment:- Dynamic Programming in Action.rar